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?

118. Pascal's Triangle 的拓展，给一个索引k，返回杨辉三角的第k行。

解法：题目要求优化到 O(k) 的空间复杂，那么就不能把每行都记录下来，而只是记录前一行和当前行。

Java:

public class Solution {

    public List<Integer> getRow(int rowIndex) {

        List<Integer> res = new ArrayList<>();

        int curr[] = new int[rowIndex + 1];

        int prev[] = new int[rowIndex + 1];

        prev[0] = 1;  

        for(int row = 1; row <= rowIndex; row++) {

            curr[0] = 1;

            curr[row] = 1;

            for(int i = 1; i < row; i++)

                curr[i] = prev[i] + prev[i - 1];

            int[] swap = curr;

            curr = prev;

            prev = swap;

        }   

        for(int i = 0; i <= rowIndex; i++)

            res.add(prev[i]);

        return res;

    }

}

Java:

public class Solution {

    public List<Integer> getRow(int rowIndex) {

        ArrayList<Integer> row = new ArrayList<Integer>();

        for (int i=0; i<rowIndex+1; i++){

            row.add(0,1);

            for(int j=1; j<row.size()-1;j++){

                row.set(j, row.get(j)+row.get(j+1));

            }

        }

        return row;

    }

}

Python:

class Solution:

    # @return a list of integers

    def getRow(self, rowIndex):

        result = [0] * (rowIndex + 1)

        for i in xrange(rowIndex + 1):

            old = result[0] = 1

            for j in xrange(1, i + 1):

                old, result[j] = result[j], old + result[j]

        return result

C++:　　

class Solution {

public:

    vector<int> getRow(int rowIndex) {

        vector<int> out;

        if (rowIndex < 0) return out;

        out.assign(rowIndex + 1, 0);

        for (int i = 0; i <= rowIndex; ++i) {

            if ( i == 0) {

                out[0] = 1;

                continue;

            }

            for (int j = rowIndex; j >= 1; --j) {

                out[j] = out[j] + out[j-1];

            }

        }

        return out;

    }

};

C++:

class Solution {

public:

    vector<int> getRow(int rowIndex) {

        vector<int> result(rowIndex+1, 0);

        result[0] = 1;

        for(int i=1; i<rowIndex+1; i++)

            for(int j=i; j>=1; j--)

                result[j] += result[j-1];

        return result;

    }

};

类似题目：

[LeetCode] 118. Pascal's Triangle 杨辉三角

All LeetCode Questions List 题目汇总

巴特西

[LeetCode] 119. Pascal's Triangle II 杨辉三角 II

All LeetCode Questions List 题目汇总

最新文章

热门文章