leetcode: 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?

原问题链接：https://leetcode.com/problems/pascals-triangle-ii/

 

问题分析

　　从实现的情况来看，这个问题的实现思路和前一个还稍微有点不一样。前一个是要求记录所有到第k个的三角序列，而这里只要记录第k个。而从前面要求来看，k = 3的时候，它这一行有4个元素，那么对于第k个序列来说，它这一行应该有k + 1个元素。

　　因为题目中要求使用O(k) 的空间，所以我们不能不断的申请空间。在这里可以使用两个k + 1长度的数组。int[] pre, int[]cur。我们最初始的情况是一个仅仅包含有数字1的元素。所以需要将pre[0] = 1。然后每次我们通过pre进行转换得到cur，然后再将cur和pre互换。在实现里我们需要定义一个两层的循环，一层表示从1到rowIndex，表示当前构造的是第几行，而里面的循环则是根据前一行进行转换。我们可以先将cur[0], cur[row]设置为１，而对于里面的每个元素，则有cur[i] = pre[i] + pre[i-1]。

　　详细的代码实现如下：

 

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;
    }
}