前言
- 对撞指针从两端向中间移动。一个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼
近。 - 对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循
环），也就是： -
- left == right （两个指针指向同一个位置）
-
- left > right （两个指针错开）
快慢指针的实现方式有很多种，最常用的⼀种就是：
- 在一次循环中，每次让慢的指针向后移动一位，而快的指针往后移动两位，实现一快一慢。
1. 快乐数（medium）
题目描述：
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
示例 1：
示例 2：
提示：
2. 解法
思路：
可以把题目中的两种情况当成一种情况来看，就是一直在死循环
- 对于情况一：⼀直在 1 中死循环
- 对于情况二：在历史的数据中死循环，但始终变不到 1
为什么会死循环？
解题方法:
- ProductSum 函数：
- 这个函数计算一个整数的每个位上数字的平方和。
- 通过不断地对整数取模 10 来获取其最后一位数字，然后将其平方并累加到 sum 变量中。
- 每次迭代，整数都通过整除 10 来移除最后一位数字。
- 当整数变为 0 时，函数返回累加的和 sum。
- isHappy 函数：
- 使用“快慢指针”技术来检测循环。
- slow 和 fast 初始时都指向 n。
- slow 每次移动一步，即计算当前数字的平方和。
- fast 每次移动两步，即连续计算两次平方和。
- 如果 n 是一个快乐数，slow 和 fast 最终都会达到 1。
- 如果 n 进入循环，slow 和 fast 会在循环中的某个点相遇（即它们的值相等）。
- 如果 slow 和 fast 相等且等于 1，则 n 是快乐数。
- 算法中使用了 do-while 循环而不是 while 循环，以确保至少执行一次循环体（即至少计算一次ProductSum），即使 slow 和 fast 初始时就相等。
复杂度
C++算法代码：
class Solution {
public:
int ProductSum(int n)
{
int sum = 0;
while(n)
{
int temp = n % 10;
sum += temp*temp;
n /= 10;
}
return sum;
}
bool isHappy(int n) {
int slow = n,fast = n;
// 快慢指针，找环的相遇位置
do
{
slow = ProductSum(slow);
fast = ProductSum(ProductSum(fast));
}while(slow != fast);
// 如果相遇时是 1 就是快乐数
return slow == 1;
}
};
java算法代码：
class Solution
{
public int bitSum(int n) // 返回 n 这个数每⼀位上的平⽅和
{
int sum = 0;
while (n != 0)
{
int t = n % 10;
sum += t * t;
n /= 10;
}
return sum;
}
public boolean isHappy(int n)
{
int slow = n, fast = bitSum(n);
while (slow != fast)
{
slow = bitSum(slow);
fast = bitSum(bitSum(fast));
}
return slow == 1;
}
}
3. 盛水最多的容器（medium）
题目描述：
示例 1：
示例 2：
提示：
4. 解法
解法一（暴力求解)(会超时):
算法思路:
枚举出能构成的所有容器，找出其中容积最大的值。
算法代码：
class Solution {
public:
int maxArea(vector<int>& height) {
int n = height.size();
int ret = 0;
// 两层 for 枚举出所有可能出现的情况
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// 计算容积，找出最⼤的那⼀个
ret = max(ret, min(height[i], height[j]) * (j - i));
}
}
return ret;
}
};
解法二（对撞指针）：
算法思路：
设两个指针 left , right 分别指向容器的左右两个端点,此时容器的容积 : v = (right - left) * min( height[right], height[left])
容器的左边界为height[left],右边界为 height[right] 。
为了方便叙述,我们假设「左边边界」小于「右边边界」. 如果此时我们固定一个边界,改变另一个边界,水的容积会有如下变化形式：
- 容器的宽度⼀定变小
- 由于左边界较小,决定了⽔的⾼度.如果改变左边界,新的水面高度不确定,但是⼀定不会超过右边的柱子高度,因此容器的容积可能会增大.
- 如果改变右边界,无论右边界移动到哪里,新的水面的高度⼀定不会超过左边界,也就是不会超过现在的水面高度,但是由于容器的宽度减小,因此容器的容积⼀定会变小的.
- 由此可见,左边界和其余边界的组合情况都可以舍去.所以我们可以 left++ 跳过这个边界,继续去判断下⼀个左右边界.
当我们不断重复上述过程,每次都可以舍去⼤量不必要的枚举过程,直到 left 与 right 相 遇.期间产生的所有的容积里面的最大值,就是最终答案.
C++ 算法代码：
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;
}
};
Java 算法代码：
class Solution
{
public int maxArea(int[] height)
{
int left = 0, right = height.length - 1, ret = 0;
while (left < right)
{
int v = Math.min(height[left], height[right]) * (right - left);
ret = Math.max(ret, v);
if (height[left] < height[right]) left++;
else right--;
}
return ret;
}
}