118、杨辉三角

leetcode

Created At : 2020-07-26 00:19

Count:392 Views 👀 :

Comment:

118、杨辉三角
1. 示例:

题解

1、模拟计算

118、杨辉三角

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

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

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

链接：https://leetcode-cn.com/problems/pascals-triangle

题解

1、模拟计算

模拟计算每一行

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        
        for (int i = 1;i <= numRows;i++) {
            List<Integer> tmp = new ArrayList<>();
            // 前两行不需要计算
            if (i <= 2) {
                for (int j = 0;j < i;j++) {
                    tmp.add(1);
                }
                res.add(tmp);
            } else {
                tmp.add(1);
                List<Integer> tmp0 = res.get(i-2);
                for (int j = 1;j < i-1;j++) {
                    tmp.add(tmp0.get(j-1)+tmp0.get(j));
                }
                tmp.add(1);
                res.add(tmp);
            }
        }
        return res;
    }
}

递归实现

class Solution {
    // 作为记忆化存储
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    public List<List<Integer>> generate(int numRows) {
        for (int i = 0;i < numRows; i++) {
            res.add(i,generateLine(i+1));
        }
        return res;
    }
    // 递归生成每一行
    private List<Integer> generateLine(int line) {
        List<Integer> line = new ArrayList<>();
        // 第一个数字为1 
        line.add(1);
        // 第一行只有一个 1
        if (line == 1) {
            return line;
        }
        // 获取前一行的数字
        List<Integer> prev = res.get(line - 2);
        // 利用递推公式计算当前行的值
        for (int i = 1; i < line - 1; i++) {
            line.add(prev.get(i-1)+prev.get(i));
        }
        // 最后一个数字也为1
        line.add(1);
        return line;
    }

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com