盛水最多的容器与快乐数

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