1：字符串的循环左移
给定一个字符串s[0..........N-1],要求把S的前k个字符移动到S的尾部，如把字符串"abcdef"前面的2个字符'a','b'移动到字符串的尾部得到'cdefab',即左移k
循环左移k=循环右移n-k
核心公式：XY to YX
(X'Y')'=YX
def stringLeftReverse(s,n,k):
s=[i for i in s] #转化为列表
s=transportation(s,0,k-1) #X'
s=transportation(s,k,n-1) #Y'
s=transportation(s,0,n-1) #(X'Y')'
s=''.join(s) #将字符串列表转化为字符串
return s
#转置函数
def transportation(s,left,right): #字符串子序列的转置
while left<right:
#首尾交换
s[right],s[left]=s[left],s[right]#这样的操作只能是可变的序列，像字符串这样的不可修改，需要将字符串转化为列表操作，之后转化为字符串
#指针移动
left+=1
right-=1
return s #返回字符串本身
if __name__=='__main__':
s='asdfeg'
n=len(s)
k=2
print(stringLeftReverse(s,n,k))2：字符串的全排列
给定字符串s[0....N-1],设计算法，枚举字符串的全排列
eg:1234,
1---234全排列
2---134全排列
3---124全排列
4---123全排列
由上述可知这是一个递归问题。
(1)递归法---字符串的全排列:
def arrangementString(s,left,right):
if left==right:
print(''.join(s)) #将列表转化为字符串
for i in range(left,right+1): #left为当前递归序列的左边界，right为右边界
#i表示与当前递归序列首元素left要交换的元素
if isRepeat(s,left,i): #判断是否有重复字符 ，（left,i）注意这里要查询的范围
continue
s[i],s[left]=s[left],s[i]
arrangementString(s,left+1,right) #递归全排列
s[i],s[left]=s[left],s[i]
def isRepeat(s,left,right): #注意
flag=False
for i in range(left,right):
if s[i]==s[right]:
flag=True
break
return flag
if __name__=='__main__':
s='ABA'
s=[i for i in s] #将字符串转化为列表
left=0
right=len(s)-1
arrangementString(s,0,right)
(2)非递归法---字符串的全排列:
思路：先找出最小的；之后依次找出他的下一个比他大的排列。
问题化解为：下一个排列问题。
下一个排列问题：思路：从最末尾向前依次查找，当不满足升序停止。之后从停止位置向后查找，找出所有大于停止位置数值的元素，且找出最小的。之后交换停止位元素和最小元素。之后翻转，停止位之后的元素。
总结为：后找，大小，交换，反转。
def arrangementString(s,left,right):
s=sorted(s)
res=[]
while True:
res.append(''.join(s))
s=nextArrangeString(s,left,right) #寻找下一个大的全排列
if not s:
break
return res
def nextArrangeString(s,left,right):
#后找
i=right-1
while i>=0:
if s[i]>=s[i+1]:
i-=1
else:
break
#判断有无升序，即是否为最后一个全排列
flag=True
if i==-1:
flag=False
return flag
#大小
j=i+1
while j<=right:
if s[j]>s[i]:
j+=1
else:
break
minimum=min(s[i+1:j])
ind=s.index(minimum)
#交换
s[i],s[ind]=s[ind],s[i]
#翻转
s[i+1:right+1]=sorted(s[i+1:right+1])
s=s[0:i+1]+s[i+1:right+1]
return s
if __name__=='__main__':
s='211'
s=[i for i in s] #将字符串转化为列表
left=0
right=len(s)-1
print(arrangementString(s,left,right))3:文本串（text）和模式串 (pattern) 的匹配
方法1：BF（暴力搜索）
核心思想：如果匹配 text[i+j]==pattern[j] j++ ；如果不匹配 text[i]!=pattern[j] i++ j=0。
def BF(text,pattern):
size_text=len(text)
size_pattern=len(pattern)
i=0
j=0
while i<=size_text-1 and j<=size_pattern-1:
if text[i+j]==pattern[j]:#若匹配，模式串后移
j+=1
else:#若不匹配，模式串回到首位
i+=1
j=0
return i
if __name__=='__main__':
text='casascascascasddd'
pattern='ascasd'
result=BF(text,pattern)
print(result) 方法2：KMP算法：
核心思想：如果匹配 text[i]==pattern[j]： i++，j++ ；如果不匹配 text[i]!=pattern[j]： j=next[j]。
区别与BF,关键在于j不在返回0，而是返回next[j].
next[j]: next[j]=k k为在(p[1].....p[j-1])中，相等的前缀A和后缀B最大长度。
具体：next[j]如何求解看代码
# -*- coding: utf-8 -*-
"""
Created on Wed Aug 28 10:57:18 2019
@author: Melo.qi
字符串的模式匹配算法
KMP:改进的字符串匹配算法
####################
如果匹配
text[i]==pattern[j]
i++
j++
####################
如果不匹配
text[i]!=pattern[j]
j=next[j]
####################
关键的next[j] 第j个位置元素的相等的前缀和后缀最大长度
next[j]表示第在模式串的第j个位置与文本串不匹配
#next[j]=k k为在(p[1].....p[j-1])中，相等的前缀A和后缀B最大长度
#更新：next[j+1]
if pattern[k]==pattern[j]
next[j+1]=next[j]+1
if pattern[k]!=pattern[j]
h=next[k](h为p[1]....p[k-1]的相等的前缀和后缀最大长度)
if pattern[k]==pattern[j]
next[j+1]=h+1
重复上诉过程
###以上实现的是模式串在text[i]!=pattern[j] 时不再移动在起始位置0，而是移动到next[j]
####################
text：文本串
pattern:模式串
"""
def GetNext(p): #求解next
size_p=len(p)
j=0
Next=[0 for i in range(size_p)]
Next[0]=-1
k=-1 #初始的k值 Next[j]=k
while j<size_p-1:
if k==-1 or p[j]==p[k]:
j+=1
k+=1
Next[j]=k#不断更新求解Next
else:
k=Next[k]#实现递推的关键
return Next
def KMP(text,pattern):
size_text=len(text)
size_pattern=len(pattern)
next_label= GetNext(pattern)
#print(next_label)
i=0
j=0
while i<=size_text-1 and j<=size_pattern-1:
if j==-1 or text[i]==pattern[j]:#若匹配，模式串后移
j+=1
i+=1
else:#若不匹配，模式串移动到next[j]
#i不移动表示本文串不动，模式串向右移动
j=next_label[j]
#print(i,j)
return i-j
if __name__=='__main__':
text='casascascascasddd'
pattern='ascasd'
result=KMP(text,pattern)
print(result)4:字符串相乘
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
输入: num1 = "123", num2 = "456"
输出: "56088"
思路：模拟乘法过程
class Solution(object):
#函数：字符转化为整型数字
def str2int(self,s):
return ord(s)-ord('0')
def multiply(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
#模拟乘法过程
result=0
a=num1[::-1] #乘法过程是从低位到高位，因此先倒取
b=num2[::-1] #乘法过程是从低位到高位，因此先倒取
#两层循环
for i,x in enumerate(a):
for j,y in enumerate(b):
result=result+(self.str2int(y) *10**j)*(self.str2int(x)*10**i) #注意10进制的问题
return str(result)
if __name__=='__main__':
num1 = "123"
num2 = "456"
solution=Solution()
result=solution.multiply(num1, num2)
print(result) 5:最长无重复子串的最大长度
无重复字符的最长子串
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
思路：一次遍历；
同时建立字典映射来记录是否重复；字典的键为字符元素，字典的值为元素位置
问题是要问最大无重复的长度：我们用start表示无重复子串的起始位置，i为终点位置。长度为i-start+1
关键点在于更新start:当遇到重复字符且是相邻的重复元素的时候，start需要更新，更新为当前重复元素的位置，由于不能start=dic[cur]+1 或start=i
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
max_len=0
start=0 #start实现对窗口大小的调整（窗口有边界,循环变量i为左边界）
dic={} #利用创建的字典实现
for i in range(len(s)):
cur=s[i]
if cur not in dic.keys():
dic[cur]=i
else:
if dic[cur]+1>start:#关键
start=i #关键
#start=dic[cur]+1
dic[cur]=i #字典键值对更新，当有重复的元素出现，字典中的cur的value需要改变
if i-start+1>max_len:
max_len=i-start+1
return max_len
if __name__ == '__main__':
s = Solution()
print(s.lengthOfLongestSubstring("abcabcbb"))
print(s.lengthOfLongestSubstring("abba"))
print(s.lengthOfLongestSubstring("aabaaacds!bacdsb"))
print(s.lengthOfLongestSubstring("bbbbb"))6:整数和罗马数字之间的相互转化
整数--罗马数字
"""
Created on Mon Jul 29 19:31:42 2019
@author: Melo.qi
整数转罗马数字
思路：哈希查询，之后取整，之后切割，循环下去
"""
class Solution:
def intToRoman(self,num):
dict1={1:'I',
4:'IV',
5:'V',
9:'IX',
10:'X',
40:'XL',
50:'L',
90:'XC',
100:'C',
400:'CD',
500:'D',
900:'CM',
1000:'M'
}
res=''
for i in range((list(dict1.keys())[::-1])):#注意这里从大的开始
t=num//i #取整技巧
if not t:
continue
res=res+dict1[i]*t #结果的字符拼接
num=num-t*dict1[i] #num更新
if num==0:
break
return res罗马数字--整数
"""
Created on Tue Jul 30 14:46:36 2019
@author: Melo.qi
罗马数字转整数
"""
class Solution:
def romanToInt(self,s):
dict1={'M':1000,
'CM': 900,
'D': 500,
'CD': 400,
'C':100,
'XC':90,
'L':50,
'XL':40,
'X':10,
'IX': 9,
'V':5,
'IV':4,
'I':1
}
res=0
i=0
while i<len(s): #用while做循环，注意在循环体中要求改变循环变量i
if i+1<len(s) and s[i]+s[i+1] in dict1: #这中情况是针对双字节来说的
res+=dict1[s[i]+s[i+1]]
i+=2
elif s[i] in dict1:
res+=res+dict1[s[i]]
i+=1
return res7:最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
class Solution:
def expandAroundCenter(self, s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return left + 1, right - 1
def longestPalindrome(self, s: str) -> str:
start, end = 0, 0
for i in range(len(s)):
left1, right1 = self.expandAroundCenter(s, i, i)
left2, right2 = self.expandAroundCenter(s, i, i + 1)
if right1 - left1 > end - start:
start, end = left1, right1
if right2 - left2 > end - start:
start, end = left2, right2
return s[start: end + 1]
版权声明：本文为Melo0705原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。