LeetCode344 反转字符串
题目链接/文章讲解/视频讲解:https://programmercarl.com/0344.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html
✌思路:双指针,i指开头,j指结尾,交换,i往右移,j往左移,直到j≤i
class Solution(object):
def reverseString(self, s):
"""
:type s: List[str]
:rtype: None Do not return anything, modify s in-place instead.
"""
j = len(s) - 1
i = 0
while j > i:
tmp = s[i]
s[i] = s[j]
s[j] = tmp
i += 1
j -= 1
return s
LeetCode541 反转字符串II
题目链接/文章讲解/视频讲解:https://programmercarl.com/0541.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2II.html
✌思路:按照题目意思分类讨论,剩余字符少于k个和其他情况
class Solution(object):
def reverseStr(self, s, k):
"""
:type s: str
:type k: int
:rtype: str
"""
s = list(s)
for i in range(0, len(s), 2 * k):
rest = len(s) - i
if rest < k: # 剩余字符少于 k 个
j = len(s) - 1
while i < j:
s[i], s[j] = s[j], s[i]
i += 1
j -= 1
break
# 剩余字符>=k个
j = i + k - 1
while i < j:
s[i], s[j] = s[j], s[i]
i += 1
j -= 1
return ''.join(s) # list转string
优化版本:
-
使用range(start, end, step)来确定需要调换的初始位置
-
对于字符串s = ‘abc’,如果使用s[0:999] ===> ‘abc’。字符串末尾如果超过最大长度,则会返回至字符串最后一个值,这个特性可以避免一些边界条件的处理。
-
用切片整体替换,而不是一个个替换.
class Solution:
def reverseStr(self, s: str, k: int) -> str:
def reverse_substring(text):
left, right = 0, len(text) - 1
while left < right:
text[left], text[right] = text[right], text[left]
left += 1
right -= 1
return text
res = list(s)
for cur in range(0, len(s), 2 * k):
res[cur: cur + k] = reverse_substring(res[cur: cur + k])
return ''.join(res)
卡码网:54.替换数字
题目链接/文章讲解:https://programmercarl.com/kama54.%E6%9B%BF%E6%8D%A2%E6%95%B0%E5%AD%97.html
✌思路:isdigit()判断字符串是否是数字
s = list(input())
for i in range(len(s)):
if s[i].isdigit():
s[i] = 'number'
print( ''.join(s))
其他判断是否是数字的方法:
str1 = input()
ans = ""
for ss in str1:
if ord("0") <= ord(ss) <= ord("9"):
ans += "number"
else:
ans += ss
print(ans)
极致做法:从后向前替换
首先扩充数组到每个数字字符替换成 “number” 之后的大小。
例如 字符串 “a5b” 的长度为3,那么 将 数字字符变成字符串 “number” 之后的字符串为 “anumberb” 长度为 8。
如图:
然后从后向前替换数字字符,也就是双指针法,过程如下:i指向新长度的末尾,j指向旧长度的末尾。
LeetCode151 翻转字符串里的单词
题目链接/文章讲解/视频讲解:https://programmercarl.com/0151.%E7%BF%BB%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%87%8C%E7%9A%84%E5%8D%95%E8%AF%8D.html
✌思路:没用库函数,写的比较复杂,先处理空格再合并单词再反转
class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
s = list(s)
# 先处理空格
i = 0
while i < len(s):
if s[i] == " ":
if i == 0: # 删除所有前导空格
s.pop(i) # pop根据索引删除List中的元素,删除后循环条件中的len(s)会变化
continue
j = i + 1
while j < len(s) and s[j] == " ": # 多个空格
s.pop(j)
if j >= len(s): # 说明i是尾随空格
s.pop(i)
break
i += 1
# 合并单词
res = []
i = 0
while i < len(s):
j = i + 1
word = "" + s[i]
while j < len(s) and s[j] != " ":
word += s[j]
j += 1
res.append(word)
i = j + 1
# 反转
i = 0
j = len(res) - 1
while i < j:
res[i], res[j] = res[j], res[i]
i += 1
j -= 1
return " ".join(res)
库函数:
s = s.strip() # 去除前后空白
s = s.split() # 根据空格划分
s = s[::-1] # 反转整个字符串
不需要额外空间的解题思路:使用整体反转+局部反转就可以实现反转单词顺序的目的
- 移除多余空格
- 将整个字符串反转
- 将每个单词反转
举个例子,源字符串为:”the sky is blue “
- 移除多余空格 : “the sky is blue”
- 字符串反转:”eulb si yks eht”
- 单词反转:”blue is sky the”
class Solution:
def reverseWords(self, s: str) -> str:
# 删除前后空白
s = s.strip()
# 反转整个字符串
s = s[::-1]
# 将字符串拆分为单词,并反转每个单词
s = ' '.join(word[::-1] for word in s.split())
return s
卡码网:55.右旋转字符串
题目链接/文章讲解:
https://programmercarl.com/kama55.%E5%8F%B3%E6%97%8B%E5%AD%97%E7%AC%A6%E4%B8%B2.htmlhttps://programmercarl.com/0151.翻转字符串里的单词.html)
✌思路:利用python的切片
num = int(input())
string = input()
res = string[len(string)-num:] + string[:len(string)-num]
print (res)
进阶:不能申请额外空间,只能在本串上操作
需要将字符串右移n位,字符串相当于分成了两个部分,如果n为2,符串相当于分成了两个部分。右移n位,就是将第二段放在前面,第一段放在后面,先不考虑里面字符的顺序,是不是整体倒叙就行了。如图:
此时第一段和第二段的顺序是我们想要的,但里面的字符位置被我们倒叙,那么此时我们在把 第一段和第二段里面的字符再倒叙一把,这样字符顺序不就正确了。 如图:
其实,思路就是 通过 整体倒叙,把两段子串顺序颠倒,两个段子串里的的字符在倒叙一把,负负得正,这样就不影响子串里面字符的顺序了。
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
int n;
string s;
cin >> n;
cin >> s;
int len = s.size(); //获取长度
reverse(s.begin(), s.end()); // 整体反转
reverse(s.begin(), s.begin() + n); // 先反转前一段,长度n
reverse(s.begin() + n, s.end()); // 再反转后一段
cout << s << endl;
}