文档章节

LeetCode:Pascal's Triangle - 帕斯卡三角形

北风其凉
 北风其凉
发布于 2015/08/15 11:06
字数 375
阅读 507
收藏 0

1、题目名称

Pascal's Triangle(帕斯卡三角形)

2、题目地址

https://leetcode.com/problems/pascals-triangle/

3、题目内容

英文:Given numRows, generate the first numRows of Pascal's triangle.

中文:给出行数numRows,生成前numRows行的帕斯卡三角形

例如,当numRows为5时,生成的三角形是这样的:

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

4、解题方法

帕斯卡三角形也叫杨辉三角形,我们可以利用该三角形的性质来逐行生成这个三角形,即:“每行的第一个和最后一个数字是1,其余数字等于前一行左上与右上两数字之和”。

一段实现本算法的Java代码如下:

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

/**
 * 功能说明:LeetCode 118 - Pascal's Triangle
 * 开发人员:Tsybius2014
 * 开发时间:2015年8月14日
 */
public class Solution {
    
    /**
     * 帕斯卡三角形
     * @param numRows 行数
     * @return
     */
    public List<List<Integer>> generate(int numRows) {
        
        if (numRows < 0) {
            return null;
        }
        
        ArrayList<List<Integer>> resultList =
            new ArrayList<List<Integer>>();
        
        if (numRows == 0) {
            return resultList;
        }
        
        //第一行
        ArrayList<Integer> firstList = new ArrayList<Integer>();
        firstList.add(1);
        resultList.add(firstList);
        
        //之后各行
        ArrayList<Integer> nextList = firstList;
        for (int i = 1; i < numRows; i++) {
            nextList = getNextArray(nextList);
            resultList.add(nextList);
        }
        
        return resultList;
    }
    
    /**
     * 给定帕斯卡三角形的一行数据,获取下一行数据
     * @param array 帕斯卡三角形某一行
     * @return 帕斯卡三角形的下一行
     */
    public ArrayList<Integer> getNextArray(ArrayList<Integer> arrayList) {

        if (arrayList == null) {
            return null;
        }

        ArrayList<Integer> nextList = new ArrayList<Integer>();

        nextList.add(1);
        for (int i = 0; i + 1 < arrayList.size(); i++) {
            nextList.add(arrayList.get(i) + arrayList.get(i + 1));
        }
        nextList.add(1);
        
        return nextList;
    }
}

END

© 著作权归作者所有

北风其凉

北风其凉

粉丝 119
博文 498
码字总数 463468
作品 4
朝阳
程序员
私信 提问
LeetCode:Pascal's Triangle II - 帕斯卡三角形2

1、题目名称 Pascal's Triangle II(帕斯卡三角形2) 2、题目地址 https://leetcode.com/problems/pascals-triangle-ii/ 3、题目内容 英文:Given an index k, return the kth row of the P......

北风其凉
2015/08/15
192
0
LeetCode 119 Pascal's Triangle II(帕斯卡三角形II)(vector、数学公式)(*)

版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50568802 翻译 原文 分析 这一题呢实际上是承接上一题的,我也...

nomasp
2016/01/23
0
0
帕斯卡三角形(杨辉三角)

原题   Given numRows, generate the first numRows of Pascal’s triangle.   For example, given numRows = 5,   Return 题目大意   给定一个正整数n,求n层帕斯卡三角形。 解题思...

一贱书生
2016/12/22
2
0
帕斯卡三角形(杨辉三角)II

原题   Given an index k, return the kth row of the Pascal’s triangle.   For example, given k = 3,   Return .   Note:   Could you optimize your algorithm to use only O......

一贱书生
2016/12/22
10
0
LeetCode 118. Pascal's Triangle

分析 难度 易 来源 https://leetcode.com/problems/pascals-triangle/ 题目 Given a non-negative integer numRows, generate the first numRows of Pascal's triangle. In Pascal's triangl......

flowingfog
2018/11/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OpenStack 简介和几种安装方式总结

OpenStack :是一个由NASA和Rackspace合作研发并发起的,以Apache许可证授权的自由软件和开放源代码项目。项目目标是提供实施简单、可大规模扩展、丰富、标准统一的云计算管理平台。OpenSta...

小海bug
昨天
5
0
DDD(五)

1、引言 之前学习了解了DDD中实体这一概念,那么接下来需要了解的就是值对象、唯一标识。值对象,值就是数字1、2、3,字符串“1”,“2”,“3”,值时对象的特征,对象是一个事物的具体描述...

MrYuZixian
昨天
6
0
数据库中间件MyCat

什么是MyCat? 查看官网的介绍是这样说的 一个彻底开源的,面向企业应用开发的大数据库集群 支持事务、ACID、可以替代MySQL的加强版数据库 一个可以视为MySQL集群的企业级数据库,用来替代昂贵...

沉浮_
昨天
6
0
解决Mac下VSCode打开zsh乱码

1.乱码问题 iTerm2终端使用Zsh,并且配置Zsh主题,该主题主题需要安装字体来支持箭头效果,在iTerm2中设置这个字体,但是VSCode里这个箭头还是显示乱码。 iTerm2展示如下: VSCode展示如下: 2...

HelloDeveloper
昨天
7
0
常用物流快递单号查询接口种类及对接方法

目前快递查询接口有两种方式可以对接,一是和顺丰、圆通、中通、天天、韵达、德邦这些快递公司一一对接接口,二是和快递鸟这样第三方集成接口一次性对接多家常用快递。第一种耗费时间长,但是...

程序的小猿
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部