【C++算法】双指针
移动零
题目链接：移动零
https://leetcode.cn/problems/move-zeroes/description/
- 算法原理
这类题是属于数组划分、数组分开题型
- 代码步骤：
- 使用cur遍历数组
- 当cur所指的元素等于0时，cur向后面移动
- 当cur所指的元素不等于0时，dest向后面移动，cur所指元素与dest移动后所指的元素交换
- 当cur指向最后一个元素的下一个时，结束。
- 代码展示
class Solution {
public:void moveZeroes(vector<int>& nums) {int dest = -1;for(int cur = 0; cur < nums.size(); ++cur){//如果cur所指的元素非0，交换if(nums[cur] != 0){swap(nums[++dest], nums[cur]);}}}
};复写零
题目链接：
复写零https://leetcode.cn/problems/duplicate-zeros/description/
- 算法原理
- 代码步骤：
- 代码展示
class Solution {
public:void duplicateZeros(vector<int>& arr) {//寻找复写的最后一个元素int cur = 0;int dest = -1;int n = arr.size();//注意arr.sizr()是size_t无符号类型//int(-1)比size_t整数大while(cur < n){if(arr[cur]){++dest;}else{dest += 2;}//注意这个判断条件需要在里面实现//如果在整个循环结束判断，cur的值无法保证if(dest >= n-1) break;cur++;}//特殊情况处理if(dest == n){arr[n - 1] = 0;--cur;dest -= 2;}//进行从右向左的复写操作for(; cur >= 0; --cur){if(arr[cur]){arr[dest--] = arr[cur];}else{arr[dest--] = 0;arr[dest--] = 0;}} }
};快乐数
题目链接：
快乐数https://leetcode.cn/problems/happy-number/submissions/552733314/
- 算法原理
- 代码步骤：
采用快慢双指针的思想：
- 定义快慢双指针
- 设置一个每个位置平方和的函数
- 慢指针每次向后移动一步
- 快指针每次向后移动俩步
- 判断快慢指针相遇的时候的值是否为1即可
- 代码展示
class Solution {
public://计算数每个位置上数字的平方和int SquareSum(int n){int sum =0;while(n > 0){int num = n % 10;sum += num * num;n /= 10;}return sum;}bool isHappy(int n) {int slow = n;int fast = SquareSum(n);while(slow != fast){fast = SquareSum(SquareSum(fast));slow = SquareSum(slow);}if(slow == 1){return true;}else {return false;}}
};盛最多水的容器
题目链接：
盛最多水的容器https://leetcode.cn/problems/container-with-most-water/
- 算法原理
- 代码步骤：
- 记录初始w最大时的初始容积
- left与right二者中较小者向里面移动，寻找比自己大的值
- 找到比自己大的值，记录面积，并与之前的面积比较大小
- 当left与right相遇的时候，结束
- 代码展示
class Solution
{
public:int maxArea(vector<int>& height) {int left = 0;int right = height.size() - 1;//寻找边界的最小值int min = (height[left] < height[right]) ? height[left] : height[right];//起始容积int vmax = min * (right - left);while(left < right){if(height[left] < height[right]){//记录此时的leftint num = left;while(left < right){//比较看是否有比height[left]大的值++left;if(height[num] < height[left]){break;}}}else{//记录此时的leftint num = right;while(left < right){//比较看是否有比height[left]大的值--right;if(height[num] < height[right]){break;}}}min = (height[left] < height[right]) ? height[left] : height[right];int v = min * (right - left);vmax = (v > vmax) ? v : vmax; }return vmax;}
};class Solution {
public:int maxArea(vector<int>& height) {int left = 0, right = height.size() - 1, vmax = 0;while(left < right){int v = min(height[left], height[right]) * (right - left);vmax = max(vmax, v);if(height[left] < height[right]) ++left;else --right;}return vmax;}
};有效三角形个数
题目链接：
有效三角形个数https://leetcode.cn/problems/valid-triangle-number/
- 算法原理
- 代码步骤：
- 对数组进行排序
- 设置三个指针，一个指向最大值，另外俩个形成单调双指针
- 当left + right < max时，个数为right-left，right--
- 当left + right >= max时，个数为0，left++
- 代码展示
class Solution {
public:int triangleNumber(vector<int>& nums) {int n = nums.size();//排序升序sort(nums.begin(), nums.end());int sum = 0;//最大值向前移动while(n >= 2)//确保right不越界{int max = nums[n - 1];int left = 0, right = n - 2;//利用单调性使用双指针while(left < right){if(nums[left] + nums[right] > max){sum += (right - left);right--;}else{left++;}}--n;}return sum;}
};三数之和
题目链接：
三数之后https://leetcode.cn/problems/3sum/
- 算法原理
- 代码步骤：
- 排序
- 固定一个数min(注意当min > 0的时候，也是可以直接结束的)
- 在该数的后面的区间之内，利用单调性使用双指针，快速找到俩个和等于-min的值
- 细节1：不漏数据
- 细节2：去重操作
- 代码展示
class Solution
{
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> vv;//排序sort(nums.begin(), nums.end());int n = nums.size();//固定一个数int min = 0;for(int min = 0; min < n - 2; ++min){//优化if(nums[min] > 0) break;int left = min + 1, right = n - 1;while(left < right){if(nums[left] + nums[right] < -nums[min]){left++;}else if(nums[left] + nums[right] > -nums[min]){right--;}else{//添加数据vv.push_back({nums[min], nums[left], nums[right]});while(left < right && nums[left] == nums[left + 1]){left++;}while(left < right && nums[right] == nums[right - 1]){right--;}if(left < right){left++;right--;}}}while(min < n - 2 && nums[min] == nums[min + 1]){min++;}}return vv;}
};四数之和
题目链接：
四数之和https://leetcode.cn/problems/4sum/description/
- 算法原理
- 代码步骤：
- 代码展示
class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> ret;//排序sort(nums.begin(), nums.end());int n = nums.size();//四数之和for(int minA = 0; minA < n;){long targetA = target - nums[minA];//三数之和for(int minB = minA + 1; minB < n;){long targetB = targetA - nums[minB];int left = minB + 1, right = n - 1;while(left < right){//利用单调性使用双指针if(nums[left] + nums[right] < targetB){left++;}else if(nums[left] + nums[right] > targetB){right--;}else{ret.push_back({nums[minA], nums[minB], nums[left], nums[right]});//left不重while(left + 1 < right && nums[left] == nums[left + 1]){left++;}//right不重while(left < right - 1 && nums[right] == nums[right - 1]){right--;}//不漏if(left < right){left++;right--;}}}//minB不重while(minB + 1 < n && nums[minB] == nums[minB + 1]){minB++;}++minB;}//minA不重while(minA + 1 < n && nums[minA] == nums[minA + 1]){minA++;}++minA;}return ret;}
};