devbox
小蓝xlanll
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法练习之双指针算法

作者：小蓝xlanll | 2024-05-17 05:16:52

赞

踩

算法练习之双指针算法

目录

前言

一、移动零【做题链接】

二、复写零【做题链接】

三、快乐数【做题链接】

四、盛水最多的容器【做题链接】

五、查找总价值为目标值的两件商品【做题链接】

六、三数之和【做题链接】

七、四数之和 【做题链接】

八、有效三角形的个数【做题链接】

总结

前言

欢迎感兴趣的小伙伴交流学习。

一、移动零【做题链接】

图1.1        题目描述
图1.2        题目解释

 题目代码：

  1. class Solution {
  2. public:
  3.     void moveZeroes(vector<int>& nums) 
  4.     {
  5.         int green_pointer = 0;
  6.         int blue_pointer = -1;
  7.  
  8.         for (; green_pointer < nums.size(); green_pointer++)
  9.         {
  10.             if (nums[green_pointer] != 0)
  11.             {
  12.                 blue_pointer++;
  13.                 
  14.                 int tmp;
  15.                 tmp = nums[green_pointer];
  16.                 nums[green_pointer] = nums[blue_pointer];
  17.                 nums[blue_pointer] = tmp;
  18.             }
  19.         }
  20.     }
  21. };

二、复写零【做题链接】

图2.1        题目描述
图2.2        题目解析

题目代码：

  1. class Solution {
  2. public:
  3.     void duplicateZeros(vector<int>& arr)
  4.     {
  5.         int write = arr.size() - 1;
  6.         int count_write_zore = 0;
  7.         int read;
  8.         int i = 0;
  9.         for (; count_write_zore < arr.size(); i++)
  10.         {
  11.             count_write_zore++;
  12.             if (arr[i] == 0)
  13.             {
  14.                 count_write_zore++;
  15.             }
  16.         }
  17.         read = i - 1;
  18.       
  19.         for (; read >= 0; read--)
  20.         {
  21.             arr[write--] = arr[read];
  22.             if (arr[read] == 0 && (read != i - 1 || count_write_zore == arr.size()))
  23.             {
  24.                 arr[write--] = arr[read];
  25.             }
  26.         }
  27.     }
  28. };

三、快乐数【做题链接】

图3.1        题目描述

题目代码： 

  1. class Solution {
  2. public:
  3.     int count(int n)
  4.     {
  5.         int ret=0;
  6.         while(n%10!=0||n/10)
  7.         {
  8.             ret+=pow(n%10,2);
  9.             n/=10;
  10.         }
  11.         cout<<ret<<" ";
  12.         return ret;
  13.     }
  14.  
  15.     bool isHappy(int n) 
  16.     {
  17.         int fast_pointer=count(count(n));
  18.         int slow_pointer=n;
  19.  
  20.         while(fast_pointer!=slow_pointer)
  21.         {   
  22.  
  23.             fast_pointer=count(count(fast_pointer));
  24.             cout<<"(";
  25.             slow_pointer=count(slow_pointer);
  26.             cout<<")";
  27.         }
  28.        
  29.         if(fast_pointer==1)
  30.         {
  31.             return true;
  32.         }
  33.         return false;
  34.     }
  35. };

四、盛水最多的容器【做题链接】

图4.1        题目描述 
  1. class Solution {
  2. public:
  3.     int maxArea(vector<int>& height) 
  4.     {
  5.         int left=0;
  6.         int right=height.size()-1;
  7.         int ret=0;
  8.  
  9.         while(left<right)
  10.         {
  11.            ret=max(ret,(right-left)*min(height[right],height[left]));
  12.            if(height[left]<height[right])
  13.            {
  14.             left++;
  15.            }
  16.            else if(height[left]>=height[right])
  17.            {
  18.             right--;
  19.            }
  20.            cout<< ret<<" "<<left<<" ";
  21.         }
  22.         return ret;
  23.     }
  24. };

五、查找总价值为目标值的两件商品【做题链接】

图5.1        题目描述 
  1. class Solution 
  2. {
  3. public:
  4.     vector<int> twoSum(vector<int>& price, int target) 
  5.     {
  6.         int left=0;
  7.         int right=0;
  8.         vector<int> ret;
  9.         for(int i=0;i<price.size();i++)
  10.         {
  11.             left=i;
  12.             right=price.size()-1;
  13.             int need=target-price[i];
  14.             while(left<right)
  15.             {
  16.                 if(need>price[right])
  17.                 {
  18.                     break;
  19.                 }
  20.                 else if(need<price[left])
  21.                 {
  22.                     break;
  23.                 }
  24.                 else
  25.                 {
  26.                     if(need==price[left]||need==price[right])
  27.                     {
  28.                         ret.push_back(price[i]);
  29.                         if(need==price[left])
  30.                         {
  31.                             ret.push_back(price[left]);
  32.                         }
  33.                         else
  34.                         {
  35.                             ret.push_back(price[right]);
  36.                         }
  37.                         return ret;
  38.                     }
  39.                     left++;
  40.                     right--;
  41.                 }
  42.             }
  43.         }
  44.         return ret;
  45.     }
  46. };

 

六、三数之和【做题链接】

图6.1        题目描述 
  1. class Solution {
  2. public:
  3.     vector<vector<int>> threeSum(vector<int>& nums)
  4.     {
  5.         vector<vector<int>> ret;
  6.         sort(nums.begin(), nums.end());    
  7.         for (int i = 0; i < nums.size(); i++)
  8.         {
  9.             int left = i + 1;
  10.             int right = nums.size() - 1;
  11.             int target = -nums[i];
  12.             if (i!=0&&nums[i] == nums[i - 1])
  13.             {
  14.                 continue;
  15.             }
  16.             while (left < right)
  17.             {
  18.                 
  19.                 if (target == nums[left]+ nums[right])
  20.                 {
  21.                     if ((left!=i+1)&&nums[left]==nums[left-1]||(right!=nums.size()-1)&&nums[right]==nums[right+1])
  22.                     {
  23.                         if (nums[left] == nums[left - 1])
  24.                         {
  25.                             left++;
  26.                         }
  27.                         if (nums[right] == nums[right + 1])
  28.                         {
  29.                             right--;
  30.                         }
  31.                         continue;
  32.                     }
  33.                     ret.push_back({ nums[i],nums[left],nums[right]});
  34.                     left++;
  35.                     right--;
  36.                 }
  37.                 else if (target > nums[left] + nums[right])
  38.                 {
  39.                     left++;
  40.                 }
  41.                 else if (target < nums[left]+ nums[right])
  42.                 {
  43.                     right--;
  44.                 }
  45.             }
  46.         }
  47.         return ret;
  48.     }
  49. };

七、四数之和 【做题链接】

图7.1        题目描述 
  1. class Solution {
  2. public:
  3.     vector<vector<int>> fourSum(vector<int>& nums, int target) 
  4.     {
  5.         vector<vector<int>> ret;
  6.         sort(nums.begin(),nums.end());
  7.         for(int i=0;i<nums.size();i++)
  8.         {
  9.             long long tmp1=target-nums[i];
  10.             if(i!=0&&nums[i]==nums[i-1])
  11.             {
  12.                 continue;
  13.             }
  14.             for(int j=i+1;j<nums.size();j++)
  15.             {
  16.                 long long tmp2=tmp1-nums[j];
  17.                 if(j!=i+1&&nums[j]==nums[j-1])
  18.                 {
  19.                     continue;
  20.                 }
  21.  
  22.                 int left=j+1;
  23.                 int right=nums.size()-1;
  24.                 while(left<right)
  25.                 {
  26.                     if(tmp2==nums[left]+nums[right])
  27.                     {
  28.                         if((left!=j+1&&nums[left]==nums[left-1])||(right!=nums.size()-1&&nums[right]==nums[right+1]))
  29.                         {
  30.                             if(nums[left]==nums[left-1])left++;
  31.                             if(nums[right]==nums[right+1])right--;
  32.                             continue;
  33.                         }
  34.                         ret.push_back({nums[i],nums[j],nums[left],nums[right]});
  35.                         left++;
  36.                         right--;
  37.                     }
  38.                     else if(tmp2>nums[left]+nums[right])
  39.                     {
  40.                         left++;
  41.                     }
  42.                     else if(tmp2<nums[left]+nums[right])
  43.                     {
  44.                         right--;
  45.                     }
  46.                 }
  47.             }
  48.         }
  49.         return ret;
  50.     }
  51. };

八、有效三角形的个数【做题链接】

图8.1        题目描述 

  1. class Solution {
  2. public:
  3.     int triangleNumber(vector<int>& nums) {
  4.         if (nums.size() < 3) return 0;
  5.         sort(nums.begin(), nums.end());
  6.         int ret = 0;
  7.         int n = nums.size();
  8.         for (int i = n - 1; i >= 2; --i){//固定住最长的那条边
  9.             int l = 0, r = i - 1;//l,r分别代表两条边
  10.             while (l < r){
  11.                 if (nums[l] + nums[r] > nums[i]){
  12.                     ret += r - l;
  13.                     --r;
  14.                 }else{
  15.                     ++l;
  16.                 }
  17.             }
  18.         }
  19.  
  20.         return ret;
  21.     }
  22. };

总结

本文介绍了一些有关双指针的算法，一些没有描述的在最近就会补上，另外，文中图片不清晰的可以去博主码云查看【点我】

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号