344.反转字符串
双指针法
时间复杂度为: O(n), 空间复杂度为: O(1)
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
return s
541. 反转字符串II
注意点: 使用切片处理掉边界的问题
方法一
class Solution:
def reverseStr(self, s: str, k: int) -> str:
def helper(s_list:list):
left, right = 0, len(s_list)-1
while left < right:
s_list[left], s_list[right] = s_list[right], s_list[left]
left += 1
right -= 1
return s_list
res_s = list(s)
for i in range(0, len(s), 2*k): # 每次 2k 的步距
res_s[i:i+k] = helper(res_s[i:i+k]) # 反转 k 或者小于k的列表
return "".join(res_s)
方法二
class Solution:
def reverseStr(self, s: str, k: int) -> str:
start = 0 # start 开始位置
while start < len(s):
rev_p = start + k # rev_p 需要反转的位置
s = s[:start] + s[start:rev_p][::-1] + s[rev_p:]
start += 2*k # 每次 2k 步距移动
return s
05.替换空格
class Solution:
def pathEncryption(self, path: str) -> str:
res = ""
for i in path:
if i == ".":
res += " "
else:
res += i
return res
151.翻转字符串里的单词
class Solution:
def reverseWords(self, s: str) -> str:
s_list = s.split() # split 不传参数获取非空格的元素
left, right = 0, len(s_list) - 1
while left < right:
s_list[left], s_list[right] = s_list[right], s_list[left]
left += 1
right -= 1
return " ".join(s_list)
58-II.左旋转字符串
1、使用切片
class Solution:
def dynamicPassword(self, password: str, target: int) -> str:
return password[target:] + password[:target]
2、使用自定义的reverse,以列表反转方式代替其他语言的原地字符串操作
class Solution:
def dynamicPassword(self, password: str, target: int) -> str:
password_l = list(password)
self.reverse(password_l, 0, target-1)
self.reverse(password_l, target, len(password_l)-1)
self.reverse(password_l, 0, len(password_l)-1)
return "".join(password_l)
def reverse(self, s_list, start, end):
while start < end:
s_list[start], s_list[end] = s_list[end], s_list[start]
start += 1
end -= 1