代码随想录算法训练营 Day 8
Published:
Q1. LeetCode 151
解法1. 将字符串按空格分开，翻转，然后输出
class Solution:
def reverseWords(self, s: str) -> str:
s = s.strip().split()
s = s[::-1]
return ' '.join(word for word in s)
解法2: 思路类似，但采用双指针
class Solution:
def reverseWords(self, s: str) -> str:
s = s.strip().split()
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
return ' '.join(word for word in s)
解法3. 1. 删除头尾可能出现的空格；2. 将整个字符串进行翻转；3. 将其中的每个单词进行翻转
class Solution:
def reverseWords(self, s: str) -> str:
s = s.strip()
s = s[::-1]
return ' '.join(word[::-1] for word in s.split())
复杂度分析
时间复杂度：O($n$) 空间复杂度：O($n$)
Take some notes
理解其他语言的写法，算法的考查要点
Q2. KamaCoder 55
思路：与Q1类似，先将整个字符串翻转，然后将字符串看作两部分：前k个和其余部分，对这两个部分分别进行翻转
k = int(input())
s = input()
# reverse the whole string
s = s[::-1]
# reverse the first k characters and the rest characters respectively
s = s[:k][::-1] + s[k:][::-1]
print(s)
复杂度分析
时间复杂度：O($n$) 空间复杂度：O($n$)
Q3. LeetCode 28
解法1: 回溯法
思路：遍历字符串haystack和needle，若对应字符相等，则继续；若不相等，则将haystack指针所指位置需要减去当前needle遍历过的长度
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if len(haystack) == 0:
return 0
n = len(haystack)
i = 0
j = 0
while i < n:
if haystack[i] == needle[j]:
j += 1
if j == len(needle):
return i - len(needle) + 1
else:
i -= j
j = 0
i += 1
return -1
解法2: KMP算法
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if len(needle) == 0:
return 0
next = self.getNext(needle)
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):
j = 0
next = [0] * len(s)
next[0] = j
for i in range(1, len(s)):
# 先判断是否不相等，因为相等的情况会更新j
while j > 0 and s[i] != s[j]:
j = next[j - 1]
if s[i] == s[j]:
j += 1
next[i] = j
return next
复杂度分析
时间复杂度：O($n$) 空间复杂度：O(1)
TODO
完成Q4，巩固并总结KMP算法