【强化算法专题一】双指针算法

1.双指针算法–移动零

算法原理解析-------------------------------------------------------------------------------动手实践

【代码:】

class Solution {
public:


//双指针：本质就是划分数组，数组分块
//cur:用来遍历数组，将数组分成两个部分，[o,cur-1]已经处理的部分[cur,n-1]待处理的部分
//已经处理的部分要求是什么呢？非0元素在前面，0元素在后面，那么我们利用dest指针来作为它们的分割线
//dest:已经处理的部分又被dest分割成两部分，[0,dest]是非0部分，而[dest+1,cur-1]就是0部分
//所以数组总体被分成三部分
    void moveZeroes(vector<int>& nums) {

     int cur=0;
     int dest=cur-1;

    while(cur<nums.size())
    {
        if(nums[cur]==0)
        {
            //当遇到0时不需要放入des区间，因为des区间里都是非0的
            cur++;
        }
        else
        {
            //当遇到非0时，就需要放入des区间，放进一个元素dest就要往后挪动一下，流出位置
            //但不能覆盖要交换
            dest++;
            swap(nums[dest],nums[cur]);
            cur++;
        }
    } 

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

2.双指针算法–复写零

算法原理解析-------------------------------------------------------------------------------动手实践

【代码:】

class Solution 
{
public:
    void duplicateZeros(vector<int>& arr)
    {
        //第一步找最后一个复写的数据
        int cur=0,dest=-1,n=arr.size();
        while(cur<n)
        {
            if(arr[cur])dest++;
            else dest+=2;
            //dest每次走完都要判断一下是否到头
            if(dest>=n-1)
            break;
            cur++;
        }
        //特殊情况处理
        if(dest==n)
        {
            arr[n-1]=0;
            dest-=2;
            cur--;
        }
        //正常往前复写
        while(cur>=0)
        {
            if(arr[cur])
            arr[dest--]=arr[cur--];
            else
            {
                arr[dest--]=0;
                arr[dest--]=0;
                cur--;
            }
        }
    }
};
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

3.双指针算法–快乐数

算法原理解析-------------------------------------------------------------------------------动手实践

【代码:】

class Solution 
{
public:
  
   int work(int n)
   {
       int ret=0;
       while(n)
       {
           ret+=(n%10)*(n%10);
           n=n/10;
       }
       return ret;
   }
    bool isHappy(int n) 
    {
    
    int slow=n,fast=n;
     //判断快慢指针相遇
     while(slow&&fast)
     {
         slow=work(slow);
         //慢指针每次走1次操作
         fast=work(work(fast));
         //快指针每次走2次操作
         if(fast==slow)
         {
             if(fast==1)
             return true;
             else
             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
29
30
31
32
33
34
35
36

4.双指针算法–盛水最多的容器

算法原理解析-------------------------------------------------------------------------------动手实践

【代码:】

class Solution {
public:
   int lower(int x,int y)
   {
       if(x<y)
       return x;
       else 
       return y;
   }
    int maxArea(vector<int>& height) 
    {
        vector<int> vt;
        int left=0,right=height.size()-1,V=0;
        while(left<right)
        {
            V=(right-left)*(lower(height[left],height[right]));
            vt.push_back(V);
            if(height[left]<height[right])
            ++left;
            else
            --right;
        }
      
     sort(vt.begin(),vt.end());
     return vt[vt.size()-1]; 
    }
};
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

5.双指针算法–有效三角形的个数

算法原理解析-------------------------------------------------------------------------------动手实践

【代码:】

class Solution {
public:
    int triangleNumber(vector<int>& nums) 
    {
         sort(nums.begin(),nums.end());
         //首先优化数组，先排序
         int ret=0,ci=nums.size()-1;
         //首先固定的是最大值
         while(ci>=0)
         {
             int left=0,right=ci-1;
            //在最大值前面的区间里利用双指针算法
            while(left<right)
            {
                if(nums[left]+nums[right]>nums[ci])
                {
                    ret+=right-left;
                    right--;
                }
                else
                {
                    left++;
                }
            }
            ci--;
         }
          return ret;
    }
   
};
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

6.双指针算法–和为s的两个数

算法原理解析-------------------------------------------------------------------------------动手实践

【代码:】

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        //使用双指针算法
        int left=0,right=nums.size()-1;
        while(left<right)
        {
            if(nums[left]+nums[right]>target)
            --right;
            else if(nums[left]+nums[right]<target)
            ++left;
            else
            return {nums[left],nums[right]};
            //大括号，这样写会发生隐射类型转化，调用vector的构造函数来构造
        }
        return {-1,-1};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

7.双指针算法–三数之和

算法原理解析-------------------------------------------------------------------------------动手实践

【代码:】

class Solution 
{
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
      //首先优化数组，对数组排序
      sort(nums.begin(),nums.end());
      //首先固定一个元素a，对后面的区间使用双指针算法，筛选
      //筛选的过程中要注意去重

      int ti=0;
      vector<vector<int>> vv;
      while(ti<nums.size()-1)
      {
        //这里要有一个小优化，排完序后，0后面肯定都是正数，整数固定以后后面不可能能找到负数了
        //所以直接可以跳过就不用固定了
           if(nums[ti]>0)break;
          //对后面的区间使用双指针算法
          int left=ti+1,right=nums.size()-1,target=-nums[ti];
         while(left<right)
         {
              if(nums[left]+nums[right]>target)
          {
            right--;
          }
          else if(nums[left]+nums[right]<target)
          {
              left++;
          }
          else//说明找到这个三元组了
          {
            vv.push_back({nums[ti],nums[left],nums[right]});
            //当找到一对满足条件的元素时，left和right要同时挪动,接下剩下的区间继续寻找
            //但要根据要去重，我们得注意下次如果再遇到上次的元素还是直接跳过去
            left++;
            right--;
            while(nums[left]==nums[left-1]&&left<right)left++;
            //还要注意避免越界left
            while(nums[right]==nums[right+1]&&left<right)right--;
          }
         }
       //最后还要注意对固定的元素进行去重，因为当固定相同的元素时，也会出现重复的
       int later=ti;
       ++ti;
       while(nums[later]==nums[ti]&&ti<nums.size()-1)
       //避免越界
        ++ti;
      }
      return vv;
    }
};
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
39
40
41
42
43
44
45
46
47
48
49
50
51

8.双指针算法–四数之和

算法原理解析-------------------------------------------------------------------------------动手实践

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        vector<vector<int>> vv;
       //第一步给数组排序
       sort(nums.begin(),nums.end());
       //依次固定一个数a  找target-a
       for(int i=0;i<nums.size();)
       {
           int a=nums[i];
           //依次固定一个数b
           for(int j=i+1;j<nums.size();)
           {
             int b=nums[j];
             long long tar=(long long)target-a-b;
             //在b后面的区间里使用双指针算法找  target-a-b
             int left=j+1,right=nums.size()-1;
             while(left<right)
             {
                 if(nums[left]+nums[right]<tar)
                 left++;
                 else if(nums[left]+nums[right]>tar)
                 right--;
                 else
                 {
                     vv.push_back({a,b,nums[left],nums[right]});
                     left++;
                     right--;
                     //首先放入数组里，left和right各自走一步
                     //然后检查后面的值是否有相同的，如果是相同的那就跳过
                     while(nums[left]==nums[left-1]&&left<right)++left;
                     while(nums[right]==nums[right+1]&&left<right)--right;

                 }
                 //b也要注意后面如果有相同的也要跳过
             }
             j++;
             while(j<nums.size()&&nums[j-1]==nums[j])j++;
           }

           i++;
           while(i<nums.size()&&nums[i-1]==nums[i])i++;
       }

       return vv;
    }
};
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
39
40
41
42
43
44
45
46
47
48