• 『 基础算法题解 』之双指针（上）

  ---

  双指针

  文章目录

  • 双指针
  • • 移动零
    • • 题目解析
      • 算法原理
      • 代码
      • 拓展
    • 复写零
    • • 题目解析
      • 算法原理
      • 代码
    • 快乐数
    • • 题目解析
      • 算法解析
      • • 拓展
      • 代码
    • 盛最多水的容器
    • • 题目解析
      • 算法解析
      • 代码
    • 有效的三角形个数
    • • 题目解析
      • 算法原理
      • 代码

  ---

  移动零

  题目解析

  【题目链接】

  

  ---

  算法原理

  该种题目可以归为一类题数组分块\数组划分;

  该题的大概为给定一个数组,并给定一个对应的规则,使得数组按照规则划分为若干个区间;

  在这个题目中,最终的数组会被分为两块,分别为:

  != 0

  == 0

  

  而在实际的过程中可以分为三块:

  假设有两个指针分别为cur指针与dest指针;

  cur指针用来遍历数组;

  dest指针为已处理区间内,非0元素与0元素的分界线,即最后一个非0元素的位置;

  != 0

  == 0

  未处理

  

  从上图中可以看到,三个区间分别为

  [0,dest],[dest+1,cur-1],[cur,n-1]

  这题的思路即为控制dest指针与cur指针,使得数组在每一次的移动或者操作中都始终都趋于该数组分化;

  在对两个指针进行初始化时,由于是上面的三段区间,cur又因为需要用来遍历整个数组,所以初始化cur的位置应该是在数组首元素的位置(即0位置);

  而对于dest指针来说,该指针用来划分非0元素与0元素,但是在最初始的情况下并没有非0元素区间,所以该段区间不存在,dest指针最初的位置应该在0位置的前一个,也就是-1的位置;

  当cur指针遍历到一个0元素时不进行操作,但cur指针遍历到一个非0元素时,应该移动dest指针使其++,并交换dest指针所指向的元素与cur遇到的非0元素;

  以第一个测试用例[ 0 , 1 , 0 , 3 , 12 ]

  该测试用例的答案为[ 1 , 3 , 12 , 0 , 0 ](分块过后非0元素的顺序不发生改变)

  

  ---

  代码

  根据上述描述只需要用双指针，利用迭代即可解决；

  class Solution {
  public:
      void moveZeroes(vector& nums) {
          int cur = 0;
          int dest = -1;
          while(cur

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

  ---

  拓展

  对于移动0这个题目来说,其实它的原理与快速排序的每一趟都是一样的;

  快速排序单趟排序hoare原生的思路即为:定义一个基准值,将大于或者小于基准值的数据分别进行分类;

  ---

  ---

  ---

  复写零

  题目解析

  【题目链接】
  

  题目的几个点:

  • 将0复写
  • 不能越界
  • 原地算法

  ---

  算法原理

  该题的解法是用双指针;

  而该双指针的解法是由异地算法进行推断的;

  以测试用例[ 1 , 0 , 2 , 3 , 0 , 4 , 5 , 0 ]为例;

  • 异地

    使用异地算法即多开一个同样大小的空间,遇到0即复写2次,遇到1即复写一次;

    同时在复写的过程中判断在复写过程中是否会产生越界;

    

    class Solution {
    public:
        void duplicateZeros(vector& arr) {
            size_t len = arr.size();
            vector tmp(arr.size());
            for(size_t cur = 0, dest = 0;dest

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

• 原地

  若是在原地的话则不能使用从左向右遍历,若是从左向右遍历的话将会出现有效内容被覆盖的问题;

  

如图所示,若是双指针都从前往后进行遍历的话将会出现覆盖的问题;

所以在复写的过程中我们可以推断出应该由后向前进行遍历;

由该测试用例的异地操作可知,最后一个复写的数据为4;下标为5的数据;

假设cur指针指向该数据,而dest指针指向n-1的位置由后向前进行遍历,且复写的规则不变;

从上述操作可以将步骤分解为两步:

1. 找到最后一个复写的元素;

   找到最后一个复写的元素这里采用的是一个双指针的方式;

   即使用双指针将复写的步骤模拟进行一遍,cur指针用来遍历,dest指针用来记录(模拟)复写;

   由于需要找到的是完成复写时的位置,所以定义dest时定义为-1,而cur用于遍历,所以在0位置处;

   可以分为四步:

   • 判断cur所指向的数据是否为0,若是为0则复写2次(dest+=2);
   • 若是为非0则复写1次(dest++);
   • 判断dest是否完成所有复写;
   • 继续遍历cur指针;

   /*
   *找到最后一个复写的位置
   */
   	int len = arr.size();
   	int cur = 0;
   	int dest = -1;
   	for(;dest=len-1) break;
   	}
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15

2. 根据规则由后向前进行复写;

    for(;cur>-1||dest>-1;--cur,--dest){
               arr[dest] = arr[cur];
               if(arr[cur] == 0){
                   arr[--dest] = 0;
               }
           }
   1
   2
   3
   4
   5
   6

但是很不巧的是若是以这样的方式提交代码仍然会报错;

报错的原因一样是因为越界;

假设有这样一组数据:[ 8 , 4 , 5 , 0 , 0 , 0 , 0 , 7 ];

在为该数据找最后一个复写的数据时将会出现这样的问题:

在该测试用例中,由于多次进行了2次复写0的操作从而导致了最终dest指针越界;

所以在这里应该进行边界控制;

在该题中越界的程度只能是1(只存在步长为1或者步长为2的操作);

if(dest == len){
            arr[len-1] = 0;
            --cur,dest-=2;//由于dest已经进行越界，所以要多跳一步；
        }
1
2
3
4

---

代码

class Solution {
public:
    void duplicateZeros(vector& arr) {
        /*
        *找到最后一个复写的位置
        */
        int len = arr.size();
        int cur = 0;
        int dest = -1;
        for(;dest=len-1) break;
        }
        cout<-1||dest>-1;--cur,--dest){
            arr[dest] = arr[cur];
            if(arr[cur] == 0){
                arr[--dest] = 0;
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

---

---

---

快乐数

题目解析

【题目链接】

题目的要求是判断一个数是否为快乐数；

同时给出了关于快乐数的规则：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是则返回 false 。

---

算法解析

在这道题目中可以用以下两种方式进行解决；

• unordered_map 哈希暴力法；

  该方法即使用unordered_map 容器用于判断是否有数据重复;

  若是重复则返回并判断重复的值是否为1;

• 快慢双指针法；

  该方法则使用到了一个思路,即快慢指针;

  以题目中给出的两个例子进行分析;

  1. 19

     1² + 9² = 82; 8² + 2² = 68;

     6² + 8² = 100; 1² + 0² = 1;

     1² + 0² = 1; …

     用图表示即为

     

  2. 2

     2² = 4; 4² = 16;

     1² + 6² = 37; …

     1² + 4² + 5² = 42; 4² + 2² = 20;

     2² + 0² = 4;

     …

     用图表示即为

     

     从两图可知这里将会形成一个类似于带环链表的结构;

     两处都必定会在同一处进行循环;

     而这题与判断链表是否带环唯一的不同之处就是该题只需要判断相遇或者循环的位置是否为1即可;

  拓展

  在这一题目的描述之中,有个奇妙的点,为什么在这个规则之下必定会出现循环且不会有第三种结果(即无限不循环);

  鸽巢原理(抽屉原理)

  假设鸽巢的数量为n而鸽子的数量为n+1,则必定会有格子数量大于1的鸽巢;

  同时假设n为9999999999 , 以快乐数的规则而言,该数为 9² * 10 为810;

  换言之它的区间即为[ 1 , 810 ];

  当经过810次的上述操作后,再第811次时的操作必定会重复;

  所以不会存在第三种结果;

---

代码

unordered_map暴力法

class Solution {
public:
    bool isHappy(int n) {
        if(n == 1){//特殊例子所作处理 " 1 "
            return true;
        }
        
        unordered_map _ret;
        int ret = 0;
        while(n!=1){
            int sum = 0;
            int tmp = n;
            while(n){
                sum+=(n%10)*(n%10);
                n/=10;
            }
            n = sum;
            ++_ret[n];
            if(n == 1) return true;//如果n为1提前结束
            for(auto [num,count]:_ret){
                if(count>=2){
                    return false;//用于判断是否无限循环
                }
            }
        }
        return false;//防止报错所作处理
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

快慢双指针法

class Solution {
public:

    int RetSum(int n){//将操作单独封装为一个子函数
        int sum = 0;
        while(n){
            sum += (n%10) * (n%10);
            n/=10;
        }
        return sum;
    }

    bool isHappy(int n) {
        size_t slow = n;
        size_t fast = n;
        do{
            fast = RetSum(RetSum(fast));
            slow = RetSum(slow);
        }
        while(slow!=fast);
        if(slow == 1){
            return true;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

---

---

---

盛最多水的容器

题目解析

【题目链接】

该题目中要求计算盛水最多的容器；

即要求计算x轴与y轴乘积最大的一次；

以给出的实例1

[ 1 , 8 , 6 , 2 , 5 , 4 , 8 , 3 , 7 ]

在该示例中的答案为y轴为8与7时;

x轴长度为8-1 = 7时的乘积为49;

---

算法解析

在该题目中有两种解法

• 暴力枚举法

  对于暴力枚举来说即定义两个指针,利用嵌套for循环枚举出每一个可能性并找到Max最大值;

  时间复杂度为O(N²);

  该时间复杂度在该题中将会超出时间限制(2w数量的测试用例);

• 双指针遍历

  该方法则考虑到一个规律;

  以该段数组中的小区间[ 8 , 6 , 2 , 5 , 4 ]为例;

  

  在这个区间内的盛水量为 4*(4-0) = 16;

  假设以右边高度 4 进行枚举(与 6 , 2 , 5 )则会出现两种状况(由于始终是向内进行枚举所以宽度w不断在缩小):

  1. 当碰到比4要小的高度时高度h减小,容积v = h*w也在减小;
  2. 当碰到比4要大的高度时,高度不变,但由于w在缩小所以容积v一样会缩小;

  通过上面两种结果可以直接判断,当高度不同时优先舍弃高度较低的高度枚举;

---

代码

• 暴力枚举法

  class Solution {
  public:
      int maxArea(vector& height) {
          int maxR = 0;//记录当前所记录的最大容量
          for(int i = 0;imaxR) maxR = tmp;
              }
          }
          return maxR;
  
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15

• 双指针遍历法

  class Solution {
  public:
      int maxArea(vector& height) {
          int maxR = 0;
          int left = 0;
          int right = height.size()-1;
          
          while(right>=left){
              int min = height[right]