算法专题1：双指针算法和简单例题
·
目录
1.双指针算法详解
常⻅的双指针有两种形式，⼀种是对撞指针，⼀种是左右指针。
对撞指针：⼀般⽤于顺序结构中，也称左右指针。
- 对撞指针从两端向中间移动。⼀个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼近。
-
对撞指针的终⽌条件⼀般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：
-
1.left == right （两个指针指向同⼀个位置）
-
2.left > right （两个指针错开）
快慢指针：⼜称为⻳兔赛跑算法，其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。
- 这种⽅法对于处理环形链表或数组⾮常有⽤。
- 其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使⽤快慢指针的思想。
快慢指针的实现⽅式有很多种，最常⽤的⼀种就是：
- 在⼀次循环中，每次让慢的指针向后移动⼀位，⽽快的指针往后移动两位，实现⼀快⼀慢。
2.例题与解析
1.移动零（easy）
「数组分两块」是⾮常常⻅的⼀种题型，主要就是根据⼀种划分⽅式，将数组的内容分成左右两部分。这种类型的题，⼀般就是使⽤「双指针」来解决。
1.题目链接：283.移动零
2.题目描述：
给定⼀个数组
nums
，编写⼀个函数将所有
0
移动到数组的末尾，同时保持⾮零元素的相对顺
序。
请注意 ，必须在不复制数组的情况下原地对数组进⾏操作。
⽰例 1:
输⼊:
nums = [0,1,0,3,12]
输出:
[1,3,12,0,0]
⽰例 2:
输⼊:
nums = [0]
输出:
[0]
3.解法（快排的思想：数组划分区间-数组分两块）：
算法思路：
在本题中，我们可以⽤⼀个
cur
指针来扫描整个数组，另⼀个
dest
指针⽤来记录⾮零数序列
的最后⼀个位置。根据
cur
在扫描的过程中，遇到的不同情况，分类处理，实现数组的划分。
在
cur
遍历期间，使
[0, dest]
的元素全部都是⾮零元素，
[dest + 1, cur - 1]
的元素全是零。
算法流程：
a.
初始化
cur = 0
（⽤来遍历数组），
dest = -1
（指向⾮零元素序列的最后⼀个位置。因为刚开始我们不知道最后⼀个⾮零元素在什么位置，因此初始化为 -1
）
b.
cur
依次往后遍历每个元素，遍历到的元素会有下⾯两种情况：
i.
遇到的元素是
0
，
cur
直接
++
。因为我们的⽬标是让
[dest + 1, cur - 1]
内的元素全都是零，因此当 cur
遇到
0
的时候，直接
++
，就可以让
0
在
cur - 1的位置上，从⽽在 [dest + 1, cur - 1]
内；
ii.
遇到的元素不是
0 ，
dest++
，并且交换
cur
位置和
dest
位置的元素，之后让cur++ ，扫描下⼀个元素。
•
因为
dest
指向的位置是⾮零元素区间的最后⼀个位置，如果扫描到⼀个新的⾮零元素，那么它的 位置应该在 dest + 1
的位置上，因此
dest
先⾃增
1
；
•
dest++
之后，指向的元素就是
0
元素（因为⾮零元素区间末尾的后⼀个元素就是0 ），因此可以交换到
cur
所处的位置上，实现
[0, dest]
的元素全部都是⾮零元素， [dest + 1, cur - 1]
的元素全是零。
代码：
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]);
}
};算法总结：
这个⽅法是往后我们学习「快排算法」的时候，「数据划分」过程的重要⼀步。如果将快排算法拆
解的话，这⼀段⼩代码就是实现快排算法的「核⼼步骤」。
2.复写零
1.题目链接：1089.复写零
2.题目描述：
给你⼀个⻓度固定的整数数组
arr
，请你将该数组中出现的每个零都复写⼀遍，并将其余的元素向右平移。
注意：请不要在超过该数组⻓度的位置写⼊元素。请对输⼊的数组就地进⾏上述修改，不要从函数返回任何东西。
⽰例 1：
输⼊：
arr = [1,0,2,3,0,4,5,0]
输出：
[1,0,0,2,3,0,0,4]
解释：
调⽤函数后，输⼊的数组将被修改为：
[1,0,0,2,3,0,0,4]
3.解法（原地复写-双指针）：
算法思路：
如果「从前向后」进⾏原地复写操作的话，由于
0
的出现会复写两次，导致没有复写的数「被覆
盖掉」。因此我们选择「从后往前」的复写策略。
但是「从后向前」复写的时候，我们需要找到「最后⼀个复写的数」，因此我们的⼤体流程分两
步：
i.
先找到最后⼀个复写的数；
ii.
然后从后向前进⾏复写操作。
算法流程：
a.
初始化两个指针
cur = 0
，
dest = 0
；
b.
找到最后⼀个复写的数：
i.
当
cur < n
的时候，⼀直执⾏下⾯循环：
•
判断
cur
位置的元素:
◦
如果是
0
的话，
dest
往后移动两位；
◦
否则，
dest
往后移动⼀位。
•
判断
dest
时候已经到结束位置，如果结束就终⽌循环；
•
如果没有结束，
cur++
，继续判断。
c.
判断
dest
是否越界到
n
的位置：
i.
如果越界，执⾏下⾯三步：
1.
n - 1
位置的值修改成
0
；
2.
cur
向移动⼀步；
3.
dest
向前移动两步。
d.
从
cur
位置开始往前遍历原数组，依次还原出复写后的结果数组：
i.
判断
cur
位置的值：
1.
如果是
0
：
dest
以及
dest - 1
位置修改成
0
，
dest -= 2
；
2.
如果⾮零：
dest
位置修改成
0
，
dest -= 1
；
ii.
cur--
，复写下⼀个位置。
代码：
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int i = 0;
int j = -1;
int sz = arr.size();
while(j < sz - 1){
if(arr[i])
j++;
else
j += 2;
if(j < sz - 1)
i++;
}
if(j == sz){
arr[j-1] = 0;
i--;
j -= 2;
}
while(i >= 0){
if(arr[i])
arr[j--] = arr[i--];
else{
arr[j] = arr[j-1] = 0;
i--;
j -= 2;
}
}
}
};3.快乐数（medium）
1.题目链接：202.快乐数
2.题目描述：
编写⼀个算法来判断⼀个数
n
是不是快乐数。
「快乐数」 定义为：
◦
对于⼀个正整数，每⼀次将该数替换为它每个位置上的数字的平⽅和。
◦
然后重复这个过程直到这个数变为 1，也可能是⽆限循环但始终变不到
1
。
◦
如果这个过程 结果为
1
，那么这个数就是快乐数。
◦
如果
n
是 快乐数 就返回
true
；不是，则返回
false
。
⽰例 1：
输⼊：
n = 19
输出：
true
解释：
19 -> 1 * 1 + 9 * 9 = 82
82 -> 8 * 8 + 2 * 2 = 68
68 -> 6 * 6 + 8 * 8 = 100
100 -> 1 * 1 + 0 * 0 + 0 * 0 = 1
⽰例 2：
输⼊：
n = 2
输出：
false
解释：（这⾥省去计算过程，只列出转换后的数）
2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16
往后就不必再计算了，因为出现了重复的数字，最后结果肯定不会是
1。
3.题目分析：
为了⽅便叙述，将「对于⼀个正整数，每⼀次将该数替换为它每个位置上的数字的平⽅和」这⼀个
操作记为
x
操作；
题⽬告诉我们，当我们不断重复
x
操作的时候，计算⼀定会「死循环」，死的⽅式有两种：
▪
情况⼀：⼀直在
1
中死循环，即
1 -> 1 -> 1 -> 1......
▪
情况⼆：在历史的数据中死循环，但始终变不到
1
由于上述两种情况只会出现⼀种，因此，只要我们能确定循环是在「情况⼀」中进⾏，还是在「情
况⼆」中进⾏，就能得到结果。
简单证明：
a.
经过⼀次变化之后的最⼤值
9^2 * 10 = 810
(
2^31-1=2147483647
。选⼀个更⼤的最⼤ 9999999999
)，也就是变化的区间在
[1, 810]
之间；
b.
根据「鸽巢原理」，⼀个数变化
811
次之后，必然会形成⼀个循环；
c.
因此，变化的过程最终会⾛到⼀个圈⾥⾯，因此可以⽤「快慢指针」来解决。
4.解法（快慢指针）：
算法思路：
根据上述的题⽬分析，我们可以知道，当重复执⾏
x
的时候，数据会陷⼊到⼀个「循环」之中。⽽「快慢指针」有⼀个特性，就是在⼀个圆圈中，快指针总是会追上慢指针的，也就是说他们总会相遇在⼀个位置上。如果相遇位置的值是 1
，那么这个数⼀定是快乐数；如果相遇位置不是
1的话，那么就不是快乐数。
补充知识：如何求⼀个数 n 每个位置上的数字的平⽅和。
a.
把数
n
每⼀位的数提取出来：
循环迭代下⾯步骤：
i.
int t = n % 10
提取个位；
ii.
n /= 10
⼲掉个位；
直到
n
的值变为
0
；
b.
提取每⼀位的时候，⽤⼀个变量
tmp
记录这⼀位的平⽅与之前提取位数的平⽅和
▪
tmp = tmp + t * t
代码：
class Solution
{
public:
bool isHappy(int n)
{
string s;
set<int> se;
do
{
if(n != 1)
se.insert(n);
s = (to_string(n));
n = 0;
for(int i = 0;i < s.size();i++)
{
n += (s[i] - '0') * (s[i] - '0');
}
if(se.count(n))
return false;
}while(n != 1);
return true;
}
};4.盛水最多的容器（medium）
1.题目链接：11.盛水最多的容器
2.题目描述：
给定⼀个⻓度为
n
的整数数组 height 。有
n
条垂线，第 i 条线的两个端点是
(i, 0)
和
(i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的⽔。返回容器可以储存的最⼤⽔量。
说明：你不能倾斜容器。
⽰例 1：
输⼊：
[1,8,6,2,5,4,8,3,7]
输出：
49
解释：图中垂直线代表输⼊数组
[1,8,6,2,5,4,8,3,7]
。在此情况下，容器能够容纳⽔（表⽰为蓝⾊部分）的最⼤值为 49
。
3.解法（对撞指针）：
算法思路：
设两个指针
left
，
right
分别指向容器的左右两个端点，此时容器的容积 :
v = (right - left) * min( height[right], height[left])
容器的左边界为
height[left]
，右边界为
height[right]
。
为了⽅便叙述，我们假设「左边边界」⼩于「右边边界」。
如果此时我们固定⼀个边界，改变另⼀个边界，⽔的容积会有如下变化形式：
◦
容器的宽度⼀定变⼩。
◦
由于左边界较⼩，决定了⽔的⾼度。如果改变左边界，新的⽔⾯⾼度不确定，但是⼀定不会超过右边的柱⼦⾼度，因此容器的容积可能会增⼤。
◦
如果改变右边界，⽆论右边界移动到哪⾥，新的⽔⾯的⾼度⼀定不会超过左边界，也就是不会超过现在的⽔⾯⾼度，但是由于容器的宽度减⼩，因此容器的容积⼀定会变⼩的。
由此可⻅，左边界和其余边界的组合情况都可以舍去。所以我们可以
left++
跳过这个边界，继续去判断下⼀个左右边界。
当我们不断重复上述过程，每次都可以舍去⼤量不必要的枚举过程，直到
left
与
right
相遇。期间产⽣的所有的容积⾥⾯的最⼤值，就是最终答案。
代码：
class Solution
{
public:
int maxArea(vector<int>& height)
{
int left = 0;
int right = height.size() - 1;
int capM = 0;
while(left < right)
{
int cap = ((height[left] < height[right] ? height[left] : height[right]) * (right - left));
if(cap > capM)
capM = cap;
if(height[left] < height[right])
left++;
else
right--;
}
return capM;
}
};结尾：
感谢您的阅读，下篇文章会展示双指针较难的题目和解析，敬请期待。
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
17
0- 0
已为社区贡献10条内容
所有评论(0)