【LeetCode每日一题】——118.杨辉三角

一【题目类别】

• 数组

二【题目难度】

• 简单

三【题目编号】

• 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]]

六【解题思路】

• 这种题目正常模拟就可以了，没什么太大难度，就是可能在语言实现的细节上需要注意一下，尤其是C语言和Java语言的区别，具体的区别可以看代码，这里只简单说一下思路：
  • 可以注意到，每行的第一个和最后一个元素值都是1
  • 除了每行的第一个和最后一个元素值，其余的元素值都是本元素值上面一行中左上方和正上方的和
• 基于这个思路这个题目就很简单的可以实现了
• 最后返回结果即可

七【题目提示】

• $1<=numRows<=30$

八【时间频度】

• 时间复杂度：$O(n^2)$，其中$n$为要生成杨辉三角的行数（numRows）
• 空间复杂度：$O(n^2)$，其中$n$为要生成杨辉三角的行数（numRows）

九【代码实现】

1. Java语言版

package Array;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: IronmanJay
 * @Description: 118.杨辉三角
 * @CreateTime: 2022-11-22  09:03
 */
public class p118_PascalsTriangle {

    public static void main(String[] args) {
        List<List<Integer>> res = generate(5);
        for (List r : res) {
            for (int i = 0; i < r.size(); i++) {
                System.out.print(r.get(i) + " ");
            }
            System.out.println();
        }
    }

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

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

2. C语言版

#include
#include

int** generate(int numRows, int* returnSize, int** returnColumnSizes)
{
	int** res = (int**)malloc(sizeof(int*)*numRows);
	*returnSize = numRows;
	*returnColumnSizes = (int*)malloc(sizeof(int)*numRows);
	for (int i = 0; i < numRows; i++)
	{
		res[i] = (int*)malloc(sizeof(int) * (i + 1));
		(*returnColumnSizes)[i] = i + 1;
		for (int j = 0; j <= i; j++)
		{
			if (j == 0 || j == i)
			{
				res[i][j] = 1;
			}
			else
			{
				int x = res[i - 1][j - 1];
				int y = res[i - 1][j];
				res[i][j] = x + y;
			}
		}
	}
	return res;
}

/*主函数省略*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

十【提交结果】

1. Java语言版
   

2. C语言版