网站网页设计在哪找,建筑材料价格查询网站,网站技巧,wix和wordpress哪个好目录
1、双指针遍历分割:避免开空间#xff0c;原地处理
2、快慢指针#xff1a;循环条件下的判断
3、左右指针#xff08;对撞指针#xff09;#xff1a;分析具有单调性#xff0c;避免重复计算 双指针又分为双指针遍历分割#xff0c;快慢指针和左右指针
1、双指…
目录
1、双指针遍历分割:避免开空间原地处理
2、快慢指针循环条件下的判断
3、左右指针对撞指针分析具有单调性避免重复计算 双指针又分为双指针遍历分割快慢指针和左右指针
1、双指针遍历分割:避免开空间原地处理
概念核心思想将数组分为两端、已处理的的部分未处理的部分cur遍历数组指向未完成的数组同时处理数组元素。dest指向处理完成的部分。
算法实际操作cur指向第一个待处理的元素。dest指向处理完元素存放的位置根据 cur指向数据的类型进行不同操作。
例题移动零
1089. 复写零 - 力扣LeetCode
class Solution {
public:void moveZeroes(vectorint nums) {int nnums.size();for(int cur0,dest-1;curnums.size();){if(nums[cur]){//非0的顺序不变那么按序处理非0swap(nums[cur],nums[dest]);}cur;}}
};
class Solution {
public:void duplicateZeros(vectorint arr) {int cur0,dest-1,narr.size();while(curn){if(arr[cur]) dest;else dest2;if(destn-1) break;cur;}if(destn){arr[n-1]0;destn-2;cur--;}while(cur0){if(arr[cur]) arr[dest--]arr[cur--];else{arr[dest--]0;arr[dest--]0;cur--;}}}
};
2、快慢指针循环条件下的判断
核心思想经过分析对于存在循环情况的问题我们可以设置快慢指针来处理
.快乐数ss
class Solution {
public:int bitsum(int n){int sum0;while(n){int in%10;n/10;sumi*i;}return sum;}//快慢指针不论是否是快乐数都会进入循环要不循环1为快乐数要不是一堆数依次循环bool isHappy(int n) {int slown,fastbitsum(n);while(slow!1){slowbitsum(slow);fastbitsum(bitsum(fast));if(slowfastslow!1)return false;}return true;}
};
快乐数分析可知必存在循环分为1循环和多个数循环然后利用快慢指针在循环中的前进速率不同若相遇判断循环数为多少即可判断是否是快乐数
3、左右指针对撞指针分析具有单调性避免重复计算
核心思想在暴击解法上利用单调性避免重复计算
11. 盛最多水的容器 - 力扣LeetCode
class Solution {
public:int maxArea(vectorint height) {int nheight.size();int left0,rightn-1;int ret(right-left)*min(height[left],height[right]);//记录最大值while(leftright){if(height[left]height[right]){left;}else{right--;}retmax(ret,(right-left)*min(height[left],height[right]));}return ret;}
};
实现操作定义左右指针left0rightn-1retH*Wleft和right向中间靠近的话w一定减小h只有增大才能实现ret变大。
611. 有效三角形的个数 - 力扣LeetCode
class Solution {
public:void duplicateZeros(vectorint arr) {int cur0,dest-1,narr.size();while(curn){if(arr[cur]) dest;else dest2;if(destn-1) break;cur;}if(destn){arr[n-1]0;destn-2;cur--;}while(cur0){if(arr[cur]) arr[dest--]arr[cur--];else{arr[dest--]0;arr[dest--]0;cur--;}}}
};
暴力枚举三层循环
简化排序后固定两个值——三角形中较大的那两个然后移动较小的那个值变成求在某一有序区间内大于某值的个数。(利用单调性)
LCR 179. 查找总价格为目标值的两个商品 - 力扣LeetCode
class Solution {
public:vectorint twoSum(vectorint price, int target) {int nprice.size();int low0,heightn-1;while(lowheight){if(price[low]price[height]target){low;}else if(price[low]price[height]target){height--;}else{break;}}return {price[low],price[height]};}
};
暴力枚举利用单调性优化类盛水容器
class Solution {
public:vectorvectorint threeSum(vectorint nums) {sort(nums.begin(),nums.end());int nnums.size();vectorvectorint ret;for(int k0;kn-2;){int leftk1,rightn-1;int target-nums[k];while(leftright){if(nums[left]nums[right]target){left;}else if(nums[left]nums[right]target){right--;}else{ret.push_back(vectorint{nums[k],nums[left],nums[right]});left;right--;while(leftrightnums[left]nums[left-1])left;//细节问题不重复同时判断不越界leftrightwhile(leftrightnums[right]nums[right1])right--;}}k;while(kn-2nums[k]nums[k-1])k;}return ret;}
}; 18. 四数之和 - 力扣LeetCode
类上对内两层的暴力改为求目标值
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {int nnums.size();sort(nums.begin(),nums.end());vectorvectorint ret;for(int x0;xn-3;){//固定第一个数for(int kx1;kn-2;){//固定第二个数long long targeti(long long)target-(nums[x]nums[k]);for(int leftk1,rightn-1;leftright;){long long sumnums[left]nums[right];if(sumtargeti){right--;}else if( targetisum){left;}else{ret.push_back(vectorint{nums[x],nums[k],nums[left],nums[right]});left;right--;while(leftrightnums[left]nums[left-1]) left;//注意仅仅找到target去重未找到的话前面那个值未被统计不同去重while(leftrightnums[right]nums[right1]) right--;}}k;while(kn-2nums[k]nums[k-1]) k;}x;while(xn-3nums[x]nums[x-1]) x;}return ret;}
};
