LeetCode题解

date: 2016-02-20 20:09:12

`[LeetCode,算法]`

1. Populating Next Right Pointers in Each Node

本题具体地址见网址：Populating Next Right Pointers in Each Node简单说就是遍历一个满二叉树，找出每个结点的右邻居，如果没有值为空。
开始的第一反应是采用层序遍历，但是限制条件是空间复杂度是常量，因此无法使用层序遍历。
现在采用的方法是将每一层看成是一个待遍历的单链表，用两个指针p,q指向表头，p为遍历指针，在遍历过程中，就可以完成next指针的设置。具体java代码如下

     public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        } 
        else {
            root.next = null;
            if (root.left == null) {
                return;
            }
            else {
            TreeLinkNode p = root , q = root;
            root.next = null;
            while (p.left != null) {
                p.left.next = p.right;
                if (p.next != null) {
                p.right.next = p.next.left;
                p = p.next;
                    }
                else {
                    p.left.next = p.right;
                    p.right.next = null;
                    p = q.left;
                    q = p;
                    }
                }
            }
        }

2. Add Digit

Add Digit是将一个非负数字上的所有数字位加起来，得到一个数并重复这个过程直到形成一个个位数，例如：742->13->4。可以采用迭代的算法，但是这里也存在公式，f(n) = 1 + (n - 1)mod9，最终得到的数称为数根。

3. Nim Game

Nim Game是取数游戏。有一堆石子，每次可以取1、2、3个石头，最后取走石头的人为赢家。你首先取数，判断给定N个石头，你是否能赢。
思路：使用DP的思路的话，fn[n] = !fn[n-1]||!fn[n-2]||!fn[n-3]，但是这里有一个技巧，可以直接判断：

n%4 == 0

假如不能被4整除，最会就能成为赢家。

4. House Robber

House Robber在一条大街上有许多房子，你作为一个小偷要从这些房子里偷money，但是相邻的房子之间有安全系统连接，如果同一个晚上连续两家被劫，就会触发报警系统。
输入：一个非负数组代表每间屋子里的money，在不触发报警系统的前提下最大化可以抢劫的数量。
思路：考虑使用动态规划(DP)，

5. Intersection of Two Arrays

Intersection of Two Arrays给定两个无序数组，求这两个数组的交集，交集中无重复数字。
思路：一个很显然的思路就是二重循环，时间复杂度是 $O(n^2)$ ；先对其中的一个数组进行排序，然后在这个有序数组上进行二分查找，时间复杂度是 $O(nlogn)$ 。

6. Move Zeros

Move Zeroes给定一个数组，将数组中所有的0移动到数组的尾部，并且保持其余非零元素的相对顺序不变。
思路：考虑非零数字最终的位置，一个非零数字最终的位置相当于在当前位置上向前移该数字前面零元素的个数，使用一个计数器计算当前数字前零元素个数；

   public void moveZeros(int nums){
         int len = nums.length;
         if(len <= 0) {
             return;
         }
         int count = 0;
         for(int i = 0;i < len;++i) {
            if(nums[i] == 0) {
                count++;
            } else {
                nums[i - count] = nums[i];
            }
         }
        return;
   }

7. Majority Element

Majority Element给定一个数组，其中一个元素出现次数超过数组长度的一半，找出这个数字。
思路：佷明显，如果将该数组排序后，Majority Element将会出现在len/2位置处，此时时间复杂度为 $O(nlogn)$ ;
考虑另外一种解法：

8. Factorial Trailing Zeroes

Factorial Trailing Zeroes给定一个整数n，求n!的末尾有多少个0，要求时间复杂度是 $O(logn)$ 。
思路：其实就是计算n!中含有因子5的个数，例如，20！ = 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20 = 2432902008176640000，含有因子5的个数为4，所以20!尾部含有4个0。可以得到如下递推公式
$f(n!) = f((5*K)*(5*K - 1)*5*A) = f(5^K*K!*A) = K + f(K!)$ ，其中A是不能被5整除的因子, $K = n/5$ 。这样用递归程序就可以解出答案。