阅读量:3
目录
双指针（利用数组下标来充当指针）：
常见的双指针有两种形式，一种是对撞指针，一种是快慢指针。
对撞指针：一般用于顺序结构中，也称左右指针。
- 对撞指针从两端向中间移动。一个指针从最左端开始，另一个从最右端开始，然后逐渐往中间逼近。
- 对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：
- left == right （两个指针指向同⼀个位置）
- left > right （两个指针错开）
快慢指针：又称为龟兔赛跑算法，其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。
这种方法对于处理环形链表或数组非常有用。
其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使用快慢指针的思想。
快慢指针的实现方式有很多种，最常用的一种就是：
- 在一次循环中，每次让慢的指针向后移动一位，而快的指针往后移动两位，实现一快一慢。
一、移动零
「数组分两块」是非常常见的一种题型，主要就是根据一种划分方式，将数组的内容分成左右两部分。这种类型的题，一般就是使用「双指针」来解决。
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] 的元素全是零，[cur, n-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] 的元素全是零。
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.题目链接：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]示例 2：
输入：arr = [1,2,3] 输出：[1,2,3] 解释：调用函数后，输入的数组将被修改为：[1,2,3]
3.解法（原地复写 - 双指针
）
🌴算法思路：
如果「从前向后」进行原地复写操作的话，由于 0 的出现会复写两次，导致没有复写的数「被覆盖掉」。因此我们选择「从后往前」的复写策略。但是「从后向前」复写的时候，我们需要先找到「最后一个复写的数」，因此我们的大体流程分两步：
- 先找到最后一个复写的数；
- 然后从后向前进行复写操作。
🌴算法流程：
a. 初始化两个指针 cur = 0 ， dest = -1 ；
b. 找到最后一个复写的数：
i. 当 cur < n 的时候，一直执行下面循环：
• 判断 cur 位置的元素:
- 如果是 0 的话， dest 往后移动两位；
- 否则， dest 往后移动一位。
• 判断 dest 是否已经到结束位置，如果结束就终止循环；
• 如果没有结束， cur++ ，继续判断。
c. 判断 dest 是否越界到 n 的位置：
i. 如果越界，执行下面三步：
- n - 1 位置的值修改成 0 ；
- cur 向移动一步；
- dest 向前移动两步。
d. 从 cur 位置开始往前遍历原数组，依次还原出复写后的结果数组：
i. 判断 cur 位置的值：
- 如果是 0 ： dest 以及 dest - 1 位置修改成 0 ， dest -= 2 ；
- 如果非零： dest 位置修改成 cur位置的值 ， dest -= 1 ；
ii. cur-- ，复写下一个位置。
4.算法代码：
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) { arr[n - 1] = 0; cur--; dest -= 2; } //3.从后向前完成复写操作 while(cur >= 0) { if(arr[cur]) { arr[dest--] = arr[cur--]; } else { arr[dest--] = 0; arr[dest--] = 0; cur--; } } } };三、快乐数
1.题目链接：202.快乐数
2.题目描述：
编写一个算法来判断一个数
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 <= n <= 231 - 1
3.题目分析
为了方便叙述，我们将「对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和」这一个操作记为 x 操作；
题目告诉我们，当我们不断重复 x 操作的时候，计算一定会「死循环」，死循环的情况有两种：
- 情况一：一直在 1 中死循环，即 1 -> 1 -> 1 -> 1......
- 情况二：在历史的数据中死循环，但始终变不到 1。
由于上述两种情况只会出现一种，因此，只要我们能确定循环是在「情况一」中进行，还是在「情况二」中进行，就能得到结果。
简单证明：
- 经过一次变化之后的最大值 9^2 * 10 = 810 ( 2^31-1=2147483647 。选一个更大的最大 9999999999 )，也就是变化的区间在 [1, 810] 之间；
- 根据「鸽巢原理（抽屉原理）」，一个数变化 811 次之后，必然会形成一个循环；
- 因此，变化的过程最终会走到一个圈里面，因此可以用「快慢指针」来解决。
4.解法（快慢指针）
🌴算法思路：
根据上述的题目分析，我们可以知道，当重复执行 x 的时候，数据会陷入到一个「循环」之中。
而「快慢指针」有一个特性，就是在一个圆圈中，快指针总是会追上慢指针的，也就是说他们总会相遇在一个位置上。如果相遇位置的值是 1 ，那么这个数一定是快乐数；如果相遇位置不是 1的话，那么就不是快乐数。
🌴补充知识：
如何求一个数 n 每个位置上的数字的平方和。
a. 把数 n 每一位的数提取出来：
循环迭代下面步骤：
- int t = n % 10 （提取个位）；
- n /= 10 （干掉个位）；
直到 n 的值变为 0 ；
b. 提取每一位的时候，用一个变量 tmp 记录这一位的平方与之前提取位数的平方和
- tmp = tmp + t * t
5.算法代码：
class Solution { public: // 返回n这个数每一位的平方和 int bitSum(int n) { int sum = 0; while(n) { int t = n % 10; sum += t * t; n /= 10; } return sum; } bool isHappy(int n) { // 定义慢指针为第一个数，快指针为第二个数 int slow = n, fast = bitSum(n); while(slow != fast) { slow = bitSum(slow);// 每次走一步 fast = bitSum(bitSum(fast));// 每次走两步 } return slow == 1; } };四、盛最多水的容器
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。示例 2：
输入：height = [1,1] 输出：1
3.解法
🌵解法一（暴力求解、会超时）
算法思路：
1、枚举出能构成的所有容器，找出其中容积最大的值。
2、容器容积的计算方式：
- 设两指针 i , j ，分别指向水槽板的最左端以及最右端，此时容器的宽度为 j - i 。由于容器的高度由两板中的短板决定，因此可得容积公式 ： v = (j - i) * min(height[i], height[j])。
算法代码：
class Solution { public: int maxArea(vector<int>& height) { int n = height.size(); int ret = 0; for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { int v = min(height[i], height[j]) * (j - i); ret = max(ret, v); } } return ret; } };🌵解法二（对撞指针）
算法思路：
设两个指针 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, right = height.size() - 1, ret = 0; while(left < right) { int v = min(height[left], height[right]) * (right - left); ret = max(ret, v); // 移动指针 if(height[left] < height[right]) left++; else right--; } return ret; } };