[双指针] (二) LeetCode 202.快乐数 和 11.盛最多水的容器
[双指针] (二) LeetCode 202.快乐数 和 11.盛最多水的容器
快乐数
202. 快乐数
题目解析
(1) 判断一个数是不是快乐数
(2) 快乐数的定义：将整数替换为每个位上的和；如果最终结果为1，就是快乐数
(3) 这个数可能变为1，也可能无限循环。
解题思路
示例1：n = 19；示例2： n = 2
我们发现它们都可以抽象为一种类型：一个环中全都是1，另一个是无限重复的数。
这和经典题目判断链表是否有环几乎是一模一样，解决判断链表是否有环时，我们使用的就是双指针解法。
141. 环形链表
解法：双指针(并不是真正意义上的指针)
定义一个快指针和一个慢指针，快指针走两步，慢指针走一步，最终它们会在同一个点相遇。(大家有能力的可以自己画图证明一下)
看到这里，大家可以尝试一下去实现一下代码，再向后面看下去。
代码实现
class Solution {
public:int getVal(int n){int val = 0;while(n){int tmp = n % 10;val += tmp * tmp;n /= 10;}return val;}bool isHappy(int n) {int fast = getVal(n), slow = n;while(fast != slow){slow = getVal(slow);fast = getVal(getVal(fast));}return slow == 1;}
};
总结
细节1：在循环条件上，我们使用fast != slow，所以一开始我们定义的快慢指针，应该不相同，所以把快指针定义为第二个数(getVal(n))，否则进不去循环。
细节2：返回的是slow == 1，最后相遇的点不一定为1，如示例中，也有可能为4。
细节3：为什么只有这两种情况(无限循环为1，或者无限循环不为1)？为什么没有一直循环下去且不重复这第三种情况？
我们进行一下简单证明：鸽巢原理
100个鸽子巢穴，有101只鸽子，可以得出至少有一个巢穴有两只鸽子。
数据范围是[1, 2 ^ 31 - 1]，也就是 [1, 2147483647]；(约2 * 10 ^ 9)
我们再扩充数据范围为[1, 9999999999] (大于9 * 10 ^ 9)
9999999999 -> 81 * 10 = 810
所以[1, 2 ^ 31 - 1]循环范围为 [1, 810]，即使有一个数经历810次循环后还不重复，但是第811次就会和这范围中的一个数重复。
由此得出，第三种情况不存在。
盛最多水的容器
11. 盛最多水的容器
题目解析
(1) 数组height中存放的是高度
(2) 存水量为长 * 高
(3) 找出最大存水量的容器
解题思路
一开始我们会想到暴力解法：两个循环枚举所有情况，一个一个比大小。
但是有些情况是不需要枚举的，比如一个高是1，其他的情况基本不需要再枚举了(具体情况具体分析)，长度确定情况下，肯定是越高越好。
接下来对暴力枚举进行优化：
我们又发现：存水量 = 长 * 高，即选择不同的下标就是选择不同的高度，所以我们尝试使用双指针。
定义一个指针left 和 指针right：
从同一方向开始，我们发现存水量 = 长 * 高，长可以变大或者变小，高可以变大或者变小：相乘之后结果是变大还是变小，这是不可控制的。
所以我们选择left在下标0处，right在下标height.size-1处。这样长是不断在减小的，高必须要变大才能使存水量变大。
所以在height[left]和height[right]之间需要选择一个更大的数，否则就跳过包含这个情况的所有情况，即为：left++或者right - -。
代码实现
class Solution {
public:int maxArea(vector<int>& height) {int max_area = 0;//h * l = area l：变小 h：变大for(int left = 0, right = height.size()-1; right > left; ){int low = height[left] < height[right] ? height[left] : height[right];max_area = max(max_area, (right - left) * low);if(height[left] < height[right]) left++;else right--;}return max_area;}
};
总结
细节1：容器盛水量是由两个高度中短的那个决定的。
细节2：height[left] 和 height[right]之间，我们需要选择大的那个，来跳过包含小的那个高度的所有情况。