【LeetCode】Pascal's Triangle II解題報告

【LeetCode】Pascal’s Triangle II解題報告
[LeetCode]
[https://leetcode.com/problems/pascals-triangle-ii/][1]
Total Accepted: 74643 Total Submissions: 230671 Difficulty: Easy
Question
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?
Ways
この問題の最も簡単な方法はもちろん楊輝三角1の方法に基づいて最後の列のデータを返すことだ.しかし、これは要求に合わないに違いない.
いい方法も思いつきましたが、直接書く能力はまだありません.これはパソコンでホワイトボードでコードを書くときにペンで描くことができないからだと思います.これは後で改善します.簡単な問題でまた1時間も振り回されましたが...
私の考えは多くの人と同じで、ダイナミックな計画のような問題は、空間を繰り返し利用して、前のラウンドのデータをカバーすればいいということです.
私ができないのは、概要のデータを上書きしないのがメリットだと思います.例:

i   answer
0   1
1   1   1
2   1   2   1
3   1   3   3   1
4   1   4   6   4   1
......

見るときはi行ごとに、この行の上の行の一番右の方から、これはこれと前の項の和に等しい.この項目の前をもう一度見てください.最後のループが完了した後に最後のビットを1に追加します.

public class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> answer = new ArrayList();
        answer.add(1);
        if (rowIndex <= 0) {
            return answer;
        }
        for (int i = 0; i < rowIndex; i++) {
            for (int j = answer.size() - 2; j >= 0; j--) {
                answer.set(j + 1, answer.get(j) + answer.get(j + 1));
            }
            answer.add(1);
        }
        return answer;
    }
}

AC:3ms
この問題の優から左へ遍歴する方法は動的計画にも用いられる.
Date
2016年05月8日