leetcode118 -- 杨辉三角

一. 问题描述

给定一个非负整数 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

二. 解决问题

主函数：

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        for(List<Integer> i : generate2(num)){
            System.out.println(i);
        }
    }
1
2
3
4
5
6
7

法一：递归

1. 解题思路

递归方法总而言之就是抓住三点：

• 找整个递归的终止条件
• 找返回值
• 一次递归需要如何操作

---

• 找整个递归的终止条件：
  • 递归至numRows = 0或者numRows = 1都可以终止。
• 找返回值：
  • 题目返回值为List ，也就是每一行遍历完一个list，之后把list附加到总的list之后就OK了。
• 一次递归需要如何操作：
  
  • 看一看第二行 -> 第三行是如何操作的：
    • 第一位和最后一位都是1，中间的数字再进行计算。
    • row.add(dg.get(numRows - 2).get(j - 1) + dg.get(numRows - 2).get(j))

2. 解题代码

 public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> dg = new ArrayList<>();
        if(numRows == 0)
            return dg;
        if(numRows == 1){
            dg.add(new ArrayList<>());
            dg.get(0).add(1);
            return dg;
        }

        //dg得接收这个返回值，要不然，递归进去东西，根本没有更新
        dg = generate(numRows - 1 );
        List<Integer> row = new ArrayList<>();
        row.add(1);
        //假设numRows = 3，那么它那一行就应该有3个元素，又是用list存储的，所以j < numRows - 1。
        for(int j = 1; j < numRows - 1; j++){
            //-2的原因是因为list是从0开始存储的，而要的数据为上一层的数据
            row.add(dg.get(numRows - 2).get(j - 1) + dg.get(numRows - 2).get(j));
        }
        row.add(1);
        dg.add(row);
        return dg;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

法二：动态规划

1. 解题思路

• 和法一比较类似，只是将递归换成了迭代。引入了Prerow，保存上一个list中的数据。

2. 解题代码

 public static List<List<Integer>> generate1(int numRows){
        List<List<Integer>> dp = new ArrayList<>();
        if(numRows == 0)
            return dp;
        //考虑用迭代来操作
        dp.add(new ArrayList<>());
        dp.get(0).add(1);
        //i 为行数
        for(int i = 2; i <= numRows; i++){
            List<Integer> row = new ArrayList<>();
            //i表示的是行数，而dp是从0开始存的，上一个为dp[0]，也就是第一行
            List<Integer> Prerow = dp.get(i - 2);
            row.add(1);
            //一行当中第一个元素为1，最后一个元素也为1，所以为j
            for(int j = 1; j < i - 1; j++) {
                row.add(Prerow.get(j - 1) + Prerow.get(j));
            }
            row.add(1);
            //一行结束了，要并入总的list里面
            dp.add(row);
        }
        return dp;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

法三：暴力破解

1. 解题思路

• 一行一行遍历，该加的数字相加。

2. 解题代码

    public static List<List<Integer>> generate2(int numRows) {
        List<List<Integer>> res = new ArrayList<>();

        for(int i = 0;i<numRows;i++){
            List<Integer> ans = new ArrayList<>();
            for(int j = 0;j<=i;j++){
                if(j == 0 || j == i){
                    ans.add(1);
                }else{
                    ans.add(res.get(i-1).get(j-1)+res.get(i-1).get(j));
                }
            }
            res.add(ans);
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

参考：https://leetcode.cn/problems/pascals-triangle/solution/javadi-gui-dong-tai-gui-hua-by-jeromememory/