文章目录
- 前言:
- 1.1 移动零
- 1.2 复写零
- 1.3 快乐数
- 最后
前言:
双指针顾名思义就是用两个指针相互配合来解决问题的。这两个指针可以在同一个数组或链表上，也可以在不同的数据结构上。它们既可以同时移动，也可以一快一慢。
作用： 使用双指针可以提高效率，在一次遍历中就可以解决问题，避免了重复遍历和不必要的计算。
1.1 移动零
题目链接： 283.移动零
题目叙述： 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
解题思路： 双指针算法（利用数组下标充当指针）
1. 定义两个指针
cur:从左向右扫描数组，遍历数组。
dest:已经处理的区间内，非零元素的最后一个位置。
2. 两个指针将区间分为3部分
[0,dest]:非零元素
[dest+1,cur-1]:零元素
[cur,n-1]:待处理元素
3. 过程模拟
①让cur指向下标为0的位置
②让dest指向-1的位置（因为dest是非零元素的最后一个位置，刚开始时不知道第一个位置是否为非零元素）
③ 让cur进行扫描，cur会遇到两种情况：零元素和非零元素；
当遇到0元素时，cur++，就可以满足区间[dest+1,cur-1]为零元素
当遇到非零元素时，先让dest++,然后交换cur和dest位置上的值，cur++进行下一个数据的扫描
4. 代码实现
class Solution {
public:
void moveZeroes(vector<int>& nums) {
for(int cur = 0,dest = -1;cur < nums.size();cur++)
{
if(nums[cur])//处理非零元素
swap(nums[++dest],nums[cur]);
}
}
};
1.2 复写零
题目链接：1089.复写零
题目叙述： 给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
解题思路： 先根据“异地”操作，然后优化成双指针下的“就地”操作
1.异地操作
① 定义一个cur指针，指向数组中的第一个元素
②定义一个dest指针，指向开辟数组中最终的位置
③当cur扫描时碰到非零元素，dest位置插入这个非零元素，cur++,dest++(两个指针同时向右挪动一位)
④ 当cur扫描时碰到零元素，dest位置插入0,dest向右再挪动一位插入0；cur++,dest++(两个指针同时向右挪动一位)
⑤ [1,0,2,3,0,4,5,0]
[1,0,0,2,3,0,0,4]
2.就地操作
当我们进行就地操作时，会发现从左向右操作时会覆盖掉数组中原来的数据，所以我们需要从右往左进行操作
从右往左进行操作时就需要首先找到cur指向的最后一个复写的数.
2.1先找到最后一个复写的数
①先判断cur位置的值，为0 ,dest移动2步；不为0，dest移动1步
②移动dest
③判断dest是否为最后一个位置
④cur向下移动一位
2.2 处理边界情况
当我们找最后一个复写的数时会发现dest指向的位置会有两种情况
①判断是否dest > n-1
② 若大于将n-1指向的位置赋0
③ cur--,dest-=2
2.3 "从后向前"完成复写
①保证cur > 0
②如果cur指向的位置不为零，将cur位置的值给dest，cur--,dest--
③如果cur指向的位置为零,将dest位置的值赋0，dest++,再将dest位置的值赋为0；
④cur--,dest--
3.代码实现
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
//1.找到最后一个复写的数
int cur = 0,dest = -1; int n = arr.size();
while(cur < n)
{
if(arr[cur]) dest++;
else dest+=2;
if(dest >= n - 1) break;
cur++;
}
//2.处理边界情况
if(dest > n-1)
{
arr[n-1] = 0;
cur--;
dest-=2;
}
//"从前向后"完成复写
while(cur>=0)
{
if(arr[cur])
{
arr[dest--] = arr[cur--];
}
else
{
arr[dest--] = 0;
arr[dest--] = 0;
cur--;
}
}
}
};
1.3 快乐数
题目链接：202.快乐数
题目叙述： 编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2：
输入：n = 2
输出：false
解题思路： 类似判断链表是否有环->抽象出的链表：判断环里的数是否为1
解法： 快慢双指针
①定义快慢指针
②慢指针每次向后移动一步，快指针每次向后移动两步
③判断相遇时候的值
解题步骤：
1.定义一个函数获取每一位的数字的平方和
2.定义快慢指针 fast 指向第二个数, slow 指向第一个数
3.让slow 走一步，fast 走两步，直到两个相遇为止
4. 判断相遇位置的值
代码实现：
class Solution
{
public:
int Sum(int n)//返回n这个数每一位上的平方和
{
int sum = 0;
while(n)
{
int t = n % 10;
sum += t * t;
n = n / 10;
}
return sum;
}
bool isHappy(int n)
{
int slow = n,fast = Sum(n);
while(slow != fast)
{
slow = Sum(slow);
fast = Sum(Sum(fast));
}
return slow == 1;
}
};
最后
以上三道题就是对双指针算法的初步应用，可以帮助我们初步了解并熟悉双指针算法，欲知后事如何，关注我请听下回分解