国外设计素材网站,设计页面导航,石家庄便宜网站制作,长春建设网站公司哪家好[双指针] (二) LeetCode 202.快乐数 和 11.盛最多水的容器
快乐数
202. 快乐数 题目解析
(1) 判断一个数是不是快乐数
(2) 快乐数的定义#xff1a;将整数替换为每个位上的和#xff1b;如果最终结果为1#xff0c;就是快乐数
(3) 这个数可能变为1#xff0c;也可能无…[双指针] (二) LeetCode 202.快乐数 和 11.盛最多水的容器
快乐数
202. 快乐数 题目解析
(1) 判断一个数是不是快乐数
(2) 快乐数的定义将整数替换为每个位上的和如果最终结果为1就是快乐数
(3) 这个数可能变为1也可能无限循环。
解题思路
示例1n 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(vectorint 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容器盛水量是由两个高度中短的那个决定的。
细节2height[left] 和 height[right]之间我们需要选择大的那个来跳过包含小的那个高度的所有情况。
