每天进步一点点🤏

杨辉三角

  • 1114 字

杨辉三角

题目

1
2
3
4
5
6
7
8
9
10
给定一个非负整数 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
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
42
43
44
45
46
47
思路:
先确定三角形的前两层为[1]和[1,1],第三层开始,为[1,2,1]
规律为首尾为1,data[] = 上一层的m[i]+m[i+1]
循环次数,为上一层可遍历次数,第二层可以遍历一次就完成整层值相加,第三层就是循环一次
第三层需要遍历两次完成前后顺序两两相加,第四层就是循环两次,总结循环次数就是上一层的数目减一

代码:

/**
 * @param Integer $numRows
 * @return Integer[][]
 */
 function generate($numRows) {
    if ($numRows === 1) {
        return [[1]];
    }

    if ($numRows === 2) {
        return [[1], [1, 1]];
    }

    // 前两层是固定的值
    $res = [
        [1],
        [1, 1],
    ];

    for ($i = 2; $i < $numRows; $i++) {
        $data = [];

        // 获取上一层的值
        $lastData = $res[$i - 1];
        // 首尾为1
        $data[]   = 1;
        
        // 遍历上一层的值,将相邻值相加的值存入$data
        for ($j = 0; $j < count($lastData) - 1; $j++) {
            $data[] = $lastData[$j] + $lastData[$j + 1];
        }

        $data[] = 1;

        $res[] = $data;
    }

    return $res;
}