1.字符串

2.LeetCode 相关题目

2.1_344反转字符串

LeetCode题目链接

2.1.1算法描述

使用双指针翻转字符串

可以与翻转链表进行对比学习

2.1.2 Python 代码实现

class Solution:def reverseString(self, s: List[str]) -> None:"""Do not return anything, modify s in-place instead."""i = 0j = len(s)-1while i<=j:s[i],s[j] = s[j],s[i]i+=1j-=1

2.1.3 时空复杂度

时间复杂度：O(N)（O(N/2)）

空间复杂度：O(1)

2.2_541反转字符串2

LeetCode题目链接

2.2.1 算法概述

因为一次处理 2*k 个元素，这个窗口大小是固定的，每次让 i 的起始位置从 i *2 k 开始

然后在选择 i~i+k 个元素进行反转。

与此同时如果剩余的子串元素 > i+k 则正常翻转，如果 < i+k 则剩下的子串元素全部反转

2.2.2 代码实现

1.C++ 代码实现

class Solution {
public:void reverse(string &s,int left,int right){ // 这里传入引用，否则报错while(left<right){swap(s[left],s[right]);left++;right--;}}string reverseStr(string s, int k) {for(int i =0;i<s.size();i = i+2*k){ // i 指向每一次反转的起始位置// 剩余的字符 > k 个，则反转 k 个if(i+k<=s.size()){reverse(s,i,i+k-1);continue;}// 剩余的字符>k个，则剩下的全部反转reverse(s,i,s.size()-1);}return s;}
};

class Solution:def reverseStr(self, s: str, k: int) -> str:# 子字符串替换方法def reverse_substring(text):left,right = 0,len(text)-1while left<right:text[left],text[right] = text[right],text[left]left+=1right-=1return textres = list(s)for cur in range(0,len(s),2*k):# 在 python 中使用 list[0:999],如果 999 那最后返回到最后一个元素res[cur:cur+k] = reverse_substring(res[cur:cur+k])return ''.join(res)

2.2.3 时空复杂度

时间复杂度：O(N)

空间复杂度：O(1)

2.3_剑指Offer05.替换空格

LeetCode题目链接

2.3.1 算法描述

遇到空格之后将空格后的元素全部顺应向后移动，为 %20 留出空

不要忘记先将 list 的大小进行扩充，要不前面加了 %20 后会 index out of range

2.3.2 Python 代码实现

class Solution:def replaceSpace(self, s: str) -> str:s_list = list(s)counter = s.count(' ')s_list.extend(['']*2*counter) # 因为要移动 s_list 中元素的位置，所以重新对其计数for i in range(len(s_list)):if s_list[i] == ' ':s_list[i] = '%'s_list[i+3:] = s_list[i+1:]s_list[i:i+3] = '%20'return ''.join(s_list)

2.3.3 时空复杂度

时间复杂度：O(N)

空间复杂度：O(1)

2.3.4 扩展：extend 和 append 的区别

参考文档

append() 将括号内的元素当做一个元素添加到 list

extend() 将括号内的元素先拆分再添加

2.3_151翻转字符串里的单词

2.3.1算法描述

这里一共分为三步:

1.移除多余的空格(数组移除元素)

2.翻转整句话

3.翻转每个子字符串中的内容

2.3.2Python 代码实现

class Solution:#1.去除多余的空格def trim_spaces(self,s):     n=len(s)left=0right=n-1# 去除开头的空格while left<=right and s[left]==' ':       left+=1#去除结尾的空格while left<=right and s[right]==' ':        right-=1tmp=[]# 去除单词之间多余的空格while left<=right:                                    if s[left]!=' ': # 不是空格直接存入tmp.append(s[left])elif tmp[-1]!=' ':#如果当前单词是空格，但是它前面那个单词不是空格这个空格就可以保留tmp.append(s[left])left+=1return tmp#2.字母字母之间的翻转def reverse_string(self,nums,left,right):while left<right:nums[left], nums[right]=nums[right],nums[left]left+=1right-=1return None#3.单词与单词之间的翻转def reverse_each_word(self, nums):start=0end=0n=len(nums)while start<n:while end<n and nums[end]!=' ':end+=1self.reverse_string(nums,start,end-1)start=end+1end+=1return None#4.翻转整个字符串def reverseWords(self, s):l = self.trim_spaces(s) # 删除多余空格                      self.reverse_string( l,  0, len(l) - 1) # 单词之间的翻转self.reverse_each_word(l)  # 翻转单词内每一个字母return ''.join(l)

2.4_151翻转字符串里的单词

力扣题目链接

2.4.1 算法描述

这个题中包含多个对字符串的操作

1.移除多余的空格：27T

2.单词之间翻转：344+541

3.单词内部字母翻转:344+541

2.4.2 Python 代码实现

class Solution:# 1.去掉多余的单词def trim_space(self,s):n = len(s)left = 0right = n-1# 去掉开头结尾的空格while left<=right and s[left] == ' ':left+=1while left<=right and s[right]==' ':right-=1# 去掉中间的空格tmp = []while left<=right:if s[left]!=' ': # 当前位置不是空格直接添加tmp.append(s[left])elif tmp[-1]!=' ': # 当前位置是空格，但是它前面不是空格就没事tmp.append(s[left])left+=1return tmp# 2.翻转操作：单词与单词翻转+单词内字母翻转def reverse_string(self,tmp,left,right):while left<=right:tmp[left],tmp[right] = tmp[right],tmp[left]left+=1right-=1return None# 3.锁定一个单词+翻转单词内的每个字母def reverse_each_word(self,tmp):start = 0end = 0n = len(tmp)while start<n:while end<n and tmp[end]!=' ': # 每次将 start 固定，然后移动 end ,找到完整单词位置end+=1self.reverse_string(tmp,start,end-1)start = end+1end+=1# 4.翻转整个字符串数组def reverseWords(self, s: str) -> str:tmp = self.trim_space(s) # 去掉多余的空格self.reverse_string(tmp,0,len(tmp)-1) # 单词与单词之间的翻转self.reverse_each_word(tmp) # 单词定位+单词内部字母之间的翻转return ''.join(tmp)

2.4.3 时空复杂度

时间复杂度：O(N)

空间复杂度：O(N)

2.5_剑指Offer 58-2 左旋转字符串

2.5.1 算法描述

要想实现题的翻转要实现三步：

1.先将前 K 个字符串翻转

2.将后 K 个字符串翻转

3.整个字符串翻转

2.5.2 C++&Python 代码实现

class Solution {
public:string reverseLeftWords(string s, int n) {reverse(s.begin(),s.begin()+n);reverse(s.begin()+n,s.end());reverse(s.begin(),s.end());return s;}
};

易错点：

C++ 使用 while 循环会超时，只能用 reverse 方法进行翻转

class Solution:def reverseLeftWords(self, s: str, n: int) -> str:# 某个字字符串的翻转def reverse_sub(sub_s,left,right):while left<right:sub_s[left],sub_s[right] = sub_s[right],sub_s[left]left+=1right-=1s_list = list(s)end = len(s)-1reverse_sub(s_list,0,n-1)reverse_sub(s_list,n,end)reverse_sub(s_list,0,end)return ''.join(s_list)

2.5.3 时空复杂度

时间复杂度:O(N)

空间复杂度：O(N)

python 的 string 不可变，需要开辟同样大小空间的 list 来修改

2.6_28实现strStr()

2.6.1算法描述

LeetCode 题目链接

B站 KMP 算法讲解

我的笔记

1.创建前缀表

i：指向新添加的元素

le：指向需要判断的元素

① s[le] == s[i]

prefix[i] = le++;

②s[le]!=s[i]

a.if le>0:

​ le = prefix[le-1] ; // 继续判断前一个元素

b.le<=0：

​ prefix[i] = 0;

​ le = 0;

2.移动前缀表

将第一个值设为 -1。最后一个字母的 prefix 值会直接被抛弃

3.KMP 核心算法

i ：指向 haystack的指针

j：指向 patten 的指针

（1）字符正常不匹配时如何移动

a. prefix 的值不为 -1

​ 先看 prefix 的值，将patten 的 p 指向 prefix 的 index

b.prefix 的值为 -1

​ 将 -1 的虚拟位置移动到错误位置，即 patten 的 0 位置移动到 haystack 的后一个

（2）字符串完全匹配

i-j 就是匹配的位置。仅将 j 移动到最后一个元素 prefix 的下标，然后继续判断是否还有其余的字符串

4.为什么 KMP 算法可以这样移动

比如说 abaa 是 haystack ,abab 是 patten 。不断匹配发现 a-b 对应不上。按理来说 patten 指针应该回溯到 patten 的最初位置 a 再重头比较，但是公共前后缀的前面和后面是对称的，也可以理解为是等价的，判断结果也是等价的。所以 i 指针当前在第二个 b 和当前在第一个 b 的效果是等价的，所以可以将其移动到前面最长公共前后缀对应的位置。

2.6.2 C++ 代码实现

2.6.3 时空复杂度

时间复杂度：O(M) T 的长度

空间复杂度：O(N) P 的长度

2.7_459重复的子字符串

LeetCode题目链接

2.7.1 算法描述

这里需要判断另个东西：①是否有重复子字符串 ②如果有重复子字符串，那子字符串多长

上面的要求完全可以通过 KMP 的 prefix 数组实现，这个时候的 prefix 的计算是包含从头到尾每一个元素的（最后一个元素也一同被算上），下面数组长度为 len

①是否由重复子字符串构成

公式：len%(len-prefix[-1])==0 and prefix[-1]!=0 则代表可以被数组的子串整除

②重复的子字符串有多长

公式len-prefix[-1] 就可以算出长度

拿一个最简单的例子，其实任意一个例子都适用

abab 的 prefix ，len=4
a 0
ab 0
aba 1
abab 2
prefix = [0,0,1,2]

①判断是否由重复子字符串构成

4%(4-2)==0 由重复子字符串构成

②判断重复子字符串多长

4-2 = 2 重复子字符串长度为 2

2.7.2 C++ &Python 代码实现

1.C++ 代码实现

class Solution {
public:bool repeatedSubstringPattern(string s) {int le = 0;int i = 1;vector<int> prefix(s.size(),0);// 得到前缀表while(i<s.size()){if(s[i]==s[le]){le++;prefix[i] = le;i++;}else{if(le>0) le = prefix[le-1];else{prefix[i] = 0;i++;}}}// 计算重复子串的长度int n =s.size();if(prefix[n-1]==0) return false;else return n%(n-prefix[n-1])==0;}
};

2.Python 代码实现

class Solution:def repeatedSubstringPattern(self, s: str) -> bool:n = len(s)prefix = [0]*nprefix[0]=0le = 0i= 1while(i<n):if s[le]==s[i]: # 新添加的元素和 len 匹配le+=1prefix[i] = lei+=1else:if le>0:le = prefix[le-1] # len 指向上一个子串的最长公共前后缀的最后一个位置else:prefix[i] = 0i+=1# 判断是否由重复元素组成if n%(n-prefix[-1])==0 and prefix[-1]!=0:return Trueelse:return False

2.7.3 时空复杂度

时间复杂度：O(N)

空间复杂度：O(N)

3.扩展题型

3.1_5最长回文子串

3.1.1 算法描述–马拉车算法

1.对字符串进行扩展
因为回文子串字符个数为奇数和偶数时判断的方法不同，所以需要在中间插入 # 使得字符串编程奇数串
因为对于边界的判断比较特殊，所以给边界添加 dummy ，具体如下图所示：

2.如何求得最长回文串的初始位置

用 P 的 i 减去 P [i]，再除以 2 就是最长回文子串的初始位置

具体实现

3.1.2 C++ 代码实现

class Solution {
public:// 添加 # string addBoundaries(string& s){int len = s.size();if(len==0) return "";vector<char>sb;// 定义新的字符串,插入 # for(int i=0;i<s.size();i++){sb.push_back('#');sb.push_back(s[i]);}sb.push_back('#'); // 最后再插入一个 # return string(sb.begin(),sb.end());}// 第 i 个字符的最长回文长度int centerSpread(string& s,int center){int len = s.size();// 从中心开始扩展int i = center-1; int j = center+1; int step = 0;// 用于记录回文长度是多少// 核心代码；i，j 同时走while(i>=0&&j<len&&s[i]==s[j]){i--;j++;step++;}return step;}string longestPalindrome(string s) {int len = s.size();// 判断长度if(len<2) return s;  string newStr = addBoundaries(s);// 新串长度int newLen = 2*len+1; int maxLen = 1;int start = 0;// 判断字符串中每一个元素for(int i =0;i<newLen;i++){int curLen = centerSpread(newStr,i);// 求最大值if(curLen>maxLen){maxLen = curLen;start = (i-maxLen)/2;}}return s.substr(start,maxLen);}
};

3.1.3 时空复杂度

时间复杂度：O(N²)
空间复杂度O(N)

3.2_190. 颠倒二进制位

字符串+位运算

3.2.1 算法描述

这里和反转字符串的方法一样

Step1：分别有 left 和 right 两个指针

Step2: 判断 left 和 right 指向的位是 0 还是 1

Step3：将相应的位置进行设置 0 或者设置为 1

3.2.2 代码实现

class Solution {public:uint32_t reverseBits(uint32_t n) {// 字符串反转int left = 0;int right = 31;while(left<right){// 判断 left 是 0 还是 1 uint32_t leftVal = n&(1<<left); // 判断是1还是 0 uint32_t rightVal = n&(1<<right);// 交换if(leftVal) n = (n|(1<<right));else n = (n&~(1<<right));if(rightVal) n = (n|(1<<left));else n = (n&~(1<<left));left++;right--;}return n;}
};

3.2.3 时空复杂度

时间复杂度：O(logn)

空间复杂度：O(1)

3.2.4 知识扩展：位运算

位运算

1.为什么使用位运算

使用位进行存储可以更加节省空间

2.有哪些位运算

3.相关操作

（1）二进制与十进制的转换（手写）

（2）查看 x 第 n 位是否为 1

x & (1<<n)

（3）将第 n 位设置为 1

x|(1<<n)

（4）将第 n 位设置为 0

x&~(1<<n)

（4）移位操作

3.3_7 整数反转

3.3.1 算法描述

整数反转和字符串反转不太一样，整数反转不需要两个指针，而是通过不断的向前 * 10 的方法将后面的数向前推

2.递归实现

以 321 为例

（1）递归顺序

我选择的是用后序遍历，后序遍历代表需要先处理 3 。因为这里有一个关键点为数字 1 需要乘几个 10 ，所以必须要先将 3 提取出来放在最后一位。

（2）参数及返回值

这里需要传入的参数是 step ，也就是递归了多少步，需要乘几个 10 ，使用全局变量的形式让 step 不断的叠加

当处理 1 时 1 需要得到 23 的值，所以需要不断的将后面处理的值向上 return

（3）结束条件

当只剩下一个个位数时就直接相加即可

（4）单层递归逻辑

如何得到最后一位 % 10

如何去掉最后一位 /10

如何判断是否越界：

这里判断越界时需要将 INT_MAX 和 INT_MIN 分别进行 /10 的操作，否则会报错

3.3.2 代码实现

1.非递归实现

class Solution {public:int reverse(int x) {int res = 0; // 用于存放最后的结果while(x!=0){if(res<INT_MIN/10||res>INT_MAX/10) return 0;int digit = x%10; // 得到最后一位x/=10; // 下面需要切分的值res = res*10+digit;}return res;}
};

2.递归实现

递归实现没有办法判断 int 类型的范围

class Solution {private:int step = 1;public:// 进行符号标记int base(int x){if(x<10) return x;int sums = reverse(x/10); // 先得到 1 // 将 x 的每一位逐渐分离出来int cur = x%10; // 先将 3 进行分离step*=10; // 进行了一次操作// 反转后的范围进行判断if(sums>INT_MAX) return 0;else return sums+cur*step;}int reverse(int x) {int sums = 0;if(x>=0) sums = base(x);else sums = base(-1*x)*-1;return sums;}
};

3.3.3 时空复杂度

时间复杂度：O(N)

时间复杂度：O(log |x|)。翻转的次数即 xx 十进制的位数。

空间复杂度：O(1)

3.4_8字符串转换整数 (atoi)

3.4.1_算法描述

这个题有几个关键点：

1.去掉前导空格

这个算法因为不需要对 s 进行改变所以直接将指针指向非空格部分就行

2.对于 int 范围的判断

3.4.2 代码实现

class Solution {public:int myAtoi(string s) {int len = s.size();// 去除前面的空格int j = 0;while(j<len){if(s[j]!=' ') break; // 最后 j 指向第一个非空格字符j++;}// 字符串中没有数字if(j==len) return 0;int sign = 1; // 判断符号if(s[j]=='+') j++;else if(s[j]=='-'){sign = -1;j++;}int res = 0;// 开始判断数字while(j<len){char cur = s[j];if(cur<'0'||cur>'9') break;if(res>INT_MAX/10||(res==INT_MAX/10&&(cur-'0')>INT_MAX%10)) return INT_MAX;if(res<INT_MIN/10||(res==INT_MIN/10&&(cur-'0')>-(INT_MIN%10))) return INT_MIN;res=res*10+sign*(cur-'0');j++;}return res;}
};