目录
- 前言
- 1. 快乐数（medium）
- 2. 解法
- 3. 盛水最多的容器（medium）
- 4. 解法
- 解法一（暴力求解)(会超时):
- 解法二（对撞指针）：
前言
双指针
常见的双指针有两种形式，一种是对撞指针，⼀种是左右指针。
对撞指针：一般用于顺序结构中，也称左右指针。
- 对撞指针从两端向中间移动。一个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼
近。 - 对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循
环），也就是： -
- left == right （两个指针指向同一个位置）
-
- left > right （两个指针错开）
快慢指针：又称为龟兔赛跑算法，其基本思想就是使用两个移动速度不同的指针在数组或链表等序列
结构上移动。
这种方法对于处理环形链表或数组非常有用。
其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使用快
慢指针的思想。
快慢指针的实现方式有很多种，最常用的⼀种就是：
- 在一次循环中，每次让慢的指针向后移动一位，而快的指针往后移动两位，实现一快一慢。
1. 快乐数（medium）
题目描述：
编写一个算法来判断一个数 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
2. 解法
思路：
可以把题目中的两种情况当成一种情况来看，就是一直在死循环
- 对于情况一：⼀直在 1 中死循环
- 对于情况二：在历史的数据中死循环，但始终变不到 1
为什么会死循环？
题目所给数据范围是小于整型（int）的最大值 231-1=2147483647,这里我们们不难发现最大值的位数是 10，那么我们可以用一个十位数的最大值来变换，即 9999999999，那么它经过变换得到的值就是 92 * 10 = 810 ，那么经过所有变换的结果就会在区间 [1, 810] 之间；
根据【鸽巢原理】，⼀个数变化 811 次之内，必然会在一个循环中有重复。
因此，可以⽤「快慢指针」来解决。
解题方法:
- 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 初始时就相等。
复杂度
时间复杂度: O(logN)
空间复杂度: O(1)
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）
题目描述：
给定一个长度为 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
提示：
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
4. 解法
解法一（暴力求解)(会超时):
算法思路:
枚举出能构成的所有容器，找出其中容积最大的值。
容器容积的计算方式:
设两指针 i , j，分别指向水槽板的最左端以及最右端，此时容器的宽度为j - i
容器的高度由两板中的短板决定，因此可得容积公式︰v = (j - i) * min(height[il, height[j])
算法代码：
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;
}
}
![[LeetCode][LCR170]交易逆序对的总数](https://img-blog.csdnimg.cn/direct/b49e9436390e499a8dcffdbbe629fe6a.png)
