【LeetCode】解题118：Pascal's Triangle

最新推荐文章于 2021-10-27 16:02:29 发布

Fayedy

最新推荐文章于 2021-10-27 16:02:29 发布

阅读量212

点赞数

分类专栏： LeetCode 文章标签： leetcode 算法杨辉三角函数 java

本文链接：https://blog.csdn.net/Fayedily/article/details/105398904

版权

LeetCode 专栏收录该内容

56 篇文章

订阅专栏

LeetCode解题 118：Pascal's Triangle

Problem 118: Pascal's Triangle [Easy]
解题思路
Solution (Java)

Problem 118: Pascal’s Triangle [Easy]

Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 5
Output:
[
 	 [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

来源：LeetCode

解题思路

杨辉三角中每一层的第j个数只需用到上一层的第j-1和第j个数，因此很容易想到每轮只需留存上一层的结果，以此计算当前层。
公式为:
$\begin{cases} 1 & j = 0;\\ 1 & j = i;\\ num(i-1, j-1) + num(i-1, j) & otherwise. \end{cases}$
其中， $n u m (i, j)$ 代表第 $i$ 层第 $j$ 个数。

Solution (Java)

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(numRows == 0) return result;
        List<Integer> last = new ArrayList<Integer>();
        for(int i = 0; i < numRows; i++){
            List<Integer> num = new ArrayList<Integer>();
            num.add(1);
            for(int j = 1; j < i; j++){
                num.add(last.get(j-1)+last.get(j));
            }
            if(i > 0){
                num.add(1);
            }
            result.add(num);
            last = num;
        }
        return result;
    }
}