解法:二分法,思路比较加简单
class Solution(object):
def reverseString(self, s):
"""
:type s: List[str]
:rtype: None Do not return anything, modify s in-place instead.
"""
if len(s) == 1: return s
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
解法:还是二分法的应用,比上一题稍微进阶一点。自己做的麻烦了。自己写的代码真是又臭又长。。
犯的错误:
- 字符串是不可变类型,不可直接修改,需要先转化为list类型
- 边界问题要思考清楚:right的初始化,以及在循环中如何更新left。如果right初始化为2k的话,看似合理,实际上如果数组中只有2k个元素,会index out of range,便不会进入循环,后续的判断也都不会符合条件,会导致原字符串没有被修改。因此初始化为2k-1。另外left每次进入循环更新为right+1,因为left到right已经是2k个元素了,进入下一个2k需要在right的基础上加一。
class Solution(object):
def reverseStr(self, s, k):
"""
:type s: str
:type k: int
:rtype: str
"""
s = list(s)
def reverse_str(t):
left, right = 0, len(t)-1
while left < right:
t[left], t[right] = t[right], t[left]
left += 1
right -=1
return t
left = 0
right = 2*k - 1
while right < len(s):
t = reverse_str(s[left:left+k])
s = s[0:left] + t + s[left+k:]
left = right + 1
right += 2*k
if len(s) - 1 - left + 1 < k:
s = s[:left] + reverse_str(s[left:])
if k <= len(s) - 1 - left + 1 < 2*k:
s = s[:left] + reverse_str(s[left:left+k]) + s[left+k:]
return ''.join(s)
第二种:在遍历字符串的过程中,只要让 i += (2 * k),i 每次移动 2 * k 就可以了,然后判断是否需要有反转的区间。而要找的也是每2k区间的起点。
#改进
class Solution(object):
def reverseStr(self, s, k):
"""
:type s: str
:type k: int
:rtype: str
"""
def reverse_str(t):
left, right = 0, len(t)-1
while left < right:
t[left], t[right] = t[right], t[left]
left += 1
right -=1
return t
s = list(s)
for i in range(0, len(s), 2*k):
s[i:i+k] = reverse_str(s[i:i+k])
return ''.join(s)
剑指 Offer 05. 替换空格
解法:python中比较骚的操作,分割后再拼接。
class Solution(object):
def replaceSpace(self, s):
"""
:type s: str
:rtype: str
"""
s = s.split(' ')
print(s)
return '%20'.join(s)
正经解法:首先扩充数组到每个空格替换成"%20"之后的大小。然后从后向前替换空格,也就是双指针法。
class Solution(object):
def replaceSpace(self, s):
"""
:type s: str
:rtype: str
"""
cnt = s.count(' ')
res = [' '] * (len(s) + cnt*2)
# res = list(s)
# res.extend([' '] * cnt * 2)
pointer1, pointer2 = len(s) - 1, len(res) - 1
while pointer1 >= 0:
if s[pointer1] == " ":
res[pointer2-2:pointer2+1] = '%20'
pointer2 -= 3
else:
res[pointer2] = s[pointer1]
pointer2 -= 1
pointer1 -= 1
return ''.join(res)
剑指 Offer 58 - II. 左旋转字符串
解法:python总有一些骚操作。。(切片)
class Solution(object):
def reverseLeftWords(self, s, n):
"""
:type s: str
:type n: int
:rtype: str
"""
return s[n:] + s[:n]
解法:局部反转+整体反转
class Solution(object):
def reverseLeftWords(self, s, n):
"""
:type s: str
:type n: int
:rtype: str
"""
s = list(s)
s[0:n] = list(reversed(s[0:n]))
s[n:] = list(reversed(s[n:]))
s.reverse()
return "".join(s)
解法:取模
class Solution(object):
def reverseLeftWords(self, s, n):
"""
:type s: str
:type n: int
:rtype: str
"""
new_str = ''
for i in range(len(s)):
j = (i + n) % len(s)
new_str += s[j]
return new_str
151. 反转字符串中的单词
class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
def strip_space(t):
n = len(t) - 1
left, right = 0, n
# 去除两边空格
# t.strip()
while left <= right and t[right] == ' ':
right -= 1
while left <= right and t[left] == ' ':
left += 1
tmp = []
# 去除单词之间多余的空格
while left <= right:
if t[left] != ' ':
tmp.append(t[left])
elif t[left] == ' ' and tmp[-1] != ' ':
tmp.append(t[left])
left += 1
return tmp
def reverse_string(nums, left, right):
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
def reverse_word(t):
start, end = 0, 0
n = len(t)
while start < n:
while end < n and t[end] != ' ':
end += 1
reverse_string(t, start, end-1)
start = end + 1
end += 1
res = strip_space(list(s))
reverse_string(res, 0, len(res) - 1)
reverse_word(res)
return ''.join(res)