[LeetCode] 118. Pascal's Triangle

Given an integer numRows, return the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:
Input: numRows = 1
Output: [[1]]

Constraints:
1 <= numRows <= 30

杨辉三角。

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

思路一 - 暴力模拟

按照题意一行一行把元素写出来然后返回整个三角形。

复杂度

时间 O(n^2)
空间 O(n^2)

代码

Java 实现一

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> firstRow = new ArrayList<>();
        firstRow.add(1);
        res.add(firstRow);
        for (int i = 1; i < numRows; i++) {
            List<Integer> cur = new ArrayList<>();
            // 每一行开头的1
            cur.add(1);
            // 从第二个数字开始，都是找上一行的元素
            // 当前行位置 j 上的数字 = 上一行位置 j - 1 + 上一行位置 j 上的数字
            for (int j = 1; j < i; j++) {
                cur.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));
            }
            // 记得加每行最后一个1
            cur.add(1);
            res.add(cur);
        }
        return res;
    }
}

思路二 - 固定空间

这个三角形注意一下几点

• 首行只有一个元素 1
• 每一行的第一个和最后一个元素是 1
• 每一行的元素个数 = 行的 index。注意 index 是从 1 开始的
• 中间行位于 index j 的元素 = 上一行位于 j - 1 的元素 + 上一行位于 j 的元素

照着这个思路，我们才能以固定空间复杂度来解决这个问题。这个思路有助于版本二 119 题。

复杂度

时间 O(n^2)
空间 O(k)

代码

Java 实现二 - 固定空间

class Solution {
	public List<List<Integer>> generate(int numRows) {
		List<List<Integer>> res = new ArrayList<>();
		List<Integer> list = new ArrayList<>();
		for (int i = 0; i < numRows; i++) {
			// 头部加1
			list.add(0, 1);
			for (int j = 1; j < list.size() - 1; j++) {
				list.set(j, list.get(j) + list.get(j + 1));
			}
			res.add(new ArrayList<>(list));
		}
		return res;
	}
}

相关题目

118. Pascal's Triangle
119. Pascal's Triangle II
120. Triangle
799. Champagne Tower
2221. Find Triangular Sum of an Array