Leetcode#118. Pascal's Triangle(杨辉三角)

题目描述

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

在杨辉三角中,每个数是它左上方和右上方的数的和。

示例:

输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

思路

对任意的n>0有 f(1, n)=1,(n>0)

f(1, 2)=1,(n=2)

f(i,j) = f(i-1, j-1)+f(i, j-1),i>2,j>2

代码实现

package Array;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 118. Pascal's Triangle(杨辉三角)
 * 给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。
 */
public class Solution118 {
    public static void main(String[] args) {
        Solution118 solution118 = new Solution118();
        int numRows = 1;
        List<List<Integer>> res = solution118.generate(numRows);
        System.out.println(res);
    }

    /**
     * 对任意的n>0有
     * f(1, n)=1,(n>0)
     * f(1, 2)=1,(n=2)
     * f(i,j) = f(i-1, j-1)+f(i, j-1),i>2,j>2
     *
     * @param numRows
     * @return
     */
    public List<List<Integer>> generate(int numRows) {
        if (numRows == 0) {
            return Collections.emptyList();
        }
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> sub = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    sub.add(1);
                } else {
                    List<Integer> upSub = res.get(i - 1);
                    sub.add(upSub.get(j - 1) + upSub.get(j));
                }
            }
            res.add(sub);
        }
        return res;
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏令仔很忙

这一年----On The Way

其实每次写总结,首先都要感叹一把,时间过的真的是太快了,当我们处于青春期的时候,总觉得时间过的好慢,什么时候能快点,早点上学,早点上高中,早点上大学,早点工作...

13120
来自专栏程序员的知识天地

这些拍案惊奇的智障桥段,分明是在蔑视我作为程序员的debug

作为在网络高速发展的时代背景下成长起来的一代人,网络文学几乎伴随着我们的整个青春。

13020
来自专栏程序员的知识天地

阿里巴巴程序员吐槽不加班的工作辞职吧!这是嫉妒还是被洗脑了?

在编程界,加班就是潜规则。程序员加班还有加班费,一个月下来薪资收入颇为丰厚。有人说,程序员就是把咖啡变成代码的机器。我想说,程序员就是满天星辰下敲着代码、喝咖啡...

23510
来自专栏金融民工小曾

电商平台分账交易是怎么做的?

另一篇文章讲到了电商平台的“二清”模式,在实际中,很多互联网电商平台需要分账给上面的平台商户或者其他角色,如果从严格的“二清”界定上来讲部分是属于违规进行了“信...

28610
来自专栏用户3254834的专栏

要钱有错吗?!

网络课堂的兴起,音频视频的商业化展示,当“白看”的电子书收取费用,当平民化的问答找不到答案,那些深耕领域作业的从业者执笔论经验、支桌开讲堂,富有阶层性的知识获取...

7810
来自专栏程序员的知识天地

阿里员工揭秘:很多程序员离职,在小公司当领导,只动嘴不动手!

阿里巴巴是中国知名的互联网公司,每个人或多或少的都从淘宝上购买的物品,自从1998年成立到现在,里面人才济济,里面的程序员不仅工资非常的高,不少程序员年收入竟然...

16720
来自专栏java一日一条

软件工程师如果没有自学的能力,还是转行吧

网络工程师和其他工程师有一些很微妙的差异,这个差异就是,网络世界变化极快,范围极广,涉及可深可浅,就取决于你要放自己在那个位置。

46620
来自专栏java一日一条

如何写出漂亮的 React 组件

在Walmart Labs的产品开发中,我们进行了大量的Code Review工作,这也保证了我有机会从很多优秀的工程师的代码中学习他们的代码风格与样式。在这篇...

13230
来自专栏奇点大数据

话说量化(1)

从今天开始,我来写一个叫做《话说量化》的随笔。主要是最近自己业余也在玩量化交易的模型,那就把一路玩的过程中的感想和碰到的问题记下来,和一起玩的朋友们做个分享。既...

13620
来自专栏令仔很忙

知识扩展----快速阅读

而快速阅读就是充分利用左右脑,协调快速处理视觉信息。快速阅读也叫“全脑速读”。

9910

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励