代码随想录算法训练营 Day 7
Published:
Q1. LeetCode 344
思路:因为不能使用额外空间,所以采用双指针的方法,初始值分别为0和len(s) - 1。那么每次只需要交换指针所指字符即可
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
left = 0
right = len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
复杂度分析
时间复杂度:O($n$) 空间复杂度:O(1)
Q2. LeetCode 541
思路:首先将字符串以2k的长度进行划分,在每个区间中取前k个进行翻转
class Solution:
def reverseStr(self, s: str, k: int) -> str:
start_idx = 0
while start_idx < len(s):
end_idx = start_idx + k
s = s[:start_idx] + s[start_idx:end_idx][::-1] + s[end_idx:]
start_idx = start_idx + 2 * k
return s
复杂度分析
时间复杂度:O($n$) 空间复杂度:O(1)
Q3. KamaCoder 54
思路:判断字符是否为数字,如果是,则替换为number。否则采用原字符
def replace_num(s):
r = ''
for i in range(len(s)):
if ord('0') <= ord(s[i]) <= ord('9'):
r += 'number'
else:
r += s[i]
return r
data = input()
res = replace_num(data)
print(res)
复杂度分析
时间复杂度:O($n$) 空间复杂度:O($n$)
Take some notes
Python里面的string也是不可改的,所以也是需要额外空间的。空间复杂度:O(n)
