杨辉三角

发表于
本文字数： 913 阅读时长 ≈ 1 分钟

LeetCode每日一题，118. Pascal’s Triangle

先看题目描述

DXqyVS.png

大意就是给定一个整数 numRows，让我们生成杨辉三角的前 numRows 行

算法和思路

这题很简单，没什么好说的，就一行行生成就可以。对于第 n 行的数字，需要由第 n - 1 行来生成，第 n 行的第一个数字和最后一个数字均为 1，对于第 n 行的第 i 个数字(1 < i < n)，其值会等于第 n - 1 行的第 i -1 个数字和第 i 个数字之和。就这样按照该规律，一行行的生成杨辉三角即可

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.*;

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> temp = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    temp.add(1);
                } else {
                    temp.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));
                }
            }
            res.add(temp);
        }
        return res;
    }
}