我爱学算法之 —— 感受双指针带来的快感（上）
前言：
欢迎来到我爱学算法系列，从现在开始我们就开始学习算法。
首先来学习 双指针 算法（这里通过一些习题，再实践中锻炼自己的思维，提升自己的算法能力）。
一、移动0
题目链接：283. 移动零 - 力扣（LeetCode）
题目描述：
题目要求我们把所有的
0元素都移动到数组的末尾，并且要保持其他非0元素的相对位置。（并且要求我们不复制数组，在原数组上进行操作）
算法解析：
对于这道题（以至于，数组划分 这一类题，我们都可以使用双指针算法来做）
思路：
使用两个整数（模拟指针）dest 和cur ，在遍历数组的同时，将数组划分成多个区域，进行数据操作即可。
dest指向已经处理完的数据区间中非0元素的最后一个数据（初始为-1）
cur指向 已经处理完的数据区间的最后一个数据（初始为-1）
这样，应该数组就被我们划分成了三个区间，分别是[0,dest] 、[dest+1,cur] 和[cur+1,n]
分析：
起始：
dest= -1 ，cur= 0dest指向非零元素的最后一个（起始为-1）；遍历过程：
cur遍历数组，遇到0元素直接++，遇到非0元素，与dest的后一个元素交换，然后dest和cur都++；
代码实现：
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int dest = -1, cur = 0;
while(cur<nums.size())
{
if(nums[cur]!=0)
{
swap(nums[dest+1],nums[cur]);
dest++;
cur++;
}
else
{
cur++;
}
}
}
};
二、复写0
题目描述：
进行复写0 ，非0 元素就复写一次，0 元素复写两次，并且要在原数组上进行操作。
算法解析：
dest指针： 指向已经复写位置的最后一个元素
cur指针： 指向已经复写位置的最后一个元素
思路：
1：先找到需要复写的最后一个元素（如果从前向后进行复写，会将没有进行复写的数据覆盖掉，所以只能从后向前进行复写）；
2：处理越界的情况（如果最后一个复写的是
0可能会出现访问越界的情况，这里需要进行特殊处理）；3：从后向前进行复写操作。
分析：
正常情况：没有边界情况，正常进行复写；
特殊情况：需要先处理边界情况，再进行复写。
这里就以特殊情况为例，进行分析：
代码实现：
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
//先找到需要复写的最后一个节点
int dest, cur;
int n = arr.size();
for(dest = -1,cur = 0;dest<n;cur++)
{
if(arr[cur] )
{
dest++;
}
else
{
dest+=2;
}
if(dest>=n - 1)
{
break;
}
}
//处理边界情况
if(dest == n)
{
arr[n-1] = 0;
dest-=2;
cur--;
}
//从后向前进行复写
while(cur>=0)
{
if(arr[cur])
{
arr[dest--] = arr[cur--];
}
else
{
arr[dest--] = 0;
arr[dest--] = 0;
cur--;
}
}
}
};
三、快乐数
题目描述：
判断一个数是不是快乐数，（快乐数的判断，一个数每一次变成它每一位数的平方和；如果最后变成1 就是快乐数）。
算法解析：
双指针，
fast和slow
看到这里，可能会有些疑惑，这个题跟双指针有啥关系呢？ 而且还是快慢双指针；我知道你很急，但你先别急，接着向下看
对于一个数，我们先来看一下它的变化过程
通过观察，我们能发现，无论是不是快乐数，最后都会陷入到一个循环当中去；唯一的区别就是，快乐数最后陷入到了只有1 的循环，而不是快乐数变不到1 。
所以，我们就从这里下手，（梦回学习数据结构——链表，做判断循环链表算法题的时候 【链表】算法题（二） ----- 力扣/牛客_力扣链表题-CSDN博客）。
思路：
快慢指针，判断链表是否有环，并且找到环的起始节点；
这里我们就拿来寻找一个数在变换过程在陷入循环时的值，如果这个值等于1 ，就代表这个数是快乐数；否则就不是。
代码实现：
class Solution {
public:
int func(int n)
{
int ret=0;
while(n)
{
int x= n%10;
ret+=x*x;
n/=10;
}
return ret;
}
bool isHappy(int n) {
int slow = n;
int fast = func(n);
while(fast!=slow)
{
fast = func(func(fast));
slow = func(slow);
}
if(slow == 1)
{
return true;
}
else
{
return false;
}
}
};
四、盛水最多的容器
题目描述：
给定一个数组，根据数组内容，我们需要判断盛水最多的容器（就是这两个值和这两个值的位置，形成的一块区域，像上图所示）；我们要找出盛水最多，也就是体积最大的容器的体积。
算法解析：
第一次看到这个题，丝毫没有思路（可能会使用暴力解法，但是时间复杂度为o(n^3))；不用着急，双指针带你来KO这个题。
首先，抛开这个题，我们先来看一个线性单调关系：
了解到这种单调关系，我们应用到这个题当中，我们就不用再进行多余的一些判断了。
思路：
我们只需从两边开始遍历数组，并求出这时的体积（记录最大的体积）；然后移动两个值中较小的那个即可。
题目分析：
代码实现：
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0;
int right = height.size()-1;
int max_v = 0;
while(left<right)
{
int high = height[left];
if(height[right]<high)
{
high = height[right];
}
int v = (right-left)*high;
if(v>max_v)
{
max_v = v;
}
if(height[left]<height[right])
{
left++;
}
else
{
right--;
}
}
return max_v;
}
};
我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws
原文地址：https://blog.csdn.net/LH__1314/article/details/143955965
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！