专栏首页爱写BugLeetcode # 118:Pascal's Triangle 杨辉三角

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 行。

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的情况提到循环外。

本文分享自微信公众号 - 爱写Bug(iCodeBugs)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java 反射理解(二)-- 动态加载类

    在获得类类型中,有一种方法是 Class.forName("类的全称"),有以下要点:

    希希里之海
  • Java数据结构-ArrayList最细致的解析笔记

    ArrayList是一个类,这个类有一个数组参数elementData,ArrayList集合中的元素正是保存在这个数组中,它继承了数组查询的高性能,参考第3篇...

    挨踢小子部落阁
  • 最全的Spring Boot 邮件发送的 5 种姿势!

    邮件发送其实是一个非常常见的需求,用户注册,找回密码等地方,都会用到,使用 JavaSE 代码发送邮件,步骤还是挺繁琐的,Spring Boot 中对于邮件发送...

    用户4143945
  • Java 学习笔记(14)—— 文件操作

    java文件操作主要封装在Java.io.File中,而文件读写一般采用的是流的方式,Java流封装在 java.io 包中。Java中流可以理解为一个有序的字...

    Masimaro
  • Qml开发中的性能Tips(翻译文)

    Qt支持任何标准图像格式,包括PNG和JPEG等位图格式,以及SVG等矢量图形格式。与位图图像相比,渲染SVG图像很慢。

    Qt君
  • Spring框架提供的异步执行能力

    Spring Framework分别使用TaskExecutor和TaskScheduler接口提供异步执行和任务调度的抽象。Spring还具有支持线程池或在应...

    用户4143945
  • 『互联网架构』埋点基础知识(112)

    1.javaagent 代理拦截(插桩的入口) 2.javassist 字节码修改工具 (怎么插)

    IT故事会
  • Java 反射理解(一)-- Class 类的使用

    希希里之海
  • 适合钱包应用开发的ERC20代币数据集

    Erc20Tokens数据集包含超过1000种主流的以太坊ERC20代币的描述数据清单和图标,可用于钱包等区块链应用的开发,支持使用Java、Python、Ph...

    用户1408045
  • Java数据结构LinkedList底层源码解析整理

    LinkedList集合中的每一个元素都是一个结点,将多个结点链接到一起,就是链表结构。以下是结点Node的源码,它是LinkedList的内部类。这段内容很简...

    挨踢小子部落阁

扫码关注云+社区

领取腾讯云代金券