双指针入门
- 双指针
- 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(vector<int>& nums) {
for(int i = 0,j = 0;j<nums.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(vector<int>& arr) {
for(int i = 0;i<arr.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(vector<int>& 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++;
else
j--;
}
return ans;
}
};
来看效果：
过啦！！！（还存在改进空间）
经过这四道题目的洗礼，我大概对双指针有了初步印象，接下来我会继续努力！！！
