app开发好还是网站开发好,wordpress用qq注册,大理网上商城网站建设,企业域名怎么填写文章目录 双指针算法leetcode题目 双指针算法
双指针算法可以实现对于时间复杂度降一维度#xff0c;使得O(n2)的算法时间复杂度变为O(n) 指针类型 对撞指针快慢指针 对撞指针 一般是用于顺序结构中的#xff0c;也可以称为左右指针#xff0c;从两端向中间移动#xff0c… 文章目录 双指针算法leetcode题目 双指针算法
双指针算法可以实现对于时间复杂度降一维度使得O(n2)的算法时间复杂度变为O(n) 指针类型 对撞指针快慢指针 对撞指针 一般是用于顺序结构中的也可以称为左右指针从两端向中间移动最左、最右向中间逐渐逼近。对撞指针的结束条件一般为leftright 或者 leftright 快慢指针 基本思想为使用两个移动速度不同的指针在数组或者链表等序列结构上移动比如在处理环形链表或者是数组时很有用只要是我们研究的问题涉及到循环往复的情况就可以考虑使用快慢指针的思想快慢指针的实现方式有很多种但是最为经典的是在一次循环中每一次让慢的指针移动一步快的指针移动两步如果成环循环那么两个指针会相遇 leetcode题目
题目链接移动零
class Solution {
public:void moveZeroes(vectorint nums) { //这是数组划分的题目我们使用双指针的方式来解决//cur0 dest-1 dest指向的是最后一个不为0的数//移动cur查找是否有nums[cur]0 那么 与nums[dest] 交换使得//[0,dest] [dest1,cur-1] [cur,n-1]//数组分为上述三部分第一部分为非零部分 第二部分为0部分第三部分为未处理的部分//我们将非零部分找到之后就放在当前非零数组的最后一个元素之后的位置这样就可以实现分块for(int cur0,dest-1;curnums.size();cur){if(nums[cur]){//如果不为0swap(nums[dest],nums[cur]);}}}
};为什么是swap(nums[dest],nums[cur])这是因为我们规定的是dest位置是已处理区域的最后一个非零元素我们发现在未处理区域cur之后发现非零元素将dest得到最后一个元素的后一个位置进行交换自然实现了0已处理的零区域与nums[cur]的移动
题目描述复写零 class Solution {
public:void duplicateZeros(vectorint arr) {//对于数组的元素进行处理我们使用双指针//因为复写遇到0要复写0所以从前向后的双指针不行我们使用从后向前指针这样就不会造成数据被覆盖//从后向前进行双指针我们首先要确定的是开始判断是否复写的起始位置//起始位置的确定就是复写完毕之后的数组最后一个元素在原先数组中的下标位置//我们使用双指针进行判断找到确定的位置//先找到最后一个位置//找到位置之后可能会有种可能nums[dest]0 所以我们将这种可能避免int cur0,dest-1; //cur比dest多1实际上就是先cur然后进行判断while(curarr.size()){if(arr[cur]){dest;}else{dest2;}if(destarr.size()-1){break;}cur;}coutarr[cur]endl;//处理边界问题dest可能大于arr.size()-1if(destarr.size()){arr[arr.size()-1] 0;dest-2;cur--;}//开始复写 从后向前while(cur0){if(arr[cur]){//如果不为0arr[dest]arr[cur];cur--;dest--;}else{//为0 复写arr[dest]arr[cur];arr[--dest]arr[cur];--dest;--cur;}}}
};题目描述快乐数 class Solution {
public://得到每一位数字的平方和int func(int n){int ans0;while(n){ans(n%10)*(n%10);nn/10;}return ans;}bool isHappy(int n) {//根据题意所知不管如何都会形成一个循环//根据循环我们知道之前判断循环链表的做法快慢指针的形式//slow和fast都是指向经过平方之后的数字来代替指针 //slow走一步平方一次fast平方两次//实现平方的函数coutfunc(100)endl;//检验func函数int slown;int fastn;while(1){//直到相等才停止slowfunc(slow);fastfunc(fast);fastfunc(fast);if(slowfast){break;}}if(slow1){return true;}else{return false;}//return true;}
};题目描述盛最多水的容器 class Solution {
public:int maxArea(vectorint height) {//使用双指针的算法来解决//在两边设置指针移动较小的哪一方指针然后计算此时的体积不断的移动直到相遇int left0,rightheight.size()-1,ans0;while(leftright){//先得到此时的体积int v(right-left)*min(height[left],height[right]);ansmax(v,ans);if(height[right]height[left]){left;}else{right--;}}return ans;}
}题目描述有效三角形的个数 class Solution {
public:int triangleNumber(vectorint nums) {sort(nums.begin(),nums.end());int ans0;for(int inums.size()-1;i;i--){int targetnums[i];int left0,righti-1;while(leftright){if(nums[left]nums[right]target){//满足三角形ansright-left;right--;//left;}else{left;}}}return ans;}
};利用数组元素的单调性先确定一个元素然后使用双指针判断当前三者是否符合三角形如果符合根据单调性left左边的所有都符合所以ansright-left,然后向左移动right,如果不符合那么向右移动left一直判断一直ansright-left 直到leftright 更换下一位c最后循环操作返回ans
题目描述和为s的两个数字 class Solution {
public:vectorint twoSum(vectorint nums, int target) {//因为是 递增的数组 //我们利用双指针算法来解决该问题 利用单调性进行优化vectorint v;int left0,rightnums.size()-1;while(leftright){if(nums[left]nums[right]target){left; //说明当前最大值加上最小值还是小于target}else if(nums[left]nums[right] target){v.push_back(nums[left]);v.push_back(nums[right]);return v;}else{right--;}}return v;}
};题目概述三数之和 class Solution {
public:vectorvectorint threeSum(vectorint nums) {sort(nums.begin(),nums.end());//进行排序然使用双指针算法先确定一个数字然后移动另外两个指针进行加减vectorvectorint vv;for(int i0;inums.size();){if(nums[i]0) break;int lefti1,rightnums.size()-1;while(leftright){int sumnums[left]nums[right];int target-nums[i];if(sumtarget){vectorint v;v.push_back(nums[i]);v.push_back(nums[left]);v.push_back(nums[right]);//找到一次之后对于相邻重复的元素进行跨越vv.push_back(v);//去重操作 left 和 rightleft,right--;while(leftright nums[left] nums[left-1]) left;while(leftright nums[right] nums[right1]) right--;//防止越界}else if(sumtarget){right--;}else {left;}}//去重操作 ii;while(inums.size() nums[i] nums[i-1]) i;}return vv;}
};题目描述四数之和 class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {//先固定一个数a然后剩余三个数字用三数之和 的内容来解决sort(nums.begin(),nums.end());vectorvectorint vv;for(int i0;inums.size();){int anums[i];for(int ji1;jnums.size();){//三数之和的内容int numtarget-a;int leftj1,rightnums.size()-1;while(leftright){int sumnums[left]nums[right];long t(long)num-nums[j];if(sumt){right--;}else if(sumt){left;} else{vv.push_back({nums[i],nums[j],nums[left],nums[right]});//加入vector后处理重复问题 left 和 rightleft, right--;while(leftright nums[left] nums[left-1]) left;while(leftright nums[right] nums[right1]) right--;}}//去重处理 jj;while(jnums.size() nums[j] nums[j-1]) j;}i;while(inums.size() nums[i] nums[i-1]) i; }return vv;}
};总结 双指针的使用场景有很多种使用对撞指针还是快慢指针是根据题意分析的如果成环我们就使用快慢指针双指针的算法是根据暴力算法的优化得到的通过省去不必要的迭代来实现优化。
