1、题目名称

Pascal's Triangle II（帕斯卡三角形2）

2、题目地址

3、题目内容

英文：Given an index k, return the kth row of the Pascal's triangle.

中文：给出行数k，返回帕斯卡三角形的第k行

例如，k=3时，返回[1,3,3,1]

4、解题方法1

帕斯卡三角形也叫杨辉三角形，在LeetCode第118题（）中，。这个方法也可以用于求指定行。

一段实现此方法的Java代码如下：

import java.util.ArrayList;import java.util.List;/** * 功能说明：LeetCode 119 - Pascal's Triangle II * 开发人员：Tsybius2014 * 开发时间：2015年8月14日 */public class Solution {        /**     * 获取帕斯卡三角形的指定行     * @param rowIndex 行数     * @return     */    public List
    
      getRow(int rowIndex) {                if (rowIndex < 0) {            return null;        }                ArrayList
     
       resultList = new ArrayList
      
       ();                //第一行        resultList.add(1);                //之后各行        for (int i = 0; i < rowIndex; i++) {            resultList = getNextArray(resultList);        }                return resultList;    }    /**     * 给定帕斯卡三角形的一行数据，获取下一行数据     * @param array 帕斯卡三角形某一行     * @return 帕斯卡三角形的下一行     */    public ArrayList
       
         getNextArray(ArrayList
        
          arrayList) {        if (arrayList == null) {            return null;        }        ArrayList
         
           nextList = new ArrayList
          
           (); nextList.add(1); for (int i = 0; i + 1 < arrayList.size(); i++) { nextList.add(arrayList.get(i) + arrayList.get(i + 1)); } nextList.add(1); return nextList; }}
          
         
        
       
      
     
    

5、解题方法2

另一个办法是利用杨辉三角形的特性，即第n行的第k个数字为组合数 C(n-1, k-1)，这样只需要写一个计算组合数的函数，调用n次就可以了。不过这里要注意，组合数的计算过程中，为了防止中间数值过大导致计算结果不精确，可以采用double类型数字存储中间值，且当k>n-k时，将k转换为n-k计算。

一段实现此方法的Java代码如下：

import java.util.ArrayList;import java.util.List;/** * 功能说明：LeetCode 119 - Pascal's Triangle II * 开发人员：Tsybius2014 * 开发时间：2015年8月14日 */public class Solution {        /**     * 获取帕斯卡三角形的指定行     * @param rowIndex 行数     * @return     */    public List
    
      getRow(int rowIndex) {        int n = rowIndex + 1;        ArrayList
     
       resultList = new ArrayList
      
       ();        for (int k = 1; k <= n; k++) {            resultList.add(C(n - 1, k - 1));        }        return resultList;    }        /**     * 求组合数 C(n,k) = (n(n-1)(n-2)...(n-k+1))/(k(k-1)(k-2)...1)     * @param n C(n,k)中的n     * @param k C(n,k)中的k     * @return 组合数     */    private int C(int n, int k) {        if (k > n - k) {            k = n - k;        }        double numerator = 1.0;        double denominator = 1.0;        for (int i = 0; i < k; i++) {            numerator *= (n - i);            denominator *= (k - i);        }        return (int)(numerator / denominator + 0.5);    }}
      
     
    

需要注意的是，因为组合数C(n,k)在k=1到k=n的循环过程中计算出的值是对称的，为了减少计算量，只需要计算最多n/2+1次组合数就可以了。

一个更好的办法是：

public List
    
      getRow(int rowIndex) {    int n = rowIndex + 1;    ArrayList
     
       resultList = new ArrayList
      
       ();    if (n % 2 == 1) {        resultList.add(C(n - 1, n / 2));    }    for (int k = n / 2; k > 0; k--) {        resultList.add(0, C(n - 1, k - 1));        resultList.add(C(n - 1, k - 1));    }    return resultList;}
      
     
    

END