【Leetcode题】119. 帕斯卡三角形 II

给定一个索引 k，返回帕斯卡三角形（杨辉三角）的第 k 行。

例如：

给定 k = 3，则返回 [1, 3, 3, 1]

你可以优化你的算法到 O(k) 的空间复杂度吗？

使用递归的方式： Ck[n] = Ck-1[n-1] + Ck-1[n]【超时了】

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new ArrayList<Integer>(rowIndex+1);
        int half = rowIndex / 2;
        if(rowIndex == 1){
            result.add(1);
            result.add(1);
            return result;
        }
        
        for(int i=0;i<rowIndex + 1;i++){
            //如果是另一半，则取对称元素
            if(i > half) {
                result.add(result.get(rowIndex - i));
            }
            else{
                result.add(getNum(rowIndex, i));
            }
        }
        return result;
    }
    //索引k， 第n个
    private Integer getNum(int k, int n) {
        if(k == 0 || k == 1){
            return 1;
        }
        if(n == 0 || n == k) {![WX20180331-204230.png](https://img.haomeiwen.com/i3017321/424fcdc89cf783f0.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

            return 1;
        }
        return getNum(k-1, n-1) + getNum(k-1, n);
    }
}

以上之所以出现超时，是因为递归调用时存在多次重复调用。

比如在计算getNum(10, 3)时会发起调用：

递归.png

如上图所示，getNum(8,2),getNum(7,1)和getNum(7,2)会调用多次，越到后面，重复调用的递归会更多，如果把这些递归调用的结果保存下来，效果会不会更好呢？

class Solution {
    private Map<String,Integer> cache = new HashMap<String, Integer>();
    public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new ArrayList<Integer>(rowIndex+1);
        int half = rowIndex / 2;
        if(rowIndex == 1){
            result.add(1);
            result.add(1);
            return result;
        }
        
        for(int i=0;i<rowIndex + 1;i++){
            //如果是另一半，则取对称元素
            if(i > half) {
                result.add(result.get(rowIndex - i));
            }
            else{
                result.add(getNum(rowIndex, i));
            }
        }//0 1 2 3 1
        
        return result;
    }
    //索引k， 第n个
    private Integer getNum(int k, int n) {
        if(cache.get(k + ":" + n) != null){
            return cache.get(k + ":" + n);
        }
        if(k == 0 || k == 1){
            return 1;
        }
        if(n == 0 || n == k) {
            return 1;
        }
        int r = getNum(k-1, n-1) + getNum(k-1, n);
        cache.put(k + ":" + n, r);
        return r;
    }

}

结果很nice, Leetcode给的结论是【4ms】，然而这个结果却是所有答案中耗时最大的，难道还有优化的地步。

杨辉三角规律：

第n行第1个数： 1
第n行第2个数：1×(n-1)
第n行第3个数：1×(n-1)×(n-2)/2
第n行第4个数:   1×(n-1)×(n-2)/2*(n-3)/3

用索引讲：

第k索引行第0索引数：1
第k索引行第1索引数：1×k
第k索引行第2索引数：1×k×(k-1)/2
第k索引行第3索引数：1×k×(k-1)/2×(k-2)/3

所以最终答案： 【耗时1ms】

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new ArrayList<Integer>(rowIndex+1);
        int half = rowIndex / 2;
        if(rowIndex == 1){
            result.add(1);
            result.add(1);
            return result;
        }
        
        for(int i=0;i<rowIndex + 1;i++){
            if(i == 0){
                result.add(1);
                continue;
            }
            //如果是另一半，则取对称元素
            if(i > half) {
                result.add(result.get(rowIndex - i));
            }
            else{
                result.add(Double.valueOf(1.0 * result.get(i-1) * (rowIndex - (i-1)) / i).intValue());
            }
        }//0 1 2 3 1
        
        return result;
    }
}

总结： 杨辉三角每行元素不仅和上一行有关系，同一行元素之间的关系也颇为密切。而递归则是采用第一种方案，不用缓存在计算大数时会出现超时，而第二种方案则非常轻松实现。