leetCode进阶算法题+解析（三十三）

打广告：Java技术交流群：130031711，欢迎各位踊跃加入。
刷题继续：

完全平方数

题目：给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9.

思路：(刚刚做了个测试，16本身就是完全平方数，而不是4+4+4+4。其实也能理解，不然都是1相加还不用算了呢。)以上都是废话，因为我有看到了使完全平方数的个数最少，是我审题不清，哈哈，咱们继续说：首先我思路是从最大的完全平方数开始算。比如12，最大的完全平方数是3，然后9剩下3，只能是三个1，这样就是4。 然后其次大的是2,4剩下8又分了两个四，结果就是3.3比4小所以选择3。同理，13最大完全平方数3的平方9。抛出了9继续算。除了本身是完全平方外，剩下如果有两个组成了就直接返回。不然就再往下判断下。判断到高位出现这个数就不用继续往下了。我感觉我说的很乱，因为都是零散的思路，我去写写代码整合一下思路。
好了，做完回来了了，思路可以用，然后性能也还好，我直接贴代码：

class Solution {
    int min = Integer.MAX_VALUE;
    public int numSquares(int n) {
        countN(n,0);
        return min;
    }
    public void countN(int n , int count){
        if(min == 2) return;
        count++;
        if(count== min) return; 
        int sq = (int)Math.sqrt(n);
        if(sq*sq == n) {
            min = Math.min(min,count);
            return;
        }
        for(int i = sq;i>0;i--){
           countN(n-i*i,count);
        }
    }
}

上面有一句代码，如果min==2直接返回。其实这个是因为首先如果这个数本身是完全平方数，那么根本不会走到for循环中的递归，所以其实不可能出现min=1的情况。其次如果这个数不是完全平方数，那么最少也就是拆成两个，所以如果出现了min是2，就没必要递归了。不过现在越想越觉得这句话其实作用也没多大，有点鸡肋，不过写了就写了吧。
性能超过百分之九十六，所以我自我感觉挺好，我去看一眼性能排行第一的代码，问题不大就直接过了。
问题有点大，因为我没太看懂：

class Solution {

  protected boolean isSquare(int n) {
    int sq = (int) Math.sqrt(n);
    return n == sq * sq;
  }

  public int numSquares(int n) {
    while (n % 4 == 0)
      n /= 4;
    if (n % 8 == 7)
      return 4;

    if (this.isSquare(n))
      return 1;
    for (int i = 1; i * i <= n; ++i) {
      if (this.isSquare(n - i * i))
        return 2;
    }
    return 3;
  }
}

除了这个for循环，剩下的，我都没太看懂。代码我是明白了，这里只会返回1,2,3,4.如果第二次循环还不是0就返回3，第二次循环就没了返回2，本身是完全平方数返回1.重点是这个4.。。除8余7就是4？我决定去评论看一看了，我是不是错过了什么？

四平方定理

笑而不语，我感觉我可能是没学过数学。。好的吧，看了这个配上代码算是明白了，我也尽量记住这个定理。下一题吧。

顶端迭代器

题目：给定一个迭代器类的接口，接口包含两个方法： next() 和 hasNext()。设计并实现一个支持 peek() 操作的顶端迭代器 -- 其本质就是把原本应由 next() 方法返回的元素 peek() 出来。

示例:
假设迭代器被初始化为列表 [1,2,3]。
调用 next() 返回 1，得到列表中的第一个元素。
现在调用 peek() 返回 2，下一个元素。在此之后调用 next() 仍然返回 2。
最后一次调用 next() 返回 3，末尾元素。在此之后调用 hasNext() 应该返回 false。
进阶：你将如何拓展你的设计？使之变得通用化，从而适应所有的类型，而不只是整数型？

思路：这个题我看了几遍题目，大概的理解是next相当于一个取出第一个元素并返回这个值。peek相当于一个返回第一个元素的值但是不取出。hasNext是判断下面还有没有元素了。至于进阶条件我觉得是泛型解决的。其实这类题我最懵的是不知道能用什么不能用什么。单纯的实现的话，我觉得集合链表都能实现。next就是获取第一个然后删除。peek就是获取第一个不做任何操作。hasNext就是判断当前集合或者链表中还有没有元素。甚至用队列的话这三个方法都是现成的。。哎，我都不知道这个题目是想要啥。我去尝试写写吧，先实现了，再去看评论好知道题目到底啥意思。
好了，我实现了，先贴代码：

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
class PeekingIterator implements Iterator<Integer> {
    Iterator<Integer> iterator;
    Integer temp;
    public PeekingIterator(Iterator<Integer> iterator) {
        // initialize any member here.
        this.iterator = iterator;
        
    }

    // Returns the next element in the iteration without advancing the iterator.
    public Integer peek() {
        if(temp==null){
            temp = iterator.next();
        }
        return temp;
    }

    // hasNext() and next() should behave the same as in the Iterator interface.
    // Override them if needed.
    @Override
    public Integer next() {
        if(temp==null){
            return iterator.next();
        }else{
            int res = temp;
            temp = null;
            return res;
        }
    }

    @Override
    public boolean hasNext() {
        return temp == null?iterator.hasNext():true;
    }
}

因为我是开始写代码了才发现这个题目构造器穿的参数就是Iterator，所以直接用了现有的api。不过有一个问题就是这个peek，迭代器是不支持取出值不移动元素的，所以我这里做了个小处理，就是把用temp缓存起来。每次移除节点也会先判断一下。
性能一般，只超过百分之七十多的人，但是主要是这个题我连题意都不知道，所以我直接去看评论了，回来再分享题目是什么意思。
回来了，性能排行第一的代码和我思路一样一样的，就是细节处理有点点区别。。评论中也没有别的说法，所以这道题好像就是这么简单，哈哈。这道题就这么过了，下一题了。

寻找重复数

题目：给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
说明：
不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。

思路：额，怎么说呢，在我没有看最后一句话的时候我甚至觉得题目还比较简单，毕竟从1加到n，然后再把结果去数组挨个减，最后负几，重复的数就是这个数的相反数。。但是！我还是太年轻了，只有一个重复数字，但是可能不止重复一次，我简直笑了！ 时间复杂度小于O(n方)，我感觉这个题应该比较复杂的，不然题目要求不会这么简单。不考虑时间复杂度的方法就是每一个数和其余的异或，有等于0的就是这个数重复了。但是现在我说这么多都被pass了，我再好好想想怎么实现吧。
emmm..暂时没思路，我用双层循环试了下，虽然性能不能看，但是居然没超时通过了，也挺有意思。

class Solution {
    public int findDuplicate(int[] nums) {
        for(int i = 0;i<nums.length-1;i++){
            for(int j = i+1;j<nums.length;j++){
                if(nums[i]==nums[j]) return nums[i];
            }
        }
        return -1;
    }
}

不过其实我觉得这个标准上不会到O(n方)，但是性能差成这样，我觉得正确答案可能是O(n)左右，O（n）的实现方式。。我想想。其实目前还有个想法，就是二进制的每一个的个数。正常如果是顺序来的，二进制的数应该是一定的。比如1,10,11连着的数每一位都是2个1.如果变成10，10，11就变成了第二位3个1，第一位1个。这样很明显就是第二位的1多了一个，第一位少了一个1.所以重复的数是10.。。但是这个是我粗略的想法， 而且我二进制运算是真的渣。。我先进来去考虑下这个思路的可性能吧。
好吧，简单百度了下，这个方法最大的问题需要存储每一个二进制位的1的个数。。用到了数组，题目不让用额外空间，所以这个思路就这么pass了。我再继续想想吧。
我看了题解，真的大把大把掉头发也没想出来。。然后看了题解还要理解好久。。真的是觉得自己越来越菜了。
哎，简单说下对题解的理解吧。主要分两部分：

链表成环

明明题目是数组，为什么说到链表了呢？其实数组的下标和数值可以组成一个链表的。数值是下一个链表的指针。下标作为当前链表的值就可以了啊。
我先画个图大概理解下怎么把数组理解成链表

数组抽象成链表

如上图，其实我一开始看的时候也不太理解，但是画了几个图才发现，链表一定是有环的，因为下标是从0开始，而数值是从1开始。所以第一步一定是能走出去的！
这个时候指针已经指向下一个了，像8这种自循环的不会被指到，所以也不会是重复的值。我们只要顺着指针往下指，哪怕指到自循环了那么更好了，直接说明这个数重复出现了（别的下标有这个值，这个下标还是这个值，直接就是出现了两次嘛！）
所以放心，只要有重复的值，肯定是有环的。我们现在要做的是从起点开始，快慢指针找到环的交点！

环的起点

其实这个题我们做过的，当时我也是理解起来比较慢还手动画了个图，就是怎么根据环的交点判断起点的，这里也贴一下：

快慢指针从交点找环起点

如图，红色是慢指针，红+绿是快指针。因为快指针一次两个，慢指针一次一个。所以红色和绿色是相等的。
然后因为环的起点到交点是一一段共同路径（慢指针走一遍，快指针走了两遍），所以红色实线和绿色实线也是相等的。
此时如果快指针从b开始，再来一个指针从起点开始相同速度走，最终实线会同时走完，并且两个指针肯定相交在环的入口处。

所以这道题就分两步：找到环形交点，找到环的起点。
环的起点就是这个重复元素。
我去写代码了：

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        while(true){
            slow = nums[slow];
            //这个下标的下标就相当于走了两步
            fast = nums[nums[fast]];
            if(slow == fast){//相交了
                fast = 0;//从头开始走
                while(slow != fast){//slow == fast 说明相交于环的起点了
                    fast = nums[fast];
                    slow = nums[slow];
                }
                return slow;
            }

        }
    }
}

思路清晰了代码其实不难，不过我还是调试了很多次，关于slow值和nums[slow]这类的，while条件是带nums[slow]这类的，返回也要这要的，比较的是直接量，返回的也要是，只要统一了就行了。
这个题乍一看简单，所有的约束条件都用上了的话真的有点烧脑啊，其实环找入口不用额外空间是做过的，但是没和这个题联系起来。还是做题少，见得少。这个题就这样了，继续往下刷题。

生命游戏

题目：根据百度百科，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在1970年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞具有一个初始状态 live（1）即为活细胞， 或 dead（0）即为死细胞。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；

如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；

如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；

如果死细胞周围正好有三个活细胞，则该位置死细胞复活；

根据当前状态，写一个函数来计算面板上细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。

示例:
输入:
[
[0,1,0],
[0,0,1],
[1,1,1],
[0,0,0]
]
输出:
[
[0,0,0],
[1,0,1],
[0,1,1],
[0,1,0]
]
进阶:
你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题？

思路：首先没有时间复杂度的要求，我觉得题目难度少了一半。至于进阶的第一个所谓的同时，我打算用状态来区分。比如之前是1.要变成0.我就给变成-1.这样他周围的我就知道这个数是1了，之前是0要变成1，我就先变为-2.这样周围也就这道这个数是0了。最后都走完了我再遍历一次，是-1的改成0.是-2的改成1.啧啧，我觉得这个想法一点问题没有。至于第二个边界问题，，，说实话我没太看懂，所以这里就先不想了，我去代码实现下试试。
思路完全没问题，代码性能超过百分百，有点小兴奋，虽然写着确实有点麻烦，哈哈。我直接贴代码了：

class Solution {
    public void gameOfLife(int[][] board) {
        if(board.length==0 || board[0].length==0) return;
        //0变1先变成-1   1变0先变成 -2
        for(int i = 0;i<board.length;i++){
            for(int j = 0;j<board[0].length;j++){
                int n = isLive(board,i,j);
                if(board[i][j]==0){
                    //死变活现先变-1
                    if(n==3) board[i][j] = -1;
                }
                if(board[i][j]==1){
                    //活变死
                    if(n<2 || n>3) board[i][j] = -2;
                }               
            }
        }
        for(int i = 0;i<board.length;i++){
            for(int j = 0;j<board[0].length;j++){
                if(board[i][j]==-1) board[i][j] = 1;
                else if(board[i][j]==-2) board[i][j] = 0;
            }
        }

    }
    public int isLive(int[][] board,int i,int j){
        //判断周围活细胞的个数
        int n = 0;
        for(int k = i-1;k<=i+1;k++ ){
            for(int r = j-1;r<=j+1;r++){
                if(k==i && r==j) continue;
                if(k>=0 && k<board.length && r>=0 && r<board[0].length &&
                (board[k][r]==1 || board[k][r]==-2)) n++;
            }
        }
        return n;
    }
}

因为以前做二维数组的扩散，像素啥的用过这样的办法，所以这里直接封装了个判断上下左右对角线活着的细胞数量的方法（其实拆开是四层循环）。
然后细心耐心就好了，这个题不难，但是很可能一个字母错了就调试好久，比如我一开始isLive中第二层循环是r=j-i。真的是看瞎眼了，调试两边才抓到这个错的，哈哈
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注。也祝大家工作顺顺利利！（ps：打个广告：Java技术交流群：130031711，欢迎各位踊跃加入。）