前言

本文记录我学习双指针的一些笔记。

原理

双指针并不是一个具体的具体的算法，而是一种思路，是相对于两次遍历而言的。通常可以把两重 for 循环优化到一次遍历。

双指针的范围非常的广，通常在链表，数组，字符串中使用比较广泛。

双指针本质上还是一个搜索算法，相对于穷举，很多优化都是剪枝，压缩搜索空间。二分、滑动窗口就是很典型的双指针，它们基本都是通过一些技巧进行剪枝从而达到优化的目的的。

根据指针的移动步长，移动方式，对应的时间复杂度也不同，如果步长是 2，或者像二分那样对撞并且跳着移动，就是 $O(lo{g}^n)$，常规的移动方式则是 O（n），而空间复杂度是 O（1）。

由于双指针的空间复杂度为 $O(1)$，因此在一些原地算法中，双指针就比较常见。

分析

1. 快、慢指针指向什么？
2. 双指针移动方向是什么？
3. 起始位置是什么？
4. 什么时候移动指针？
5. 怎么移动指针？

心得：
很多时候我们刷题容易陷入这种情况：不知道为什么出了错，一个测试过不了，
就单步或者手动模拟这个测试的执行过程，但是总是有测试出了问题，根据测试数据修改代码，修修改改的，
即使最后 ac l，也感觉自己好像并没有学到些什么，下一次遇到还是不会，总感觉是硬凑出来的。

我就经常遇到这种情况。

根据我的经验：这是因为自己对这个题理解不够深，没有从合适的角度去分析和理解这个题，要知道
刷题是需要动脑子的，上面那种一直单步调试似乎很努力，但是一点作用都没有，因为我们的大脑根本
没有动起来。

这是正常的，大脑本来就会主动去寻找消耗低的路径。

那么要怎么改善呢？
其实很简单，就是样对一个题型养成思维定势，然后固定几个问题，拿到问题就先从这些角度分析，而不是
动手就写代码。

这是我刷滑动窗口的经验，每拿到一个题我就会问滑动窗口的一些要点，比如这题窗口内的状态是什么？
什么时候扩展？什么时候收缩？窗口是固定大小的吗？就这样一步一步的细化题目，之后分析清楚后，
再开始刷题。

而最近刷二分我又陷入那种低效率的方式，反思一下发现自己并没有养成思维定势那样去分析，甚至
有些题动手就刷，有种为了 ac 而 ac 的怠卷期了。这时如果比较累了，建议先休息一下，比较刷题
动脑是非常重的。

分类

根据指针移动方向是否相同

移动的方式：跳跃还是移动，两者相同还是不同，每次一样还是不同等等。

快慢指针：不定长滑动窗口，链表反转，环，倒数第 k 个

对撞指针（左右指针）：反转，数组和，有序，二分

固定间隔指针：固定滑动窗口

• 快慢指针（前后按不同步调的两个指针），快指针在前，慢指针在后，利用两者间的距离解决问题
• 前后双端指针（一个在首，一个在尾部，向中间靠拢），用来界定范围，或者两个碰撞点
• 固定间隔的指针（以 i, i + k 的间距的两个指针）

模板

快慢指针

// 1.快慢指针
l = 
r = 
while 没有遍历完
  if 一定条件
    l += 
  r += 
return 合适的值

对撞指针

//2. 左右端点指针
l = 0
r = n - 1
while l < r
  if 找到了
    return 找到的值
  if 一定条件
    l += 
  else if  一定条件
    r -= 
return 没找到

固定间隔指针

//3. 固定间距指针
l = 0
r = k
while 没有遍历完
  自定义逻辑
  l += 
  r += 
return 合适的值

题型

固定间隔的指针

• list

  **876. 链表的中间结点**难度简单436

  **剑指 Offer 22. 链表中倒数第 k 个节点**难度简单293

快慢指针

• list

  141. 环形链表

  392. 判断子序列

  题意

  判断一个字符串是否是另一个字符串的子序列

  分析

  子序列就是不连续的子串，但是这题字符要顺序相同，如 abc 就是 sssagsbasc 的子序列。

  那我们开两个指针，分别指向两字符串的当前字符，然后遍历判断即可。

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      bool isSubsequence(string s, string t) {
          int i=0;
          int j=0;
  
          for (;j<t.size();j++){
              if (s[i]==t[j]){
                  i++;
              }
              if (i==s.size()){
                  break;
              }
          }
          
          return i==s.size() || j != t.size();
      }
  };

  58. 最后一个单词的长度

  题意

  求最后一个字符的长度

  分析

  开两个指针，从后往前遍历，找到单词边界即可。

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      int lengthOfLastWord(string s) {
          int l=0;
          int r=s.size()-1;
  
          while(r>=0 && s[r]==' '){
              r--;
          }
          l=r;
          while(l>=0 && s[l]!=' '){
              l--;
          }
  
          return r-l;
      }
  };

  面试题 01.06. 字符串压缩

  题意

  将连续字符变成字符+出现次数

  分析

  要将字符变成连续字符，那么需要找到连续字符的次数，故开快慢指针，快指针扫描计算次数，慢指针为字符，统计结束后转换为字符+数字即可。

  优化

  本题需要注意几个坑：

  1. 由于字符出现次数可能操作 9，故不能直接 '1'+出现次数转换为出现次数的字符，因为可能不只一个字符，故需要直接将 int 转换为 string
  2. 生成结果字符串时，使用 res=res+a 会超时+内存溢出，而使用 += 则不会，这是因为 += 相当于 append，直接在原字符串后增加字符，而 = + 则是新开内存

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      string compressString(string s) {
          if (s.empty()){
              return s;
          }
          string res;
          int l=0;
          int r=0;
          
          while(r<s.size()-1) {
              if (s[r]==s[r+1]) {
                  r++;
                  continue;
              }
              res+=s[l];            
              res+=to_string(r-l+1); 
              r++;
              l=r;
          }
          res+=s[l];
          res+=to_string(r-l+1);
  
          return res.size()<s.size()?res:s;
      }
  };

  844. 比较含退格的字符串

  题意

  比较去除退格字符后的字符是否相等

  分析

  由于退格字符时，前面的字符可能会被删掉，所以不能从前往后看，故开双指针，从后往前扫描。

  基本思想也很简单：

  从后往前扫描，分别找到第一个非退格字符即可，如果是退格字符，则需要记录一下个数，然后跳过相应个数的普通字符，之后在比较即可。

  上面是基本扫描一遍，问题在于，可能只有一个字符被扫描结束了，而另一字符可能没有扫描完，故还要继续判断。由于这个字符串已经扫描完，故如果要对比成功，那么另一个字符串余下的字符必然全部会被退格清掉。

  则有下面这些情况：

  1. 如果两者都扫描完了，则成功
  2. 如果 i 没有扫描完，且第一个字符不是退格字符，前面也没有积累退格字符，那么就必然不可能对比成功，故返回失败
  3. 同理 j 没有扫描完且第一个不是退格字符
  4. 如果 i 没有扫描完，就扫描判断，如果最后退格字符大于等于 0，说明普通字符被清空了，则对比成功
  5. 同理 j

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      bool backspaceCompare(string s, string t) {
          int i=s.size()-1;
          int j=t.size()-1;
          bool iFast=false;
          int cnti=0;
          int cntj=0;
  
          while(i>-1&&j>-1){
              if (s[i]=='#'){
                  i--;
                  cnti++;
                  continue;
              }
              if (cnti>0){
                  i--;
                  cnti--;
                  continue;
              }
              if (t[j]=='#'){
                  j--;
                  cntj++;
                  continue;
              }
              if (cntj>0){
                  j--;
                  cntj--;
                  continue;
              }
              if (s[i]!=t[j]){
                  return false;
              }
              i--;
              j--;
          }
  
  				// 如果两者都扫描完了，则成功
          if (i==-1 && j==-1){
              return true;
          }
  
  				// 第一个字符不是退格字符，前面也没有积累退格字符
          if ((j==-1) && (cnti==0) && (s[i]!='#')){
              return false;
          }
          if ((i==-1) && (cntj==0) && (t[j]!='#')){
              return false;
          }
  
          if (i==-1){
              iFast=true;
          }
  
          while(i>-1){
              if (s[i]=='#'){                
                  cnti++;
              }else {
                  cnti--;
              }
              i--;
          }
          while(j>-1){
              if (t[j]=='#'){
                  cntj++;
              } else {
                  cntj--;
              }
              j--;            
          }
  
  				// 如果最后退格字符大于等于 0，说明普通字符被清空了
          if (iFast){
              return cntj>=0;
          } else {
              return cnti>=0;
          }
      }
  };

  696. 计数二进制子串

  题意

  求连续 0 和 1 数量相等的子串

  分析

  要求 0 和 1 数量相等的子串，那么假设子串是由 n 个 0 和 m 个 1 组成的，即 0001111 或 111110000 等，那么显然，满足条件的子串长度等于 min(n,m).

  换一句话说，我们只要知道相邻 0 和 1 个数的较小值，就是最长的子串长度。如是 000111，那么这个字符串中满足条件的子串有 01，0011，000111，即长度的一半，也就是相邻 0 和 1 个数的较小值。

  那么我们只需要计算出相邻 0，1 的个数，再计算相邻两者的较小值之和即可。如 00110001 ，个数数组就是 2231，值就为 min(2,2)+min(2,3)+min(3,1).

  故我们预先计算出该数组，再遍历一次即可。

  优化

  根据上面的分析，我们知道其实某一时刻计算时，我们只需要知道相邻两数的个数即可，而和其它个数无关，那么我们可以用快慢指针来维护这两个值。快指针是当前种类的个数，慢指针是前一个种类的个数，然后遍历即可。

  效率

  时间复杂度：$O(n)$

  空间复杂度：优化前 $O(n)$，优化后 $O(1)$

  代码

  class Solution {
  public:
      int countBinarySubstrings(string s) {
          vector<int> nums;
          int cnt;
          int res=0;
          
          for (int i=0;i<s.size();i++){
              cnt=1;
              
              while (s[i]==s[i+1]) {
                  cnt++;
                  i++;
              }
              nums.push_back(cnt);
          }
          
          for (int i=0;i<nums.size()-1;i++) {
              res+=(min(nums[i],nums[i+1]));
          }
          
          return res;
      }
  };

  class Solution {
  public:
      int countBinarySubstrings(string s) {
          int cur=0;
          int pre=0;
          int cnt=0;
          int res=0;
          
          for (int i=0;i<s.size();i++){
              cnt=1;
              
              while (s[i]==s[i+1]) {
                  cnt++;
                  i++;
              }
              pre=cur;
              cur=cnt; 
              res+=(min(cur,pre));
          }
          
          return res;
      }
  };

  88. 合并两个有序数组

  题意

  合并两个有序数组

  分析

  由于最后的结果数组在 nums1 中，故可能会涉及到 nums1 中数组的移动，如果从前后往后遍历的话，就会出现移动的情况，因此开双指针从后往前移动，一个开始指向 m-1,一个指向 n-1，再开一个指向 nums1 中当前应该存放的位置，那么每次把双指针中大的一个放到指定位置中即可。

  最后，可能 nums2 数组并没有遍历完，因为里面的元素可能比 nums1[0] 的元素还要小，故最后再遍历余下的 nums2 数组，存放到指定位置即可。

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
          int i=m-1;
          int j=n-1;
          int k=nums1.size()-1;    
                  
          while(i>-1 && j>-1){
              if (nums1[i]>nums2[j]){
                  nums1[k]=nums1[i];
                  i--;
              } else {
                  nums1[k]=nums2[j];
                  j--;
              }
              k--;
          }
          
          while(j!=-1){
              nums1[k]=nums2[j];
              k--;
              j--;
          }
      }
  };

  31. 下一个排列

  题意

  将 nums 中的数全排列，问当前排序的下一个排序是什么

  分析

  首先，我们要知道什么是字典序全排序：对于数字来说，字典序全排序就是从小到大的数字。

  如 1，2，3，4 组成的全排列就是

  1234
  1243
  1324
  1342
  ...

  我们要找任意一个数的下一个排列，自然需要知道两个排列之间的关系。

  先说结论，那就是对于相邻的两排列，我们一定能找到某个分界点，使得小的排列分界点右边是最大值，而新的排列分界点右边是最小值。

  无效的图片地址

  如排列 5,1,4,3,2 和 5,2,1,3,4

  无效的图片地址

  我们能找到分割点 i，使得数 a 的右边是数字 4，3，2 组成的最大值 432，而 b 的右边是组成的最小值 1，2，3.

  知道这个性质之后，这个题就很简单了。其实这个性质也很好理解，就是类似于数字进位，进位前低位必然是最大值，进位后低位自然是最小值。而分割点就是进的位。

  首先，显然我们需要找到这个分界点，对于数 a 来说，分界点 i 右边的数显然是单调递减的，所以我们从右边开始遍历，找到第一个非递增的元素即可，即数 1。数 1 要进位的话，自然是进到刚刚比 1 大的数。

  故我们要在分割点右边，即 1 的右边三个数 1，3，4 中，找到第一个比分割点 1 大的数。而这就是一个在递减数组中找第一个大于的数，是个典型的二分操作。

  找到数后，在这是 2，然后和分割点那个数交换，即进位。

  无效的图片地址

  无效的图片地址

  交换后，我们再把分割点右边的数变成组合的最小值，在这就是 134.最简单的 sort 递增排列一下即可。不过注意观察，我们知道原先右边的数是递递减的，交换分割点后，其实仍没有改变递减的顺序。所以要变成最小值，即递增的，之间反转 reverse 下即可。

  所以总结一下，算法步骤就是：

  1. 从右向左找到第一个递减的元素
  2. 在右边二分该元素，找到第一个大于它的元素
  3. 交换两元素的值
  4. 反转右部

  需要注意的是，就是原先数组完全递增，是排列的最大值了。就找不到递减的元素，所以要判断一下，直接反转即可。

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      void nextPermutation(vector<int>& nums) {
          int i=nums.size()-1;
          
          // 从右向左找到第一个递减的元素
          while(i-1>-1 && nums[i]<=nums[i-1]){
              i--;
          }
          i--;
          
          int l=i+1;
          int r=nums.size()-1;
          int mid;
  
          // 原先数组完全递增，直接反转
          if (i==-1){
              reverse(nums.begin(),nums.end());
              return;
          }
          
          // 在右边二分该元素，找到第一个大于它的元素
          while(l<r) {
              mid=(r-l)/2+l;
              
              if (nums[mid]>nums[i]) {
                  l=mid+1;
              } else {
                  r=mid;
              }
          }
          
          if (nums[l]<=nums[i]){
              l--;
          }
             
          // 交换两元素的值
          swap(nums[i],nums[l]);        
          // 反转右部
          reverse(nums.begin()+i+1,nums.end());        
      }
  };

  556. 下一个更大元素 III

  题意

  将 nums 中的数全排列，问当前排序的下一个排序是什么

  分析

  类似于 31，只是给定的数不是数组，而是一个数的各个位，并且最大全排列不是继续循环，而是返回 -1.同时溢出还要注意一下而已。

  参考 31

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      int nextGreaterElement(int n) {
          vector<int> nums;
          int m;
          
          while (n!=0){
              m=n%10;
              n=n/10;
              nums.insert(nums.begin(),m);
          }
  
          int i=nums.size()-1;
          
          while(i-1>-1 && nums[i]<=nums[i-1]){
              i--;
          }
          i--;
          
          int l=i+1;
          int r=nums.size()-1;
          int mid;
                  
          if (i==-1){
              return -1;
          }
          
          while(l<r) {
              mid=(r-l)/2+l;
              
              if (nums[mid]>nums[i]) {
                  l=mid+1;
              } else {
                  r=mid;
              }
          }
          
          if (nums[l]<=nums[i]){
              l--;
          }
       
          swap(nums[i],nums[l]);        
          reverse(nums.begin()+i+1,nums.end());   
  
          long long res=0;
          
          for (int i=0;i<nums.size();i++){            
              res=res*10+nums[i];
          }
          
          if (res<=INT_MAX){
              return (int)res;
          }
          
          return -1;
      }
  };

对撞指针

• list

  922. 按奇偶排序数组 II

  题意

  使数组 i 和 nums[i] 同奇偶

  分析

  对撞指针，左指针扫奇数，找到不满足的。右指针扫偶数，找到不满足的，交换即可。

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      vector<int> sortArrayByParityII(vector<int>& nums) {
          int i=0;
          int j=nums.size()-1;
          
          while(i<nums.size() && j>-1){
              if (nums[i]%2==0){
                  i+=2;
                  continue;
              }
              if (nums[j]%2!=0){
                  j-=2;
                  continue;
              }
              swap(nums[i],nums[j]);
  
              i=i+2;
              j=j-2;
          }
                          
          return nums;
      }
  };

  面试题 16.16. 部分排序

  题意

  问是否存在一个子数组，使得排列这个数组后，整个数组就是有序的。求子数组的最短长度。

  分析

  这题有点麻烦，没有思路，主要参考这个题解 。

  这个题虽然没给条件，不过测试下来数据就是升序，故按升序来算。

  实际上，这个题只有两种情况，即找得到或找不到。当子数组为空，或者已经升序以后，就找不到，或者说不用找。否则一定找得到答案。

  如果数组有序的话，那么 nums[i] 左边的元素一定比 nums[i] 小，右边的元素一定比 nums[i] 大。这一点没有问题。

  那么反过来，我们怎么判断一个数是否应该被排序呢？很简单，只要满足上面的条件即可。而由于我们要找子数组，那么理论上就能分成三个部分：

  无效的图片地址

  b 就是要找的数组，而 a，c 已经有序。我们要找的，应该就是数组 b 的两个端点。

  我们说过，只要一个数是拍好序的，那么它左边的元素一定比它小，右边的元素一个比它大。换句话说，只有存在左边元素比它大，或者存在右边元素比它小，这个元素就不满足有序，就应该被排序。

  而存在左边元素比 nums[i] 大，等价于 max(left) > nums[i]，存在右边元素比它小，等价于 min(right) < nums[i] .

  也就是说，对于一个元素 nums[i]，只要 max(left) < nums[i] 或者 min(right) > nums[i]，那么它就应该被排序。那么要找到未排序的两个边界，只需遍历一遍，然后找最大和最小的两个即可。

  但实际上，我们还能优化一下。因为满足 max(left)>nums[i] 中最左边的值，一定小于等于 min(right)<nums[i] 最左边的值。满足 min(right)<nums[i] 中最右边的值，一定大于 max(left)>nums[i] 最右边的值。

  故，我们只需找到，满足 max(left)>nums[i] 中最右边的值，就是右边界，和满足 min(left)<nums[i] 中最左边的值，就是左边界。

  算法步骤如下：

  1. 从左遍历，维护 nums[i] 左边的最大值
  2. 如果 max(left)<nums[i]，则更新右端点。
  3. 从左遍历，维护 nums[j] 右边的最小值
  4. 如果 min(right)>nums[j]，则更新左端点。

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      vector<int> subSort(vector<int>& nums) {
          if (nums.empty()){
              return {-1,-1};
          }
          
          int leftMax=nums[0];
          int rightMin=nums[nums.size()-1];
          int l=-1;
          int r=-1;
          
          for (int i=0;i<nums.size();i++){
              if (leftMax>nums[i]){
                  r=i;
              } else {
                  leftMax=nums[i];
              }
          }
          
          for (int j=nums.size()-1;j>-1;j--){
              if (rightMin<nums[j]){
                  l=j;
              } else {
                  rightMin=nums[j];
              }
          }
          
          return {l,r};
      }
  };

原地反转

原地反转通常用于反转字符串，即在 $O(1)$ 空间复杂度的基础上操作

• list

  344. 反转字符串

  题意

  原地反转字符串

  分析

  我们直到所有的数据结构最终在内存中都只有两个组织方式：

  1. 顺序存储
  2. 链式存储

  而对于这两种组织方式中，我们反转这些元素，就是反转字符串和反转链表这两题。

  而要在原地反转的话，那么对于每一个字符，它至少应该从源地址 → 目标地址，比如第一个字符和最后一个字符，第二个字符和倒数第二个字符，那么，这就是一个典型的双指针使用场景，可以说，这种思路就是一个简单的模拟题，遍历所有字符，然后对于该字符，它应该怎么移动，直接模拟即可。

  优化

  这题已经空间复杂度为 $O(1)$，那么能优化的就只有时间复杂度了，而这题前后指针移动时，显然没有什么可优化的，所以只有交换元素可以考虑优化一下。

  而交换元素一般有两种方式：

  1. 临时变量
  2. 异或位运算

  临时变量很好理解，而异或运算其实也很简单：

  s[l]^=s[r]; // s[l]=s[l]^s[r]
  s[r]^=s[l]; // s[r]=s[r]^s[l]^s[r]=s[l]
  s[l]^=s[r]; // s[l]=s[l]^s[r]^s[l]=s[r]

  当然，也可以使用库函数。

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      void reverseString(vector<char>& s) {
          int l=0;
          int r=s.size()-1;
  
          while(l<r) {
              swap(s[l],s[r]);
              l++;
              r--;
          }
      }
  };

  class Solution {
  public:
      void reverseString(vector<char>& s) {
          int l=0;
          int r=s.size()-1;
          char t;
  
          while(l<r) {
              t=s[l];
              s[l]=s[r];
              s[r]=t;
  
              l++;
              r--;
          }
      }
  };

  class Solution {
  public:
      void reverseString(vector<char>& s) {
          int l=0;
          int r=s.size()-1;
  
          while(l<r) {
              s[l]^=s[r];
              s[r]^=s[l];
              s[l]^=s[r];
  
              l++;
              r--;
          }
      }
  };

  917. 仅仅反转字母

  题意

  反转非字母字符

  分析

  类似于 344，只是这题多了非字母字符限制，相对于 344，我们只需跳过非字符字符即可。即使用对撞指针，然后找到字母字符，再交换即可。

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      string reverseOnlyLetters(string s) {
          int l=0;
          int r=s.size()-1;
  
          while(l<r){
              while(l<r && !isChar(s[l])){
                  l++;
              }
              while(r>=0&&!isChar(s[r])){
                  r--;
              }
              if (l>s.size() || r<0 || l>=r){
                  return s;
              }
  
              swap(s[l],s[r]);
              l++;
              r--;        
          }
  
          return s;
      }
  
      bool isChar(char c) {
          return (c>='a' && c<='z')||(c>='A'&&c<='Z');
      }
  };

  345. 反转字符串中的元音字母

  题意

  反转元音字母

  分析

  类似于 917，只是要反转的字符变了而已，使用对撞指针，然后找到字母字符，再交换即可。甚至直接 copy 917 的改下条件就能跑。

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      string reverseVowels(string s) {
          int l=0;
          int r=s.size()-1;
  
          while(l<r){
              while(l<r && !isChar(s[l])){
                  l++;
              }
              while(r>=0&&!isChar(s[r])){
                  r--;
              }
              if (l>s.size() || r<0 || l>=r){
                  return s;
              }
  
              swap(s[l],s[r]);
              l++;
              r--;        
          }
  
          return s;
      }
  
      bool isChar(char c) {
          return ((c=='a')||(c=='e')||(c=='i')||(c=='o')||(c=='u')||(c=='A')||(c=='E')||(c=='I')||(c=='O')||(c=='U'));
      }
  };

  541. 反转字符串 II

  题意

  每隔 k 个字符，翻转 k 个字符，最后小于 k 个也反转。

  分析

  每隔 k 个字符反转 k 个，那么我们可以每次移动 2k 个字符，如果没有范围，那么就反转 k 个即可。

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      string reverseStr(string s, int k) {
          int l=0;
          int r=2*k;
  
          while(r<s.size()) {
              reverse(s.begin()+l,s.begin()+l+k);
              l+=2*k;
              r+=2*k;
          }
  
          if (s.size()-l < k) {
              reverse(s.begin()+l,s.end());
          } else {
              reverse(s.begin()+l,s.begin()+l+k);
          }
  
          return s;
      }
  };

  class Solution {
  public:
      string reverseStr(string s, int k) {
          for (int i=0;i<s.size();i+=2*k){
              if (i+k>s.size()){
                  reverse(s.begin()+i,s.end());
                  return s;
              }
              reverse(s.begin()+i,s.begin()+i+k);
          }
  
          return s;
      }
  };

  557. 反转字符串中的单词 III

  题意

  反转字符串中的单词

  分析

  首先反转单词这个参考 344，原地反转，以 344 为基础。

  然后这题要反转所有单词，那么自然首先需要找到每个单词的起始位置，然后反转即可，故最简单的就是遍历一遍，然后找到为空字符的索引，显然两个索引就是单词，反转即可。我们可以边扫描边反转，没必要扫两边。

  优化

  起始我们没有必要引入数组来存索引，因为每次我们要反转的其实只有一个单词，也就是，每一时刻只需直到两个索引即可，而用数组来存的话，那些已经被反转过的索引就没有用了，显然再存起来就很浪费了，所以我们可以用两个前后指针，分别存当前单词的前后索引即可。

  至于怎么寻找也很简单，右指针找到空字符，反转了左指针直接跳到右指针处即可。

  效率

  时间复杂度：优化前后都是 $O(n^2)$

  空间复杂算：优化前 $O(n)$，优化后 $O(1)$

  代码

  class Solution {
  public:
      string reverseWords(string s) {
          vector<int> bank(1,-1);
          int j=0;
  
          for (int i=0;i<s.size();i++){         
              if (s[i]==' '){
                  bank.push_back(i);
                  reverse(s.begin()+bank[j]+1,s.begin()+bank[j+1]);
                  j++;
              }
          }
  
          reverse(s.begin()+bank[j]+1,s.end());
  
          return s;
      }
  };

  class Solution {
  public:
      string reverseWords(string s) {
          int l=0;
          int r=0;
  
          while(r<s.size()){
              if (s[r]!=' '){
                  r++;
                  continue;
              }
              reverse(s.begin()+l,s.begin()+r);                  
              r++;
              l=r;
          }
  
          reverse(s.begin()+l,s.end());
          return s;
      }
  };

  151. 翻转字符串里的单词

  题意

  反转单词并去除多余的空格

  分析

  这题只是在 557 的基础上增加了多余的空格操作，因此，问题就在于，怎么消除多余的空格，消除多余空格之后，就和 557 一样，先反转整个字符，然后找到单词，再部分反转。

  问题在于怎么消除空格呢？

  如果使用自带的 erase 函数，那么是很容易消除的，只需找到连续两个空格，然后 erase 一个即可。需要注意 erase 一个之后，索引就变短了，因此如果是从左向右遍历，需要自减一次，而如果从右往左遍历，则没有这个限制。

  但是需要注意的是，erase 函数的时间复杂度就已经是 $O(n)$ 的了，因此，总的复杂度就变成 $O(n^2)$ 了，这比较慢。

  优化

  既然 erase 这么慢，而且调用库函数也没有提高编程能力，那么我们就来想办法优化并手动实现一下。

  问题在于，我们该怎么做呢？使用 erase 时，我们每找到一次就删除一次，那么后面的元素都要前移，所以整个复杂度才那么高，实际上我们真的有必要每找到一个空格就删除一次吗？

  其实没有必要，我们可以把空格全部集中在一起，然后之后在一次性删除即可。这样就减少了元素整体移动的情况，那么我们该怎么做呢？

  其实很简单，类似于冒泡排序，我们把空格全部冒到后面即可，之后把后面的所有空格删除就行了。做法也很简单，用对撞指针，分别找到空格和非空格字符即可，而这，就是 27 题的做法。并且也使用到了双指针。

  效率

  时间复杂度：优化前由于 erase 是 $O(n)$ 的，故总 $O(n^2)$，优化后 $O(n)$

  空间复杂度：$O(1)$

  代码

  优化前

  class Solution {
  public:
      string reverseWords(string s) {
  				// 消除空格，除了第一个和最后一个
          for (int i=s.size()-1;i>0;i--){
              if (s[i]==' ' && s[i-1]==' '){
                  s.erase(s.begin()+i);
              }
          }
  				// 消除第一个空格
          if (s[0]==' '){
              s.erase(s.begin());
          }
  
  				// 防止全为空格
  				if (s.empty()) {
              return "";
          }
  
  				// 消除最后一个空格
          if (s[s.size()-1]==' ') {
              s.erase(s.end()-1);
          }
  
  				// 反转整个字符串
          reverse(s.begin(),s.end());
  
          int l=0;
          int r=0;
  				
  				// 反转部分字符串
          while(r<s.size()){
              if (s[r]!=' '){
                  r++;
                  continue;
              }
              reverse(s.begin()+l,s.begin()+r);
              l=r+1;
              r++;
          }
          reverse(s.begin()+l,s.end());
          
          return s;
      }
  };

  优化后

  class Solution {
  public:
      string reverseWords(string s) {
          remove(s);        
          if (s.empty()){
              return s;
          }
          reverseW(s);
          return s;
      }
  
      void remove(string &s){
  				int l=0;
          int r=0;
          
          while(r<s.size() && s[r]==' '){
              r++;
          }
          
          if (r==s.size()){                
              s.resize(0);
              return;
          }
          
          while(r<s.size()){
              if (r>0 && s[r]==s[r-1] && s[r]==' '){ // 如果遇到两个空格，则跳过
                  r++;
                  continue;
              }
              s[l]=s[r]; // 如果不是两个空格，则将其前移
              l++;
              r++;
          }
          if (s[l-1]==' '){
              l--;
          }
          s.resize(l);        
      }
  
      void reverseW(string &s){
          int l=0;
          int r=0;
  
          reverse(s.begin(),s.end());		
          while(r<s.size()){
              if (s[r]!=' '){
                  r++;
                  continue;
              }
              reverse(s.begin()+l,s.begin()+r);
              l=r+1;
              r++;
          }
          reverse(s.begin()+l,s.end());
      }
  };

  剑指 Offer 58 - I. 翻转单词顺序

  同 151

  剑指 Offer 58 - II. 左旋转字符串

  题意

  将前 k 个字符反转到后方

  分析

  只需全部反转字符串，然后分别反转前 k 个字符和后面所有字符即可。

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  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;
      }
  };

  2000. 反转单词前缀

  题意

  反转第一个 ch 字符前的字符

  分析

  找到第一个字符的索引，然后反转即可。

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      string reversePrefix(string word, char ch) {
          int i=0;
          while(i<word.size()&& word[i]!=ch){
              i++;
          }
          if (i<word.size()){
              reverse(word.begin(),word.begin()+i+1);
          }
  
          return word;
      }
  };

  796. 旋转字符串

  题意

  分析

  提示说得很清楚了，字符串 xy 经过旋转得到 yx，那么 xy+xy=xyxy 就必然包含了 yx。但是包含了 yx 就一定成立吗？必要性呢？这个不知道怎么证明。赞踩回复分享举报编辑删除

  优化

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      bool rotateString(string s1, string s2) {
          if (s1.size()!=s2.size()){
              return false;
          }
          return (s1+s1).find(s2)!=-1;
      }
  };

  面试题 01.09. 字符串轮转

  同 796

  459. 重复的子字符串

  题意

  分析

  优化

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      bool repeatedSubstringPattern(string s) {         
          return -1!=(s+s).substr(1,s.size()*2-2).find(s);
      }
  };

回文串

主要是检测回文串问题，主要有对撞指针和中心探测两种方法，而两者都是双指针的典型应用。

• list

  125. 验证回文串

  题意

  只考虑数字和字母，并且忽略大小写，判断是否是回文串。

  分析

  最暴力的自然是从回文串的定义着手，即逆转后判断，但是这样空间复杂度太高，可以优化。

  优化的思路也很简单，我们不是直接比较字符串，而是比较字符，即找到对称的两个字符，然后比较两者是否相等即可。

  而对称的字符也有两种方式，即从串首位开始往中心走，或者中心往两边走。第一种即对撞指针，第二种即中心探测。

  对撞指针

  对撞指针非常简单，需要注意的点有两个：

  1. 非数字、字母字符要跳过
  2. 要忽略大小写

  跳过字符这个好判断，而忽略大小写可以有多种方式，最简单的是利用大小写字符间 ASCII 码的规律，即 字符 & 0b11011111= 对应的大写字符。

  class Solution {
  public:
      bool isPalindrome(string s) {
          int l=0;
          int r=s.size()-1;
          
          while(l<=r) {                        
              if (!isChar(s[l])) {
                  l++;
                  continue;
              }
              if (!isChar(s[r])) {
                  r--;
                  continue;
              }
                          
              if ((s[l] & 0b11011111) != (s[r] & 0b11011111)){
                  return false;
              }
              l++;
              r--;
          }
          
          return true;
      }
      
      bool isChar(char c){
          return (c>='0' && c<='9') || (c>='a' && c<='z') || (c>='A' && c<='Z');
      }
  };

  对撞指针的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

  中心探测

  中心探测是指从字符串中心开始向两侧探测判断，由于字符串分奇偶，故中心也可能有两个。

  无效的图片地址

  故我们编写分别从 l，r 向两侧拓展的函数，然后根据奇偶设置中心 l、r。

  对了，由于中心探测需要提前知道字符串长度奇偶，而原题又要跳过特殊字符，比较麻烦，故提前预处理了下。去掉特殊字符。

  class Solution {
  public:
      bool isPalindrome(string s) {        
          s=regex_replace(s,regex("[^0-9a-zA-Z]"),"");
  
          if (s.size()%2==0){
              return expandAroundCenter(s,s.size()/2-1,s.size()/2);
          } else {
              return expandAroundCenter(s,s.size()/2,s.size()/2);
          }
      }
      
      bool expandAroundCenter(string s,int l,int r){
          while (l>-1 && r<s.size()){            
              if ((s[l] & 0b11011111) != (s[r] & 0b11011111)){
                  return false;
              }
              l--;
              r++;
          }
          
          return true;
      }
  };

  中心探测的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

  680. 验证回文字符串 Ⅱ

  题意

  删除一个字符后，判断是不是回文串

  分析

  先对撞指针，找到不等的两字符后，拆分成两个字符串，再分别判断即可。判断方式有对撞指针和中心探测。

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  中心探测

  class Solution {
  public:
      bool validPalindrome(string s) {
          int l=0;
          int r=s.size()-1;
          int cnt=0;
          
          while(l<=r) { 
              if (s[l]==s[r]){
                  l++;
                  r--;
                  continue;
              }
              return isPalindrome(s.substr(l,r-l))||(isPalindrome(s.substr(l+1,r-l)));
          }
          
          return true;        
      }
      
      bool isPalindrome(string s) {        
          if (s.size()%2==0){
              return expandAroundCenter(s,s.size()/2-1,s.size()/2);
          } else {
              return expandAroundCenter(s,s.size()/2,s.size()/2);
          }
      }
      
      bool expandAroundCenter(string s,int l,int r){
          while (l>-1 && r<s.size()){            
              if ((s[l] & 0b11011111) != (s[r] & 0b11011111)){
                  return false;
              }
              l--;
              r++;
          }
          
          return true;
      }
  };

  对撞指针

  class Solution {
  public:
      bool validPalindrome(string s) {
          int l=0;
          int r=s.size()-1;
          int cnt=0;
          
          while(l<=r) { 
              if (s[l]==s[r]){
                  l++;
                  r--;
                  continue;
              }
  
              return expandAroundCenter(s,l+1,r) || expandAroundCenter(s,l,r-1);
          }
          
          
          return true;        
      }
  
      
      bool expandAroundCenter(string s,int l,int r){
          while (l<r){            
              if (s[l] != s[r]){
                  return false;
              }
              l++;
              r--;
          }
          
          return true;
      }
  };

  面试题 01.04. 回文排列

  题意

  判断字符串是否是回文串的排列。

  分析

  回文串要么奇数长度，要么偶数长度。奇数长度时，只有中心个数为 1，其它都是对称的。偶数所有字符都是对称的。所以，回文串中，字符是奇数的个数要么是 1，或者 0.

  那最简单的自然是统计奇数字符个数了，直接开 map 即可。

  优化

  我们实际上根本不需要知道字符的个数，没必要统计个数再判断奇偶。我们只需在遍历的过程中就维护字符奇偶性即可。而奇偶性只有两种状态，故我们可用位图 bitset 来维护。0 表示偶数，1 表示计数。

  那么每增加一个字符，它的状态就在 0 和 1 间交替。即 0←→1取反操作。故我们每增加一个字符，将其对应位取反即可。

  最后再统计计数个数，即 1 的个数是否小于 2 即可。

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(n)$

  代码

  map

  class Solution {
  public:
      bool canPermutePalindrome(string s) {
          int cnt=0;
          unordered_map<char,int> m;        
          
          for (int i=0;i<s.size();i++){
              m[s[i]]++;
          }
          
          for (auto k:m){
              cnt+=(k.second%2);
          }
          
          return cnt<=1;
      }
  };

  优化

  class Solution {
  public:
      bool canPermutePalindrome(string s) {
          bitset<127> b;        
          
          for (int i=0;i<s.size();i++){
              b.flip(s[i]);
          }
          
          return b.count()<2;
      }
  };

  409. 最长回文串

  题意

  在字符串中任取字符，问最长能组成的回文串长度是多少

  分析

  这题和 面试题 01.04. 回文排列 类似，都是考回文串的性质，即：

  回文串要么奇数长度，要么偶数长度。奇数长度时，只有中心个数为 1，其它都是对称的。偶数所有字符都是对称的。所以，回文串中，字符是奇数的个数要么是 1，或者 0.

  那么我们要取字符的话，最后要么都取偶数，要么再取一个奇数。

  思路有了后，实现就很简单了，由于要知道字符是奇偶数，所以用 map 计算下奇偶（并且由于要用到个数，所以不能像 01.04 那样用位图了）。

  然后取所有的偶数，如果有奇数，再从所有奇数里面取余下一个，最后再从奇数里去一个，这就是偶数情况。如果没有奇数，那就取所有偶数就行了。

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(n)$

  代码

  class Solution {
  public:
      int longestPalindrome(string s) {
          unordered_map<char,int> m;  
          int res=0;
          int hasOdd=0;
          
          for (int i=0;i<s.size();i++){
              m[s[i]]++;
          }
          
          for (auto k:m){
              if (k.second%2==0){
                  res+=(k.second);
              } else {
                  res+=(k.second-1);
                  hasOdd=1;
              }
          }
          
          return res+hasOdd;
      }
  };

  1332. 删除回文子序列

  题意

  每次删除一个回文子序列，问多少次可以删光

  分析

  这个题在题意上有点坑，因为是回文子序列而不是子串，也就是说，可以不连续。

  那么一共三种情况：

  1. 如果字符串本身为空，那自然不需要删，删除次数为 0
  2. 如果字符串是回文，那么一次就删除完，次数为 1
  3. 如果字符串不是回文，由于一共两种字符，而全为 a 或全为 b 也是子串，所以我们可以每次删除同一种字符，比如先把所有 a 删除，再把余下的 b 删了，次数就为 2.

  综上，这题就是个判断回文操作而已，使用简单的对撞指针即可。

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      int removePalindromeSub(string s) {
          if (s.empty()){
              return 0;
          }
          
          int l=0;
          int r=s.size()-1;
          
          while(l<r){
              if (s[l]!=s[r]){
                  return 2;
              }
              l++;
              r--;
          }
          
          return 1;
      }
  };

  1616. 分割两个字符串得到回文串

  题意

  相同索引分割两字符串，问两字符串前后缀分开组成的新字符串是否有回文串

  分析

  最简单的自然是把所有生成的字符串枚举出来，然后判断是否有回文串，判断的方式用对撞指针或中心探测都行。

  不过数量级在 10^5，显然暴力 $O(n^2)$ 会超时。

  优化

  优化的思想也很简单，充分利用到了回文串的回文特性，即：从中心到两边探测，生成的子串也是回文串。反过来一样的，要是回文串，那么中心到两侧的子串需要是回文串才行。

  先两字符串两侧往中间判断

  无效的图片地址

  假设这时 s1[l]≠s2[r]

  无效的图片地址

  而最终要形成回文串，显然只有 xmy 或 xny 这两种情况

  无效的图片地址

  现在 x 和 y 已经对称，那么要使得总的字符串成回文，必有中间的子串 n 或 m 是回文。所以这时我们再判断 m 或 n 是否是回文即可。

  上面是 s1 取前缀，s2 取后缀，反过来也是一样的。

  效率

  时间复杂度：暴力 $O(n^2)$ 优化 $O(n)$

  空间复杂度：$O(1)$

  代码

  暴力

  class Solution {
  public:
      bool checkPalindromeFormation(string s1, string s2) {
  				// 枚举生成的字符串
          for (int i=0;i<s1.size();i++){
              if (isPalindrome(s1.substr(0,i)+s2.substr(i,s1.size()-i)) || isPalindrome(s2.substr(0,i)+s1.substr(i,s1.size()-i))){
                  return true;
              }
          }
          
          return false;
      }    
      
  		// 中心探测判断回文串
      bool isPalindrome(string s) {        
          if (s.size()%2==0){
              return expandAroundCenter(s,s.size()/2-1,s.size()/2);
          } else {
              return expandAroundCenter(s,s.size()/2,s.size()/2);
          }
      }
      
      bool expandAroundCenter(string s,int l,int r){
          while (l>-1 && r<s.size()){            
              if (s[l] != s[r]){
                  return false;
              }
              l--;
              r++;
          }
          
          return true;
      }
  };

  优化

  class Solution {
  public:
      bool checkPalindromeFormation(string s1, string s2) {
          return check(s1,s2) || check(s2,s1);
      }
      
      bool check(string s1,string s2){
          int l=0;
          int r=s1.size()-1;
          
  				// 先两侧判断
          while(l<r && s1[l]==s2[r]){
              l++;
              r--;
          }
          
  				// 再判断中间的子串是否是回文
          return isPalindrome(s1,l,r) || isPalindrome(s2,l,r);
      }
      
      // 对撞指针法判断回文串
      bool isPalindrome(string s,int l,int r){
          while(l<r){
              if (s[l]!=s[r]){
                  return false;
              }
              l++;
              r--;
          }
          
          return true;
      }
  };

  5. 最长回文子串

  题意

  找到字符串的最长回文子串

  分析

  最暴力的解法自然是枚举每个字符串，然后判断是否是回文子串。不过枚举的复杂度太高，我们没必要枚举字符串，根据判断回文子串的两种方式，即对撞指针和中心探测，我们枚举边界或者中心即可。枚举边界的话，显然复杂度为 $O(n^2)$，而枚举中心只要 $O(n)$，故我们枚举中心。

  枚举中心，然后用中心探测法找到最长的回文子串即可。需要注意的是，由于可能有两个中心的情况，故当相邻两字符相等时，则要判断双中心的情况。

  优化

  我们可以利用回文串的特性来优化，即马拉车算法。todoing

  效率

  时间复杂度：$O(n^2)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      string longestPalindrome(string s) {
          string res;
          string even,odd;
          
          for (int i=0;i<s.size();i++){
              even=expandAroundCenter(s,i,i);
              if (res.size()<even.size()){
                  res=even;
              }
              if (i+1<s.size() && s[i]==s[i+1]){
                  odd = expandAroundCenter(s,i,i+1);
              }
              if (res.size()<odd.size()){
                  res=odd;
              }
          }        
          
          return res;
      }
      
      string expandAroundCenter(string s,int l,int r){
          while (l-1>-1 && r+1<s.size() && s[l-1]==s[r+1]){           
              l--;
              r++;
          }
          
          return s.substr(l,r-l+1);
      }
  };

  647. 回文子串

  题意

  找到字符串中子串是回文串的数量

  分析

  这个题就是 5 题+696 题的结合，即枚举中心，然后用中心探测法求最长回文子串，而最长回文子串又包含 length/2 个回文子串，最后求和即可，需要注意一下双中心的情况。

  优化

  无

  效率

  时间复杂度：$O(n)$

  空间复杂度：$O(1)$

  代码

  class Solution {
  public:
      int countSubstrings(string s) {
          int res=0;
          int even,odd;
          
          for (int i=0;i<s.size();i++){
              even=expandAroundCenter(s,i,i);
              res+=even;
              if (i+1<s.size() && s[i]==s[i+1]){
                  odd = expandAroundCenter(s,i,i+1);
                  res+=odd;
              }            
          }        
          
          return res;
      }
          
      int expandAroundCenter(string s,int l,int r){
          int res=1;
          while (l-1>-1 && r+1<s.size() && s[l-1]==s[r+1]){             
  						res++;
              l--;
              r++;
          }
          
          return res;
      }
  };