任务
344. 反转字符串
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
思路
这道题比较简单,只需用双指针法交换头尾的值,然后往中间缩进即可。注意的是这里python给提供的函数时字符列表,因为字符串本身是不可变对象,无法修改其中的元素。
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
size = len(s)
for i in range (0,size//2):
tmp = s[i]
s[i] = s[size-1-i]
s[size-1-i] = tmp
541. 反转字符串 II
思路
模拟题,按照2k的步数遍历,如果还剩多于k个数,则反转k个。少于k个,则反转最后的剩余的数字。注意找的是每2k区间的起点,所以可以不需要计数器和逻辑代码处理,那样反而复杂了,只需在循环的步数上做文章。注意这里给出了在[start,end)中反转的方法,也优化了上一题的思路。
class Solution:
def reverse(self,lst,start,end):
while end-start >1: #至少两个数
lst[start],lst[end-1] = lst[end-1],lst[start]
start+=1
end-=1
def reverseStr(self, s: str, k: int) -> str:
size = len(s)
lst = list(s)
for i in range(0,size,2*k):
if i+k <= size:
self.reverse(lst,i,i+k)
else:
self.reverse(lst,i,size)
s = ''.join(lst)
return s
特别地,利用python切片的便利性,有个更巧妙的方法比较难想到,可以不停地更新s,达到“就地”更改的作用。注意实际不是就地,而是每次循环中,你都是创建一个新的字符串,而这个新字符串是在原有字符串基础上进行拼接和反转得到的。尽管 Python 字符串不可变,每次的修改都生成了新的字符串,这种方式通过不断地构建和替换,达到了预期的效果。
class Solution:
def reverseStr(self, s: str, k: int) -> str:
p = 0
while p < len(s):
p2 = p + k
s = s[:p] + s[p:p2][::-1]+s[p2:] #[0,p)保持,[p,p2)反转,[p2,size)保持
p = p + 2* k
return s
kama 54.替换数字(第八期模拟笔试)
思路
如果是用py,这题很简单,就是将字符串转为字符串list后,将对应位置的值修改为'number',再转为字符串即可,就不需要考虑修改后大小变化的问题了。
class Solution:
def changeNumber(self, s):
lst = list(s)
size = len(lst)
for i in range(size):
if lst[i].isdigit():
lst[i]='number'
return ''.join(lst)
心得体会
通过做字符串的题目,更加认识到了循环条件的思考方式,对于左闭右开区间,有两种思路
- 一种是类似C++迭代器那种,iter < end,表达是右界桩,因此在循环中最多到达end的前一个。
- 另一种是考虑区间包含的元素数量,[start,end) 包含的数量为end-start个元素,因此判断循环至少需要几个元素,如541中反转区间字符串函数,while循环的循环条件就是区间内至少包含2个元素,因此条件为 end-start>1或者 end-start>=2
另外,学习了py中可变对象,不可变对象,浅拷贝深拷贝与切片的关系。特别地,将切片赋值给变量和直接用切片赋值有不同的效果和行为,如果是赋值给变量,得到的变量是对原列表指定范围的浅拷贝,当修改切片中的可变对象时,会影响到原列表。而替换时不会影响到。对于直接用切片赋值,可以达到修改原列表内容的效果。
# 切片赋值给变量,再去修改的情况(浅拷贝)
lst = [0,1,2,3,4,5,6]
sliced = lst[1:3]
sliced[1] = 100
print(lst) # 输出:[0, 1, 2, 3, 4, 5, 6] 元素为不可变变量直接无法修改(不可变对象的浅拷贝没有意义)
lst = [[1, 2], [3, 4], [5, 6]]
sliced = lst[1:3]
# 修改切片中的第一个子列表的元素
sliced[0][0] = 10
sliced[1]=[1,2,3,4] #此时已经修改了引用,后续的处理都不会影响到lst[2]了,只有不修改引用时,修改内容如修改slice[1][0]或者slice[1].append等可以修改lst[2]
print(lst) # 输出:[[1, 2], [10, 4], [5, 6]] #元素为可变变量,只能修改其内容,不能替换
print(sliced) # 输出:[[10, 4], [1,2,3,4]]]
# 切片直接修改的情况
original_list = [1, 2, 3, 4]
original_list[1:3] = [10, 20]
print(original_list) # 输出:[1, 10, 20, 4]
标签:end,Day8,start,修改,part1,lst,字符串,size
From: https://www.cnblogs.com/haohaoscnblogs/p/18320677