剑指 Offer 05. 替换空格
在 Python 和 Java 等语言中，字符串都被设计成「不可变」的类型，即无法直接修改字符串的某一位字符，需要新建一个字符串实现。
方法一：遍历
class Solution:
def replaceSpace(self, s: str) -> str:
if not s : return ''
res = ''
star = 0
for i in range(len(s)):
if s[i] == ' ':
res = res + s[star:i] + '%20' # 字符串拼接 答案给的是判断 + res.append
star = i+1
res = res + s[star:]
return res对于c++中字符串可变，因此不需要新建字符；在原字符串中延长添加字符所需要的长度然后逆序替换即可.
class Solution {
public:
string replaceSpace(string s) {
int count = 0, len = s.size();
// 统计空格数量
for (char c : s) {
if (c == ' ') count++;
}
// 修改 s 长度
s.resize(len + 2 * count);
// 倒序遍历修改
for(int i = len - 1, j = s.size() - 1; i < j; i--, j--) {
if (s[i] != ' ')
s[j] = s[i];
else {
s[j - 2] = '%';
s[j - 1] = '2';
s[j] = '0';
j -= 2;
}
}
return s;
}
};
剑指 Offer 58 - II. 左旋转字符串
-
最简单当然使用python的字符串切片了，这里就不赘述了。
-
方法二：列表遍历拼接；先天添加n+1以后的字符在添加首位到第n位的字符
通过列表代替字符串，但会用到join方法
- 方法三：字符串遍历拼接
class Solution:
def reverseLeftWords(self, s: str, n: int) -> str:
res = ''
for i in range(len(s)):
if n+i < len(s):
res = res + s[n+i]
else:
res = res + s[n-len(s)+i] # 单纯画图找的规律；答案用的两个循环或是求余数可读性更高
return res或者是答案给的求余;可读性更高
class Solution:
def reverseLeftWords(self, s: str, n: int) -> str:
res = ""
for i in range(n, n + len(s)):
res += s[i % len(s)]
return res- 方法四：c++ 三次翻转
假设字符串x翻转后为$\bar{x}$,字符串s=ab，则ba为$\bar{\bar{a}\bar{b}}$
答案:
class Solution {
public:
string reverseLeftWords(string s, int n) {
reverseString(s, 0, n - 1);
reverseString(s, n, s.size() - 1);
reverseString(s, 0, s.size() - 1);
return s;
}
private:
void reverseString(string& s, int i, int j) {
while(i < j) swap(s[i++], s[j--]);
}
};
