Leetcode # 118:Pascal's Triangle 杨辉三角

爱写bug

发布于 2019-08-01 10:23:25

4930

发布于 2019-08-01 10:23:25

文章被收录于专栏：爱写Bug爱写Bug

118:Pascal's Triangle 杨辉三角

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

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

img

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

解题思路：

第一行第二行都是1，每行第一个和最后一个都为1，假设任意一个位置的数x，索引坐标是(m,n)，则x就是该数正上方的数和左上方那个数之和。即(m-1,n),(m-1,n-1)两数和。

java：

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<List<Integer>>();

        if(numRows == 0) return triangle;
        List<Integer> one = new ArrayList<Integer>();
        one.add(1);
        triangle.add(one);
        if(numRows == 1) return triangle;
        for (int i=1;i<numRows;i++){
            List<Integer> row = new ArrayList<Integer>();
            row.add(1);
            for (int j=1;j<i;j++){
                List<Integer> prev = triangle.get(i-1);
                row.add(prev.get(j-1)+prev.get(j));
            }
            row.add(1);
            triangle.add(row);
        }
        return triangle;
    }
}

python：

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        if numRows==0:return []
        triangle=[[1]]
        if numRows==1: return triangle
        for i in range(1,numRows):
            tmp=[1]
            for j in range(1,i):
                tmp.append(triangle[i-1][j-1]+triangle[i-1][j])
            tmp.append(1)
            triangle.append(tmp)
        return triangle

总结：

很简单的一道题，可以复习一下java嵌套数组数据结构。另外可以在内层循环加判断 if(i!=0) row.add(1);triangle.add(row); 意思是在第二行时开始有规律的输出，这样可省略

List<Integer> one = new ArrayList<Integer>();
        one.add(1);
        triangle.add(one);
        if(numRows == 1) return triangle;

i 也可从0开始循环，但是这个 if(i!=0)会在每次进入第一次循环后就判断一次。本着减少资源消耗的原则，应当把i=0的情况提到循环外。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2019-06-26，如有侵权请联系 cloudcommunity@tencent.com 删除

java

本文分享自爱写Bug 微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

java

登录后参与评论

0 条评论

热度