LeetCode字符串
LeetCode字符串刷题记录
基础知识
字符串和数组很相似
- 每个元素的数据类型相同
- 都可以通过下标索引访问
字符串比大小
从第0个位置开始，依次比较对应位置上的字符编码大小
def compare(str1, str2):
i = 0
j = 0
while i < len(str1) and j< len(str2):
if ord(str1[i]) == ord(str2[j]):
index1 += 1
index2 += 1
elif ord(str1[i]) < ord(str2[j]):
return -1
else:
return 1
if len(str1) < len(str2):
return -1
elif len(str1) > len(str2):
return 1
else:
return 0
存储结构
字符串分为顺序存储结构和链式存储结构
- 顺序：连续的地址里一次存储各个字符，每个字符所占的存储空间相同
- 链式：用链表结构存储，每个节点的数据域可以存储不同大小的数据
反转字符串
class Solution:
def reverseString(self, s: List[str]) -> None:
left = 0
right = len(s)-1
while right > left:
s[right],s[left] = s[left], s[right]
right -= 1
left += 1
进阶：反转 2 k 2k 2k个字符中的前 k k k个，如果剩余字符少于 k k k个，则反转所有剩余字符，如果剩余字符大于等于 k k k个，反转前 k k k个
class Solution:
def reverseStr(self, s: str, k: int) -> str:
lit = list(s)
for i in range(0, len(s), 2*k):
left = i
right = i + k - 1
while right < len(s) and left < right:
lit[left],lit[right] = lit[right], lit[left]
left += 1
right -= 1
if i + k > len(s):
left = i
right = len(s) - 1
while left < right:
lit[left],lit[right] = lit[right], lit[left]
left += 1
right -= 1
return ''.join(lit)
注意
- 如果剩余字符大于等于
k
k
k个，反转前
k
k
k个 着条逻辑我已经在
for循环内部的while循环解决了 - 外部的
if i + k > len(s):是在判断剩余字符是否少于k个 - 过于复杂，其实如果利用python的切片特性，根本不需要单独判断是最后剩余字符的数目，因为如果
s[start:end]end超出索引范围，则返回到字符串末尾
class Solution:
def reverseStr(self, s: str, k: int) -> str:
lit = list(s)
for i in range(0, len(s), 2*k):
lit[i:i + k] = lit[i:i + k][::-1]
return ''.join(lit)
替换数字
lit = list(input())
for i in range(len(lit)):
if lit[i] >= '0' and lit[i] <= '9':
lit[i] = 'number'
print(''.join(lit))
python不能直接更改字符串的值，所以必须要开辟新空间，但是如果是用c++，可以尝试在原数组基础上更改，但个人感觉没带来太大的效益，算法的时间复杂度虽然还是同一等级，但是确实运行时要长一些
#include <iostream>
using namespace std;
int main() {
string s;
while (cin >> s) {
int sOldIndex = s.size() - 1;
int count = 0;
// 统计数字字符的个数
for (int i = 0; i < s.size(); i++) {
if (s[i] >= '0' && s[i] <= '9') {
count++;
}
}
// 扩充字符串s的大小，每个数字替换为"number"（6个字符）
s.resize(s.size() + count * 5); // 因为 "number" 比单个数字多 5 个字符
int sNewIndex = s.size() - 1;
// 从后往前将数字替换为"number"
while (sOldIndex >= 0) {
if (s[sOldIndex] >= '0' && s[sOldIndex] <= '9') {
s[sNewIndex--] = 'r';
s[sNewIndex--] = 'e';
s[sNewIndex--] = 'b';
s[sNewIndex--] = 'm';
s[sNewIndex--] = 'u';
s[sNewIndex--] = 'n';
} else {
s[sNewIndex--] = s[sOldIndex];
}
sOldIndex--;
}
cout << s << endl;
}
return 0;
}