一级做爰片软件网站,wordpress中医主题,古典网站织梦模板,四川住房和建设厅网站一、移动零
. - 力扣#xff08;LeetCode#xff09; 移动零 该题重要信息#xff1a;1、保持非0元素的相对位置。2、原地对数组进行操作 思路#xff1a;双指针算法 class Solution {
public:void moveZeroes(vectorint nums){int nnums.size();for(int cur…
一、移动零
. - 力扣LeetCode 移动零 该题重要信息1、保持非0元素的相对位置。2、原地对数组进行操作 思路双指针算法 class Solution {
public:void moveZeroes(vectorint nums){int nnums.size();for(int cur0,des-1;curn;cur)if(nums[cur])//如为非零就要与des后面的位置元素进行交换swap(nums[des],nums[cur]);}
}; 二、复写零
. - 力扣LeetCode复写零 该题的重要信息1、不要在超过该数组的长度的位置写入元素就是不要越界2、就地修改就是不能创建新数组。3、不返回任何东西。 思路双指针算法 class Solution {
public:void duplicateZeros(vectorint arr){int cur0,des-1,narr.size();//找最后一个被复写数的位置for(;curn;cur){if(arr[cur])des;elsedes2;if(desn-1)//要让des指向最后一个位置break;}//边界修正if(desn){arr[--des]0;--des;--cur;}//从后往前复写for(;cur0;--cur){if(arr[cur])arr[des--]arr[cur];else{arr[des--]0;arr[des--]0;}}}
}; 三、快乐数
. - 力扣LeetCode快乐数 该题的关键是将正整数变成他的每位数的平方之和有可能会一直循环始终到不了1也有始终是1快乐数
思路快慢双指针算法 以上的两个结论在博主的关于链表带环追击问题的文章里面有分析
顺序表、链表相关OJ题2-CSDN博客
class Solution {
public:int bitsum(int n){ int sum0;while(n){int tn%10;sumt*t;n/10;//最后一位算完后拿掉}return sum;}bool isHappy(int n) {int slown,fastbitsum(n);while(fast!slow){slowbitsum(slow);fastbitsum(bitsum(fast));}return slow1;}
};
四、盛最多水的容器
. - 力扣LeetCode盛最多水的容器 思路1、暴力枚举时间复杂度太高 class Solution {
public:int maxArea(vectorint height){//暴力枚举int nheight.size();int ret0;for(int i0;in;i)for(int ji1;jn;j)retmax(ret,min(height[i],height[j])*(j-i));return ret;}
}; 思路2、双指针对撞算法 class Solution {
public:int maxArea(vectorint height){int left0,rightheight.size()-1,ret0;while(leftright){retmax(ret,min(height[left],height[right])*(right-left));if(height[left]height[right])left;else--right;}return ret;}
};
五、有效三角形的个数
. - 力扣LeetCode有效三角形的个数 思路1升序暴力枚举
思路2升序利用双指针算法 class Solution {
public:int triangleNumber(vectorint nums) {//排序一下sort(nums.begin(),nums.end());//先固定一个数然后用双指针去找比较小的两个数int nnums.size(),ret0;for(int in-1;i2;--i){int left0,righti-1;while(leftright){int sumnums[left]nums[right];if(sumnums[i]) left;else {ret(right-left);--right;} }}return ret;}
}; 六、查找总价格为目标值的两个商品
. - 力扣LeetCode查找总价格为目标值的两个商品 思路1两层for循环找到所有组合去计算
思路2利用单调性使用双指针算法解决问题 class Solution {
public:vectorint twoSum(vectorint price, int target) {int nprice.size();int left0,rightn-1;while(leftright){int sumprice[left]price[right];if(sumtarget) --right;else if(sumtarget) left;else return {price[left],price[right]};}return {1,0};}
};
七、三数之和
. - 力扣LeetCode三数之和 解法1排序暴力枚举set去重
解法2排序双指针 class Solution {
public:vectorvectorint threeSum(vectorint nums){vectorvectorint ret;int nnums.size();//先排序sort(nums.begin(),nums.end());//先固定一个数for(int i0;in;){if(nums[i]0) break;//小优化int target -nums[i];//目标值//定义双指针int lefti1,rightn-1;while(leftright){int sumnums[left]nums[right];if(sumtarget) left;else if(sumtarget) --right;else {ret.push_back({nums[left],nums[right],nums[i]});//插入进去left;--right;//去重while(leftrightnums[left]nums[left-1]) left;//去重要注意边界while(leftrightnums[right]nums[right1]) --right;}}i;while(innums[i]nums[i-1]) i;//去重要注意边界}return ret;}
};
八、四数之和
. - 力扣LeetCode四数之和 解法1排序暴力枚举set去重
解法2排序双指针和上一题基本一样无非就是多固定了一个数 class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint ret;//先进行排序sort(nums.begin(),nums.end());//利用双指针解决int nnums.size();//先固定一个数for(int i0;in;){//再固定一个数for(int ji1;jn;){int leftj1,rightn-1;long long aim(long long)target-nums[i]-nums[j];//确保不超出范围while(leftright){long long sumnums[left]nums[right];if(sumaim) left;else if(sumaim) --right;else {ret.push_back({nums[i],nums[j],nums[left],nums[right]});left;--right;//去重while(leftrightnums[left]nums[left-1]) left;while(leftrightnums[right]nums[right1]) --right;}}//去重j;while(jnnums[j]nums[j-1]) j;}//去重i;while(innums[i]nums[i-1]) i;}return ret;}
};
九、总结
常见的双指针有三种形式前后指针、对撞指针、快慢指针
1、前后指针用于顺序结构一般是两个指针同方向cur指针用来遍历数组des指针将数组进行区域划分。如1、2题 注意事项如果是从前往后遍历要注意dst不能走得太快否则cur还没遍历到一些数就会被覆盖掉必要时候可以根据情况从后往前遍历。
2、快慢指针其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。 这种⽅法对于处理环形链表或数组⾮常有⽤。如第3题以及链表带环的问题 注意事项 其实不单单是环形链表或者是数组如果我们要研究的问题出现循环往复的情况时均可考虑使⽤快慢指针的思想。最常用的就是快指针走两步慢指针走一步。
3、对撞指针一般用于顺序结构。从两端向中间移动。⼀个指针从最左端开始另⼀个从最右端开始然后逐渐往中间逼近。并且常常会用到单调性如4-8题 注意事项对撞指针的终⽌条件⼀般是两个指针相遇或者错开也可能在循环内部找到结果直接跳出循环 如果后面还有关双指针的经典题目博主会继续在这篇更新的
