网站投票活动怎么做,哪个网站可以做c语言的题,wordpress 常规选项,云脑网络科技网站建设打卡Day9 1.151.翻转字符串里的单词2.右旋字符串3.28. 实现 strStr()4.459.重复的子字符串 1.151.翻转字符串里的单词
题目链接#xff1a;翻转字符串里的单词 文档讲解#xff1a; 代码随想录
思路#xff1a;首先#xff0c;移除多余的空格#xff1b;然后#xff0c… 打卡Day9 1.151.翻转字符串里的单词2.右旋字符串3.28. 实现 strStr()4.459.重复的子字符串 1.151.翻转字符串里的单词
题目链接翻转字符串里的单词 文档讲解 代码随想录
思路首先移除多余的空格然后将整体字符串反转最后将单个单词反转。 在python中字符串是不可变类型因此需要将其转变成list再使用join函数将其再转变为字符串因此空间复杂度不是O1。
class Solution(object):def reverseWords(self, s)::type s: str:rtype: str#删除前后空白s.strip()#将整个字符串反转s s[::-1]#将单词反转s .join(word[::-1] for word in s.split())return sclass Solution(object):def reverseWords(self, s)::type s: str:rtype: strword s.split()left, right 0, len(word) - 1while left right:word[left], word[right] word[right], word[left]left 1right - 1return .join(word)class Solution(object):def reverseWords(self, s)::type s: str:rtype: strword s.split()word word[::-1]return .join(word) 面试的时候最好还是不要用内置的split函数所以我在力扣的解答里找到了一个不用split函数的答案。 思路首先删掉首位空格。然后需要定义一个新列表来存储从s中倒序取到的单词。接着定义两个指针 i 和 j初始位置在s的末尾左移 i 直至 s[i] 不为空格此时需要存储的单词就是 s[i1:j1]继续左移 i 以寻找下一个单词当遍历到 s[i] 不为空格时令 ji重复左移 i。最后使用 join 函数拼接字符串。
class Solution(object):def reverseWords(self, s)::type s: str:rtype: str#删掉首尾空格s s.strip()i j len(s) - 1res []while i 0:while i 0 and s[i] ! :i - 1res.append(s[i 1: j 1])while s[i] :i - 1j ireturn .join(res)2.右旋字符串
题目链接右旋字符串 文档讲解 代码随想录
k int(input())
s input()s s[-k:] s[:-k]print(s)k int(input())
s input()s s[lens(s) - k:] s[:len(s) - k]print(s)卡码网是需要有输入有输出的。
3.28. 实现 strStr()
题目链接实现 strStr() 文档讲解 代码随想录
暴力解法
class Solution(object):def strStr(self, haystack, needle)::type haystack: str:type needle: str:rtype: intm, n len(haystack), len(needle)for i in range(m):if haystack[i:in] needle:return ireturn -1KMP算法用来判断一个字符串是否出现在另一个字符串中。 前缀表不减一
class Solution:def getNext(self, next: list[int], s: str) - None:j 0next[0] 0for i in range(1, len(s)):while j 0 and s[i] ! s[j]:j next[j - 1]if s[i] s[j]:j 1next[i] jdef strStr(self, haystack: str, needle: str) - int:if len(needle) 0:return 0next [0] * len(needle)self.getNext(next, needle)j 0for i in range(len(haystack)):while j 0 and haystack[i] ! needle[j]:j next[j - 1]if haystack[i] needle[j]:j 1if j len(needle):return i - len(needle) 1return -1前缀表减一
class Solution:def getNext(self, next: list[int], s: str) - None:j -1next[0] -1for i in range(1, len(s)):while j 0 and s[i] ! s[j 1]:j next[j]if s[i] s[j 1]:j 1next[i] jdef strStr(self, haystack: str, needle: str) - int:if len(needle) 0:return 0next [0] * len(needle)self.getNext(next, needle)j -1for i in range(len(haystack)):while j 0 and haystack[i] ! needle[j 1]:j next[j]if haystack[i] needle[j 1]:j 1if j len(needle) - 1:return i - len(needle) 1return -14.459.重复的子字符串
题目链接重复的子字符串 文档讲解 代码随想录
除了暴力求解外还有两种解法。 1移动匹配字符串是由重复的子字符串组成则ss一定还存在一个s。在判断ss拼接的字符串中是否出现一个s的时候要刨除ss的首字符和尾字符以避免在ss中搜索出原来的s。
.find(s) 是字符串方法用于查找子字符串 s 在字符串 ss 中的第一次出现的位置索引。如果找到了则返回该子字符串第一次出现的索引值如果没有找到则返回 -1。
class Solution(object):def repeatedSubstringPattern(self, s)::type s: str:rtype: boolif len(s) 1:return Falsess s[1:] s[:-1]return ss.find(s) ! -12KMP算法
在由重复子串组成的字符串中最长相等前后缀不包含的子串就是最小重复子串。
t0 k0, t1 k1因此 t01 k01。 t2 k0, t3 k1因此 t23 k01。 t2 k2, t3 k3因此 t23 k23. 循环往下可以证明。
判断方法数组长度减去最长相同前后缀的长度相当于是第一个周期的长度也就是一个周期的长度如果这个周期可以被整除就说明整个数组就是这个周期的循环。
假设 s 是由 n 个重复子字符串 x 构成的s 的最长相等前后缀一定不包含 s 本身则一定是由 n-1 个 x 构成的。最长最长相等前后缀的长度为 next[len(s) - 1] 1则一个周期的长度为 len(s) - (next[len(s) - 1] 1)。
#前缀表减一
class Solution:def repeatedSubstringPattern(self, s: str) - bool:if len(s) 0:return Falsenet [0] * len(s)self.getNext(net, s)if net[- 1] ! -1 and len(s) % (len(s) - (net[- 1] 1)) 0:return Truereturn Falsedef getNext(self, net: list[int], s:str) - None:j -1net[0] -1for i in range(1, len(s)):while j 0 and s[j 1] ! s[i]:j net[j]if s[j 1] s[i]:j 1net[i] j#前缀表不减一
class Solution:def repeatedSubstringPattern(self, s: str) - bool:if len(s) 0:return Falsenet [0] * len(s)self.getNext(net, s)if net[- 1] ! 0 and len(s) % (len(s) - (net[- 1])) 0:return Truereturn Falsedef getNext(self, net: list[int], s:str) - None:j 0net[0] 0for i in range(1, len(s)):while j 0 and s[j] ! s[i]:j net[j - 1]if s[j] s[i]:j 1net[i] j
