[Leetcode] Pascal's Triangle 楊輝三角形

Berwin 發(fā)布于2019-08-14 12:37 / 735人閱讀

摘要：迭代法復(fù)雜度時間空間思路簡單的按照楊輝三角形的規(guī)則計算就行了。代碼加入第一個加入中間的數(shù)加入最后一個逆序相加法復(fù)雜度時間空間思路同樣用迭代的方法，根據(jù)上一層的值算下一層，不過這里每一層都在同一個上操作。

Pascal"s Triangle I

Given numRows, generate the first numRows of Pascal"s triangle.
For example, given numRows = 5, Return
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

迭代法 復(fù)雜度

時間 O(N) 空間 O(k^2)

思路

簡單的按照楊輝三角形的規(guī)則計算就行了。

代碼

public class Solution {
    public List> generate(int numRows) {
        List> res = new ArrayList>();
        if(numRows <= 0) return res;
        List one = new ArrayList();
        one.add(1);
        res.add(one);
        for(int i = 1; i < numRows; i++){
            List line = new ArrayList();
            // 加入第一個1
            line.add(1);
            // 加入中間的數(shù)
            for(int j = 1; j < i; j++){
                line.add(res.get(i-1).get(j-1) + res.get(i-1).get(j));
            }
            // 加入最后一個1
            line.add(1);
            res.add(line);
        }
        return res;
    }
}

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].
Note: Could you optimize your algorithm to use only O(k) extra space?

逆序相加法 復(fù)雜度

時間 O(N) 空間 O(k)

思路

同樣用迭代的方法，根據(jù)上一層的值算下一層，不過這里每一層都在同一個List上操作。如果我們從后向前計算，而且每次計算都用到上一個位置的數(shù)的話，我們會重復(fù)計算好幾次，導(dǎo)致結(jié)果錯誤。這里的技巧在于從后向前計算，并且每次計算用當前位置的值和上一位置的值，來更新當前位置的值。最后再在后面加個1，就是這一層的結(jié)果了。

代碼

public class Solution {
    public List getRow(int k) {
        List line = new ArrayList();
        // 加入第一個1
        line.add(1);
        if(k <= 0) return line;
        for(int i = 1; i <= k; i++){
            // 計算j+1位置的值，是根據(jù)j位置的值和j+1位置的值得到的，相當于往后位移一位
            for(int j = line.size() - 2; j >= 0; j--){
                line.set(j + 1, line.get(j) + line.get(j + 1));
            }
            // 加上最后一個1
            line.add(1);
        }
        return line;
    }
}

公式法 復(fù)雜度

時間 O(K) 空間 O(1)

思路

更“暴力”的方法，是直接使用公式，對于第k(k>=1)層下標為i(i>=0)的位置，數(shù)字應(yīng)該為num[i-1] * (k - i) / i，由于這個乘法可能溢出，我們用一個long型臨時變量將其存起來。

注意

rowIndex是0開始的，公式中k是1開始的

代碼

public class Solution {
    public List getRow(int rowIndex) {
        // rowIndex是0開始的，我們將它加1，得到k
        int k = rowIndex + 1;
        ArrayList line = new ArrayList();
        line.add(1);
        long tmp = 1;
        for(int i = 1; i < k; i++){
            // 使用公式 上一個數(shù)乘以(k-i)再除以i
            tmp = tmp * (k - i) / i;
            line.add((int)tmp);
        }
        return line;
    }
}