118&119. 杨辉三角I & II

118. 杨辉三角

本题来自 LeetCode：118. 杨辉三角^[1]

题目描述

给定一个非负整数  numRows，生成杨辉三角的前  numRows  行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例:

输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

题目分析

观察杨辉三角的结构，可以转换成如下的形式。

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

可以发现除了位置 [i][i] = 1外，其它位置 [i][j]的值等于 [i-1][j-1]+[i-1][j]。为了防止 j - 1越界，可以通过在前一行 [i - 1][-1]位置补 0来避免。如下

0
0 1
0 1 1
0 1 2 1
0 1 3 3 1
0 1 4 6 4 1

题目解答

class Solution {
    public ListListInteger generate(int numRows) {
        ListListInteger rows = new LinkedList();
        ListInteger preLine = new ArrayList();
        // 分别计算前numRows的值
        for(int i = 1; i = numRows; i ++) {
            preLine = generateRow(preLine, i);
            rows.add(preLine);
        }
        return rows;
    }

    // 根据 rowNum-1行 计算第rowNum行的值
    public ListInteger generateRow(ListInteger preLine, int rowNum) {
        ListInteger line = new ArrayList(rowNum);
        int pre = 0;
        for(int i = 0; i  preLine.size(); i ++) {
            line.add(pre + preLine.get(i));
            pre = preLine.get(i);
        }
        // 最后一位补1
        line.add(1);
        return line;
    }
}

复杂度分析：
时间复杂度： O(numRows^2)
空间复杂度： O(numRows^2)

119. 杨辉三角 II

本题来自 LeetCode：119. 杨辉三角 II^[2]

题目描述

给定一个非负索引  k，其中 k ≤ 33，返回杨辉三角的第 k 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例:

输入: 3
输出: [1,3,3,1]

进阶：
你可以优化你的算法到 O(k)空间复杂度吗？

题目分析

本题要求空间复杂度为 O(k)，故需要原地将上一行转换为当前行。注意起始行的行号为 0

题目解答

class Solution {
    public ListInteger getRow(int rowIndex) {
        ListInteger line = new ArrayList();
        line.add(1);
        for(int i = 1; i = rowIndex; i ++) {
            int pre = 0;
            for(int j = 0; j  i; j ++) {
                Integer current = pre + line.get(j);
                pre = line.get(j);
                line.set(j, current);
            }
            line.add(1);
        }
        return line;
    }
}

复杂度分析：
时间复杂度： O(k * k)
空间复杂度： O(k)

参考资料

118. 杨辉三角: https://leetcode-cn.com/problems/pascals-triangle

119. 杨辉三角 II: https://leetcode-cn.com/problems/pascals-triangle-ii

原文始发于微信公众号（xiaogan的技术博客）：