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

gggggggbong 发布于2019-08-16 18:23 / 2607人阅读

摘要：杨辉三角给定一个非负整数，生成杨辉三角的前行。在杨辉三角中，每个数是它左上方和右上方的数的和。另外可以在内层循环加判断在不等于时才加上，这样可省略代码段，但是这个会在每次进入第一次循环后判断一次。本着减少资源消耗的原则，应当提到外面。

118:Pascal"s Triangle 杨辉三角

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

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

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> generate(int numRows) {
        List> triangle = new ArrayList>();

        if(numRows == 0) return triangle;
        List one = new ArrayList();
        one.add(1);
        triangle.add(one);
        if(numRows == 1) return triangle;
        for (int i=1;i row = new ArrayList();
            row.add(1);
            for (int j=1;j 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); 在i不等于0时才加上1，这样可省略

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

代码段，但是这个 if(i!=0)会在每次进入第一次循环后判断一次。本着减少资源消耗的原则，应当提到外面。

GPU云服务器云服务器 Triangle pascal_triangle Leetcod LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/74995.html

leetcode # 118:Pascal&#039;s Triangle 杨辉三角

摘要：杨辉三角给定一个非负整数，生成杨辉三角的前行。在杨辉三角中，每个数是它左上方和右上方的数的和。另外可以在内层循环加判断在不等于时才加上，这样可省略代码段，但是这个会在每次进入第一次循环后判断一次。本着减少资源消耗的原则，应当提到外面。 118:Pascals Triangle 杨辉三角 Given a non-negative integer numRows, generate the...

CKJOKER 2019-07-31 10:37 评论0 收藏0
Leetcode 118&119 Pascal&#039;s Triangle

摘要：首先要对特殊情况进行处理小于等于的情况。然后循环，每一次产生一个，个有个元素，每个的第一个和第个元素都是对于中间的那些元素，则找出前一个的对应位置的两个元素加和即可得到。这一道题只要求返回形式的一行的元素即可。 118 Pascals Triangle 题目详情 Given numRows, generate the first numRows of Pascals triangle....

laznrbfe 2019-08-15 13:40 评论0 收藏0
[LeetCode] 118. Pascal&#039;s Triangle

Problem Given a non-negative integer numRows, generate the first numRows of Pascals triangle. In Pascals triangle, each number is the sum of the two numbers directly above it. Example: Input: 5Output:...

sunnyxd 2019-08-16 13:34 评论0 收藏0
LeetCode 118：杨辉三角 II Pascal&#039;s Triangle II

摘要：公众号爱写作者爱写给定一个非负索引，其中，返回杨辉三角的第行。在杨辉三角中，每个数是它左上方和右上方的数的和。示例输入输出进阶你可以优化你的算法到空间复杂度吗解题思路和之前写的那篇号杨辉三角基本类似。公众号：爱写bug（ID：icodebugs）作者：爱写bug 给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。 Given a non-negative index...

KaltZK 2019-08-16 18:29 评论0 收藏0
LeetCode 118：杨辉三角 II Pascal&#039;s Triangle II

摘要：公众号爱写作者爱写给定一个非负索引，其中，返回杨辉三角的第行。在杨辉三角中，每个数是它左上方和右上方的数的和。示例输入输出进阶你可以优化你的算法到空间复杂度吗解题思路和之前写的那篇号杨辉三角基本类似。公众号：爱写bug（ID：icodebugs）作者：爱写bug 给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。 Given a non-negative index...

xiaodao 2019-07-31 11:25 评论0 收藏0