三、盛水最多的容器
给定一个长度为n的整数数组height。有n条垂线，第i条线的两个端点是(i, 0)和(i, height[i])。
找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
这题的暴力解法非常简单，属于有点基础都能做。
当然，还是会详细写一下。
首先容器的体积公式应该是常识，V=H×W，用容器的宽度乘高度。
为了方便记录宽度，需要用到两层循环。
每次遍历，算出所有的容积，依次比较，直到循环结束，留下的值就是最大容积。
代码：
class Solution { public int maxArea(int[] height) { int max=0; for(int i=0;i<height.length;i++){ for(int j=1;j<height.length;j++){ int hei=Math.min(height[i],height[j]); int v=(j-i)*hei; max=Math.max(max,v); } } return max; } }这个代码虽然正确，但是在力扣上不通过。因为时间复杂度太高了。
不过，可以基于这个思路再想个更优的解法。
既然都需要遍历一次，不如单独拎出一个区间研究一下。
我们把指针定位在左右两端，算出这个位置的容积。再选择其中一个向内移动。
把 j 固定住，i 向右移动。
此时，发现了两种情况。
第一种，[ i ] 小于 [ j ]，高度和宽度同时减小，容积减小。
第二种，[ i ] 大于 [ j ]，高度不变，宽度减小，容积减小。
我们要的是最大容积，所以比较后，元素小的位置可以直接跳过，不需要进行计算。
这个题目核心思路就出来了。
指针由两侧向中间移动，等到循环结束时，存在变量里的值即为最大容积。
代码：
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]){ right--; }else{ left++; } } return ret; } }四、快乐数
编写一个算法来判断一个数n是不是快乐数。
「快乐数」定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
- 如果这个过程结果为1，那么这个数就是快乐数。
如果n是快乐数就返回true；不是，则返回false。
看看这两个例子快不快乐。
先看第一个 n = 19 。
第一个定义是啥意思？就是说，原本 19 的位置替换为 1²+9²=82。
然后依次继续替换，若是最后变成1的循环，则为快乐数。
所以第一个N为快乐数。
再看看第二个 n=2。
经历第N次后并没有循环到最开始的值，所以第二个N不是快乐数。
那么问题来了，现在知道19是快乐数，可是怎么验证？
这两个图示结构看着是不是很像链表，而链表里有一个算法题是判断链表是否成环。
我们可以借鉴这个题的思路，把 1 看成是链表的标记点，若两个链表其中一个值分别为 1 ，则说明链表成环。
有了方向接下来就很好做了。
但是，新的问题又来了，用什么方法判断一定会过标记点？
各位应该都做过不少题目，这类题最容易想到的就是快慢双指针。
既然成环了，那么快慢指针一定会在某个位置相遇。
但是这里没有数组，用什么当做指针？
其实，稍微思考一下不难发现，这东西很像链表，可以拿它每个替换的平方和作为指针。
于是，代码就写出来了。
这部分代码用来计算平方和，n 小于0 时循环结束。
这部分是判断是否成环主体。
代码：
class Solution { public int bitSum(int 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(fast != slow){ slow=bitSum(slow); fast=bitSum(bitSum(fast)); } return slow == 1; } }
