深圳企业网站定制公司,朝阳网络 网站建设,别墅室内设计网站,wordpress添加表情双指针入门 双指针283.移动零1089. 复写零202. 快乐数11. 盛最多水的容器Thanks♪(#xff65;ω#xff65;)#xff89;谢谢阅读#xff01;#xff01;#xff01;下一篇文章见#xff01;#xff01;#xff01; 双指针
双指针是非常经典的算法#xff0c;包括但… 双指针入门 双指针283.移动零1089. 复写零202. 快乐数11. 盛最多水的容器Thanks♪(ω)谢谢阅读下一篇文章见 双指针
双指针是非常经典的算法包括但不限于前后双指针快慢双指针特殊双指针。 尤其需要注意的是双指针并不能只局限于指针数组下标过程数据都可以成为“指针”。重要的是能够灵活使用双指针的思想把解题思路捋顺。 下面我们来会会几道双指针的题目
283.移动零
家人们 上连接283.移动零 通过题目发现这并不是一到很复杂的题。主要难点在于不改变数组的相对顺序。 这里我们使用前后双指针逐渐遍历完成操作
首先定义两个数组下标 i j我们赋予他们不同含义 [ 0 i是已经处理过已经没有零的部分 并按相对顺序排好 [i , j] 是零的部分 (j , n) 待处理的部分我们控制 j 来进行整个数组的遍历0 到 i是非零数据。遇到 0 i j 位置互换即可 来看代码类似冒泡排序的过程把零向后挪动
class Solution {
public:void moveZeroes(vectorint nums) {for(int i 0,j 0;jnums.size();j)if(nums[j] ! 0) swap(nums[j],nums[i]);}
};非常简洁的代码。就可以完成我们的操作。来看效果 很好过啦
1089. 复写零
家人们跟上节奏1089. 复写零 这道题与前面的移动零很像但使用的算法细节不同。 这里需要的也是双指针 i j
首先定义两个数组下标 i j赋予他们不同含义 0 到 i 是处理完的部分 i 到 j 是 未处理部分首先使用 i 遍历整个数组j 负责调换未处理的数据将数据后移空出新的零的位置 来看代码
class Solution {
public:void duplicateZeros(vectorint arr) {for(int i 0;iarr.size();i){if(arr[i] 0){for(int j arr.size() - 1 ; j i ; j--){arr[j] arr[j - 1];}i;}}}
};运行效果
202. 快乐数
家人们 继续干202. 快乐数 这道题是比较特殊的一道题我们来看奥 首先看测试用例的 1 9 和 2 可以发现最后都会处于循环这里可以证明一下为什么都会处于循环 假设我们最大数为 99999 99999 那对应的数为 810 相当于 0 到 9999999999 只有 810 个数与之对应所以必然会出现循环。 到这里大家应该也看出这和判断链表是否有环很像使用快慢指针慢指针依次进行一步操作快指针一次两步操作。这里“指针”代指数字。 class Solution {
public://操作函数int getsum(int n ){int sum 0;while(n){int i n % 10;sum i*i;n / 10;}return sum;}bool isHappy(int n) {//初始化int slow n;int fast getsum(n);//进行循环 直到相遇while(slow ! fast){slow getsum(slow);fast getsum(getsum(fast));}//判断一下即可if(slow 1) return true;return false;}
};来看效果 很好 过啦
11. 盛最多水的容器
家人们终于到了最后一题 11. 盛最多水的容器 这道题可谓十分抽象 这里使用前后双指针代我细细到来为什么 首先我们选取前后这一片段然后得到一个体积值。 这时我们可以进行一下分析
如果移动较大这边的指针那长必然减小 高一定不会增加所以不需移动较高这边再来看较小这边移动后不能确定到底是增加还是减少所以需要移动进行遍历
根据这两条规矩我们就可以完成操作来看图解来自 力扣官方题解 这样必然可以得到答案。
class Solution {
public:int maxArea(vectorint height) {int i 0;int j height.size() - 1;// 记录答案值int ans 0;while(i ! j){//求得新的体积int v min(height[i],height[j]) * (j - i);//取最大值ans max(ans,v);// 移动较小的指针if(height[i] height[j])i;elsej--;}return ans;}
};来看效果 过啦还存在改进空间
经过这四道题目的洗礼我大概对双指针有了初步印象接下来我会继续努力
Thanks♪(ω)谢谢阅读
下一篇文章见
