微信如何做网站,腾讯云安装wordpress,seowhy教研室,凡科官网登录双指针-OJ题 移动零#xff08;点击跳转#xff09;原理讲解代码实现 复写零#xff08;点击跳转#xff09;原理讲解代码实现 快乐数#xff08;点击跳转#xff09;原理讲解代码实现 盛最多水的容器#xff08;点击跳转#xff09;原理讲解代码实现 有效三角形的个数… 双指针-OJ题 移动零点击跳转原理讲解代码实现 复写零点击跳转原理讲解代码实现 快乐数点击跳转原理讲解代码实现 盛最多水的容器点击跳转原理讲解代码实现 有效三角形的个数点击跳转原理讲解代码实现 查找总价值为目标值的两个商品点击跳转原理讲解代码实现 三数之和点击跳转原理讲解代码实现 四数之和点击跳转原理讲解代码实现 移动零点击跳转 原理讲解 因此我们定义两个指针
cur遍历数组dest已处理的区间内最后一个非零元素的位置
这样就把数组划分成三块区间 [0 , dest] 、[dest1 , cur-1] 、[cur , size-1] 分别对应 非零元素、零、待处理
具体操作 cur遍历过程中
遇到0元素 cur;遇到非0元素 swap(dest1cur); //swap数组中下标为dest1和cur的元素 dest;cur;
代码实现
void moveZeroes(vectorint nums) {int dest -1;int cur 0;while (cur nums.size()){if (nums[cur])swap(nums[dest], nums[cur]);cur;}
}复写零点击跳转 原理讲解
这道题首先要想到从后向前遍历因为如果从前向后遍历会覆盖掉后面的值较难操作因此 第一步找到最后一个数可以用快慢指针来实现cur指针、dest指针。前者从前向后遍历后者根据前者位置的值走1步或2步具体如下
先判断cur位置的值若cur位置的值非0dest向后移动一步若cur位置的值为0dest向后移动2步判断dest位置是否到了结束的位置cur
代码实现
void duplicateZeros(vectorint arr) {int dest -1;int cur 0;//找到最后一个数while (cur arr.size()){if (arr[cur])dest;elsedest 2;if (dest arr.size() - 1)break;cur;}
//处理特殊情况cur指向的最后一个数是0dest越界if (dest arr.size()){arr[dest - 1] 0;cur--;dest - 2;}
//复写while (cur 0){if (arr[cur])arr[dest--] arr[cur--];else{arr[dest--] 0;arr[dest--] 0;cur--;}}
}快乐数点击跳转 原理讲解 最后一定会成环可以证明用鸽巢原理 因此可以通过判断环的起点是否为1决定返回true还是false
→ 快慢指针 快慢指针有⼀个特性就是在⼀个圆圈中快指针总是会追上慢指针的也就是说他们总会相遇在⼀个位置上。就本题而言如果相遇位置的值是 1 那么这个数⼀定是快乐数如果相遇位置不是 1 那么就不是快乐数。
代码实现
//求x每一位数的平方和int SqSum(int x){int ret 0;while(x){int n x%10;ret n*n;x/10;}return ret;}bool isHappy(int n) {int slow n,fast SqSum(n);//fast不能设成n否则进不了循环while(slow ! fast){slow SqSum(slow);fast SqSum(SqSum(fast));}return slow1;}盛最多水的容器点击跳转 原理讲解
我们首先想到的大概率是两层循环暴力枚举但是复杂度高这道题不能通关
那应该如何解这题呢 首先容器的容积这道题只考虑面积是S h * w h表示高度即height[?] w表示宽度即两条垂线间隔的距离
为了方便叙述我们假设左边边界height[left]小于右边边界height[right]。
如果此时我们固定⼀个边界改变另⼀个边界水的容积会有如下变化形式
容器的宽度w一定变小。由于左边界较小决定了水的高度。①如果改变左边界新的水面高度不确定但是一定不会超过右边的柱子高度因此容器的容积可能会改变可能变大、变小、不变。②如果改变右边界无论右边界移动到哪里新的水面的高度一定不会超过左边界也就是不会超过现在的水面高度但由于容器的宽度减小因此容器的容积⼀定会变小的。
所以我们可以舍去情况②只需要讨论情况①因为我们的目的是求最大的容积
因此我们定义两个指针left和right然后比较height[left] 和 height[right]移动height小的位置的指针循环这个过程期间产生的所有的容积里的最大值就是要return的最终答案
代码实现 int maxArea(vectorint height) {int left 0;int right height.size()-1;int _max 0;while(left right){int tmp (right-left)*min(height[right],height[left]);_max max(_max,tmp);if(height[left] height[right])left;elseright--; }return _max;}有效三角形的个数点击跳转 原理讲解
我们小学五年级都学过三角形的三条边必须满足任意两边之和大于第三边、任意两边之差小于第三边~
假设三角形三条边长度分别为a, b, c 方法① ab c ; ac b ; bc a 方法② 在①的基础上优化先排序a ≤ b ≤ c只需要判断 ab c即可
解法一三层循环暴力枚举 → O(n3)
解法二利用排序后单调性用双指针算法来解决。 → O(n2)
先固定最大的数在最大数的左边区间内用双指针算法快速统计出符合要求的另外两个数: 如果 nums[left] nums[right] nums[max]说明 [left, right - 1] 区间上的所有元素均可以与 nums[right] 构成比nums[max] 大的二元组此时满足条件的有 right - left 种此时 right 位置的元素的所有情况相当于全部考虑完毕 right-- 进入下一轮判断 如果 nums[left] nums[right] nums[max]说明 left 位置的元素是不可能与 [left 1, right] 位置上的任意元素构成满足条件的二元组left 进入下一轮循环 向左移动最大数循环上面的过程
代码实现 int triangleNumber(vectorint nums) {int left,right;int cmax nums.size() - 1;int ret 0;sort(nums.begin(),nums.end());while (cmax 1) {left 0;right cmax-1;while (left right) {if (nums[left] nums[right] nums[cmax]) {ret(right-left);right--; } else {left;}}cmax--;//向左移动最大数}return ret;}查找总价值为目标值的两个商品点击跳转 原理讲解
类比上面《有效三角形的个数》会发现利用单调性同样很香利用对撞指针优化时间复杂度
初始化 left right 分别指向数组的左右两端接下来无非三种情况 price[left] price[right] target说明找到了跳出循环返回即可 price[left] price[right] target说明两数之和大了right– price[left] price[right] target说明两数之和小了left
代码实现 vectorint twoSum(vectorint price, int target) {int left 0,right price.size()-1;vectorint ret;while(left right){if(price[left] price[right] target){ret.push_back(price[left]);ret.push_back(price[right]);break;}else if(price[left] price[right] target)right--;elseleft;}return ret;}或者不需创建vector直接返回 vectorint twoSum(vectorint price, int target) {int left 0,right price.size()-1;while(left right){if(price[left] price[right] target)return {price[left] , price[right]};else if(price[left] price[right] target)right--;elseleft;}return {-1};//注意这里必须return一个数组目的是照顾编译器否则编译不通过}三数之和点击跳转 原理讲解
我们可以利用在两数之和那道题的双指针思想来对暴力枚举做优化
先排序然后固定一个数 a在这个数后面的区间内利用双指针快速找到两个数之和等于 -a 即可
但是要注意的是这道题需要有去重操作~ 除了用set我们可以自己实现
找到一个结果之后 left 和 right 指针要跳过重复的元素当用完⼀次双指针算法之后固定的 a 也要跳过重复的元素。
代码实现 vectorvectorint threeSum(vectorint nums) {sort(nums.begin(),nums.end());int i 0,left,right;vectorvectorint vv;while(i nums.size()-2){if(nums[i] 0)break;//leftrightleft i1;right nums.size()-1;while(left right right nums.size()){if(nums[left] nums[right] -nums[i]){vv.push_back({nums[i],nums[left],nums[right]});left;right--;while(left right right nums.size()nums[left] nums[left-1])left;//left跳过重复元素while(left right right nums.size()nums[right] nums[right1])right--;//right跳过重复元素}else if(nums[left] nums[right] -nums[i])right--;elseleft;}i;while(nums[i] nums[i-1] inums.size()-2)i;//“固定”的数跳过重复元素}return vv; }四数之和点击跳转 原理讲解
这道题和上面的《三数之和》几乎一模一样区别在于多了一层
固定一个数a在这个数 a 的后面区间上利用「三数之和」找到三个数使这三个数的和等于 target - a 即可
代码实现 vectorvectorint fourSum(vectorint nums, int target) {sort(nums.begin(),nums.end());vectorvectorint vv;int i0,j,left,right;while(inums.size()){j i1;while(jnums.size()){left j1;right nums.size()-1;long long aim (long long)target-nums[i]-nums[j];//有些用例不强转会越界while(leftright){int sum nums[left]nums[right];if(sum aim){vv.push_back({nums[i],nums[j],nums[left],nums[right]});left;right--;while(leftright nums[left] nums[left-1])left;while(leftright nums[right] nums[right1])right--;}else if(sum aim)left;elseright--;}j;while(j nums.size() nums[j] nums[j-1])j;}i;while(inums.size() nums[i] nums[i-1])i;}return vv;}
