tsanmmmm2000's Tech Blog

Question

Given an index k, return the k^th 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?

Thinking

若知道如何求帕斯卡三角形(Pascal's Triangle)某一row的數學公式\(C^k_i=\frac{k!}{i!(k-i)!}=\binom{k}{i} = \binom{k}{i-1} {k+1-i\over i}\)，其實可以直接套公式解，不過要注意計算過程可能發生Overflow的情況

public class Solution {
    public IList<int> GetRow(int rowIndex) {
        var result = new int[rowIndex+1];
        result[0] = 1;
        for(var i = 1; i < result.Length; i++)
        {
            result[i] = (int)((long)result[i-1] * (rowIndex + 1 - i) / i);
        }
        return result.ToArray();
    }
}

若覺得公式解不易讀，可以換成與#118 Pascal's Triangle類似的解法，但題目有提到最好能做到空間複雜度O(k)，因此我們還必須不斷變更List內的值才行

My C# Solution

public class Solution {
    public IList<int> GetRow(int rowIndex) {
        var result = new List<int>();
        while(rowIndex >= 0)
        {
            FillNextRowVal(result);
            rowIndex--;
        }            
        return result;
    }
    
    private void FillNextRowVal(List<int> row)
    {
        var rowNumber = row.Count;
        if (rowNumber == 0)
        {
            row.Add(1);            
        }
        else
        {
            for (var i = rowNumber - 1; i > 0; i--)
            {
                var val = row[i] + row[i-1];
                row[i] = val;
            }
            row.Add(1);            
        }
    }
}

Reference：Pascal's triangle - Wikipedia