Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in polynomial time complexity.
题目大意：
给定一个整数n，返回n!（n的阶乘）数字中的后缀0的个数。
注意：你的解法应该满足多项式时间复杂度。
解题思路：
参考博文：http://www.geeksforgeeks.org/count-trailing-zeroes-factorial-number/
朴素解法：
首先求出n!，然后计算末尾0的个数。（重复÷10，直到余数非0）
该解法在输入的数字稍大时就会导致阶乘得数溢出，不足取。
O（logn）解法：
一个更聪明的解法是：考虑n!的质数因子。后缀0总是由质因子2和质因子5相乘得来的。如果我们可以计数2和5的个数，问题就解决了。考虑下面的例子：
n = 5: 5!的质因子中 (2 * 2 * 2 * 3 * 5)包含一个5和三个2。因而后缀0的个数是1。
n = 11: 11!的质因子中(2^8 * 3^4 * 5^2 * 7)包含两个5和三个2。于是后缀0的个数就是2。
我们很容易观察到质因子中2的个数总是大于等于5的个数。因此只要计数5的个数就可以了。那么怎样计算n!的质因子中所有5的个数呢？一个简单的方法是计算floor(n/5)。例如，7!有一个5，10!有两个5。除此之外，还有一件事情要考虑。诸如25，125之类的数字有不止一个5。例如，如果我们考虑28!，我们得到一个额外的5，并且0的总数变成了6。处理这个问题也很简单，首先对n÷5，移除所有的单个5，然后÷25，移除额外的5，以此类推。下面是归纳出的计算后缀0的公式。
By given number 4617.
5^1 : 4617 ÷ 5 = 923.4, so we get 923 factors of 5
5^2 : 4617 ÷ 25 = 184.68, so we get 184 additional factors of 5
5^3 : 4617 ÷ 125 = 36.936, so we get 36 additional factors of 5
5^4 : 4617 ÷ 625 = 7.3872, so we get 7 additional factors of 5
5^5 : 4617 ÷ 3125 = 1.47744, so we get 1 more factor of 5
5^6 : 4617 ÷ 15625 = 0.295488, which is less than 1, so stop here.
public class Solution {
public int trailingZeroes(int n) {//0的个数取决于n中质数5的个数，因为2的个数总是大于5,注意这里i的类型是long，不是int，否则会溢出
int result = 0;
for(long i=5; n/i>0; i*=5){
result += (n/i);
}
return result;
}
}
算法1耗时1ms， 更简单的算法是算法2，计算单个5被除的次数，耗时2ms
public class Solution {
public int trailingZeroes(int n) {//0的个数取决于n中质数5的个数，
int zeroCount = 0;
while(n>0){
n/=5;
zeroCount+=n;
}
return zeroCount;
}
}
Pascal's Triangle II
Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3,
Return [1,3,3,1].
public class Solution {
public List<Integer> getRow(int rowIndex) {
/*first method used in Pascal's Triangle, just return the wanted row
List<List<Integer>> listReturn = new ArrayList<List<Integer>>();
for(int i=0;i<rowIndex+1;i++){
List<Integer> tempList= new ArrayList<Integer>();
for(int j=0;j<=i;j++){
if(j==0||j==i)tempList.add(1);
else tempList.add(listReturn.get(i-1).get(j-1)+listReturn.get(i-1).get(j));
}
listReturn.add(tempList);
}
return listReturn.get(rowIndex);*/
// second way: deal with the wanted row directly, look it as a integration of all the before rows
//把第三行看成是第1、2行的结合，先构造第1、2行的data，然后按照相同的原则计算第3行：K(i)(j)=K(i-1)(j-1)+K(i-1)(j)
//例如，先构造[1,1],[1,2,1],[1,3,3,1]
List<Integer> ret = new ArrayList<Integer>();
ret.add(1);//the first element
for (int i = 1; i <= rowIndex; i++) {
for (int j = i - 1; j >= 1; j--) {
int tmp = ret.get(j - 1) + ret.get(j);
ret.set(j, tmp);
}
ret.add(1);//the last element
}
return ret;
}
}