一刷：6月3日到6月9日
反转字符串
l=0
r=len(s)-1
while l<r:
s[l],s[r]=s[r],s[l]
l+=1
r-=1
反转字符串II
res=list(s)
for i in range(0,len(s),2*k):
res[i:i+k]=res[i:i+k][::-1]
return "".join(res)
替换数字
没有使用额外的空间
s=list(input())
l=len(s)-1
x=['r','e','b','m','u','n']
num=0
for i in s:
if i.isdigit():
num+=1
for i in range(num*5):
s.append(0)
idx_2=len(s)-1
for idx_1 in range(l,-1,-1):
if s[idx_1].isdigit():
for sx in x:
s[idx_2]=sx
idx_2-=1
else:
s[idx_2]=s[idx_1]
idx_2-=1
print("".join(s))
翻转字符串里的单词
s.strip()
s=s[::-1]
return " ".join([x[::-1] for x in s.split()])
右旋转字符串
这么写超时了。。。
k=int(input())
s=list(input())
for i in range(k):
x=s[-1]
for i in range(len(s)-1,0,-1):
s[i]=s[i-1]
s[0]=x
print("".join(s))
这个跟上一题翻转字符串里的单词有异曲同工之妙
k=int(input())
s=list(input())
s=s[::-1]
s[0:k]=s[0:k][::-1]
s[k:]=s[k:][::-1]
print("".join(s))
实现strStr(())
KMP算法的实现
i是后缀末尾
j是前缀末尾
def getnext(self,s,next):
j=0
next[0]=0
for i in range(1,len(s)):
while j>0 and s[j]!=s[i]:
j=next[j-1]
if s[i]==s[j]:
j+=1
next[i]=j
return next
def strStr(self, haystack, needle):
next=[0]*len(needle)
self.getnext(needle,next)
j=0
for i in range(len(haystack)):
while j>0 and haystack[i]!=needle[j]:
j=next[j-1]
if haystack[i]==needle[j]:
j+=1
if j==len(needle):
return i-len(needle)+1
return -1
重复的子字符串
def getnext(self,s):
next=[0]*len(s)
j=0
next[0]=0
for i in range(1,len(s)):
while j>0 and s[j]!=s[i]:
j=next[j-1]
if s[i]==s[j]:
j+=1
next[i]=j
return next[-1] #返回最大相等公共子字符串的最大数
def repeatedSubstringPattern(self, s):
num=self.getnext(s)
if len(s)%(len(s)-num)==0 and num!=0: #有可能返回为0,如"abac"
return True
else:
return False
