344.反转字符串
题目简述:
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。不要给另外的数组分配额外的空间,你必须原地修改输入数组,使用O(1)的额外空间解决这一问题。
解题思路:
没什么好说的,直接双指针
代码如下:
class Solution: def reverseString(self, s: List[str]) -> None: """ Do not return anything, modify s in-place instead. """ n=len(s) left=0 right=n-1 while(left<right): s[left],s[right]=s[right],s[left] left+=1 right-=1 return s
541.反转字符串II
题目简述:
给定一个字符串 s 和一个整数 k,从字符串开头算起,每计数至 2k 个字符,就反转这 2k 字符中的前 k 个字符。
- 如果剩余字符少于 k 个,则将剩余字符全部反转。
- 如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,其余字符保持原样。
思路:
老实说,一开始没怎么看懂题目。后来理解了,意思是从左到右从1数到2k,这样算一个循环,然后反转前k个字符,之后数数又从1开始,即遍历到第2k+1个字符从1开始数,不是说回过头去遍历第一个字符。
1. 首先把字符串转为列表
2. 利用for循环遍历,每次走2k步,也即0,2k,4k......这样取值
3. 对下标为[0,2k-1],[2k,4k-1]......的分片列表进行反转
4. 利用join函数整合成为字符串
代码如下:
class Solution: def reverseStr(self, s: str, k: int) -> str: t = list(s) for i in range(0, len(t), 2 * k): t[i: i + k] = reversed(t[i: i + k]) return "".join(t)
剑指Offer 05.替换空格
题目简述:
请实现一个函数,把字符串 s
中的每个空格替换成"%20"。
思路:
1. 创建一个空列表。
2. 遍历s,遇到字符,往空列表中append该字符;遇到空格,append %20即可
3. 利用join函数输出
代码实现:
class Solution: def replaceSpace(self, s: str) -> str: res = [] for c in s: if c == ' ': res.append("%20") else: res.append(c) return "".join(res)
151.翻转字符串里的单词
思路:
1. 去除字符串开头和结尾的空白字符
2. 去掉字符串间多余的空白字符
3. 翻转整个字符串
4. 逐个翻转各个单词
代码如下:
class Solution: def trim_spaces(self, s: str) -> list: left, right = 0, len(s) - 1 # 去掉字符串开头的空白字符 while left <= right and s[left] == ' ': left += 1 # 去掉字符串末尾的空白字符 while left <= right and s[right] == ' ': right -= 1 # 将字符串间多余的空白字符去除 output = [] while left <= right: if s[left] != ' ': output.append(s[left]) elif output[-1] != ' ': output.append(s[left]) left += 1 return output def reverse(self, l: list, left: int, right: int) -> None: while left < right: l[left], l[right] = l[right], l[left] left, right = left + 1, right - 1 def reverse_each_word(self, l: list) -> None: n = len(l) start = end = 0 while start < n: # 循环至单词的末尾 while end < n and l[end] != ' ': end += 1 # 翻转单词 self.reverse(l, start, end - 1) # 更新start,去找下一个单词 start = end + 1 end += 1 def reverseWords(self, s: str) -> str: l = self.trim_spaces(s) # 翻转字符串 self.reverse(l, 0, len(l) - 1) # 翻转每个单词 self.reverse_each_word(l) return ''.join(l)
剑指Offer 58-II.左旋转1字符串
思路1:
1. 创建空res
2. 使用切片
3. 传入res
代码如下:
class Solution: def reverseLeftWords(self, s: str, n: int) -> str: return s[n:] + s[:n]
思路2:
列表遍历拼接
代码如下:
class Solution: def reverseLeftWords(self, s: str, n: int) -> str: res = [] for i in range(n, len(s)): res.append(s[i]) for i in range(n): res.append(s[i]) return ''.join(res)
思路3:
字符串遍历拼接
代码如下:
class Solution: def reverseLeftWords(self, s: str, n: int) -> str: res = "" for i in range(n, len(s)): res += s[i] for i in range(n): res += s[i] return res
列表用append,字符串用+。