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

一【题目类别】

• 数组

二【题目难度】

• 简单

三【题目编号】

• 119.杨辉三角 II

四【题目描述】

• 给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
• 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
• 

五【题目示例】

• 示例 1:

  • 输入: rowIndex = 3
  • 输出: [1,3,3,1]

• 示例 2:

  • 输入: rowIndex = 0
  • 输出: [1]

• 示例 3:

  • 输入: rowIndex = 1
  • 输出: [1,1]

六【解题思路】

• 这个题和【LeetCode每日一题】——118.杨辉三角很像，但是这个题不是求所有的，而是求某一行的值，当然可以选择上一个题的方法，求出所有的，然后再返回需要的即可，但是明显那样的时空复杂度有些大，那应该怎么办呢？
• 经过观察发现，求某一行的值的时候，我们只需要上一行的值，那我们只需要一个数组保存当前的值就行
• 既然保存好了当前行的上一行，我们就能计算当前行的值了，计算方法和昨天那道题一样，但是需要注意的是，上一行没有值要用0填充，这样不会对计算结果产生影响
• 还有两个细节需要注意：
  • 要从后向前遍历计算，否则不知道什么时候停止
  • 第一列一直是1不用计算，如果计算到第一列的话，反而会出现空指针异常（数组越界）
• 最后返回结果即可

七【题目提示】

• $0<=rowIndex<=33$

八【题目进阶】

• 你可以优化你的算法到 $O(rowIndex)$ 空间复杂度吗？

九【时间频度】

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

十【代码实现】

1. Java语言版

package Array;

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

/**
 * @Author: IronmanJay
 * @Description: 119.杨辉三角 II
 * @CreateTime: 2022-11-23  09:01
 */
public class p119_PascalsTriangleII {

    public static void main(String[] args) {
        List<Integer> res = getRow(3);
        System.out.println("res = " + res);
    }

    public static List<Integer> getRow(int rowIndex) {
        List<Integer> res = new ArrayList<Integer>();
        res.add(1);
        for (int i = 1; i <= rowIndex; i++) {
            res.add(0);
            for (int j = i; j > 0; j--) {
                res.set(j, res.get(j) + res.get(j - 1));
            }
        }
        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

2. C语言版

#include
#include

int* getRow(int rowIndex, int* returnSize)
{
	*returnSize = rowIndex + 1;
	int* res = (int*)calloc((*returnSize), sizeof(int));
	res[0] = 1;
	for (int i = 1; i <= rowIndex; i++)
	{
		for (int j = i; j > 0; j--)
		{
			res[j] = res[j] + res[j - 1];
		}
	}
	return res;
}

/*主函数省略*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

十一【提交结果】

1. Java语言版
   

2. C语言版