HomeArchivesCategoriesLabelMomentsPhotosLinkAbout

LeetCode 118. 杨辉三角

学习
47
0
0
2022-04-22
LeetCode 118. 杨辉三角

LeetCode 118. 杨辉三角

问题描述

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

示例 1：

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

示例 2：

输入: numRows = 1
输出: [[1]]

提示：

  • 1 <= numRows <= 30

思路

方法一：找规律

首先，观察杨辉三角可以得到以下规律：杨辉三角两条腰上的值全部设置为1，并且杨辉三角中任意一个内部的值都等于与其上一行相邻的两个值之和。找到规律后，具体求解步骤如下：

  1. 定义 List 数组 res，用于保存结果；

  2. 进行 numRows 层 for 循环来分别求出 numRows 行的杨辉三角，并且需要定义 List 数组 tmpRes 用来保存每一行的结果，在求解过程中，需要分以下两种情况：

    • 若当前值位于杨辉三角的腰上，那么设置为1；

    • 若当前值位于杨辉三角的内部，那么该值等于与其上一行相邻的两个值之和；

  3. 每求解出一行的值，就将 tmpRes 添加到 res 中；

  4. 循环结束后，返回 res 即可。

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        for (int i = 0; i < numRows; i++) {
            // 保存第 i 行的结果，此处是从 i = 0 行开始
            List<Integer> tmpRes = new ArrayList<Integer>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    // 设置杨辉三角两条腰上的值，即全部设置为1
                    tmpRes.add(1);
                } else {
                    // 设置杨辉三角内部的值，任意一个内部的值都等于与其上一行相邻的两个值之和
                    tmpRes.add(res.get(i - 1).get(j) + res.get(i - 1).get(j - 1));
                }
            }
            // 将第 i 行的结果保存到 res 中
            res.add(tmpRes);
        }
        return res;
    }
}

总结

本题通过找规律，可以轻松地生成杨辉三角的前 numRows 行。关键是理解杨辉三角的性质，即两条腰上的值都为1，内部的值等于与其上一行相邻的两个值之和。

#LeetCode 9