Leetcode 118:Pascal's Triangle 杨辉三角

简介: 118:Pascal's Triangle 杨辉三角Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。

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); 在i不等于0时才加上1,这样可省略

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

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

目录
相关文章
|
6月前
|
索引
leetcode-119:杨辉三角 II
leetcode-119:杨辉三角 II
58 0
|
5月前
|
缓存 算法 数据可视化
LeetCode 题目 119:杨辉三角 II
LeetCode 题目 119:杨辉三角 II
|
5月前
|
存储 SQL 算法
LeetCode 题目 118:杨辉三角
LeetCode 题目 118:杨辉三角
|
6月前
leetcode代码记录(杨辉三角
leetcode代码记录(杨辉三角
38 1
【每日一题】4.LeetCode——杨辉三角
【每日一题】4.LeetCode——杨辉三角
|
6月前
leetcode-118:杨辉三角
leetcode-118:杨辉三角
56 0
|
算法
【LeetCode】136. 只出现一次的数字、118. 杨辉三角
目录 136. 只出现一次的数字 118. 杨辉三角
48 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
54 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
107 2