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 行。
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)
会在每次进入第一次循环后判断一次。本着减少资源消耗的原则,应当提到外面。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
golang下载gocolly/colly
git clone https://github.com/golang/net.git src/github.com/golang/netgit clone https://github.com/golang/sys.git src/github.com/golang/sysgit clone https://github.com/golang/tools.git src/github.com/golang/toolsgit clone https://github.com/golang/lint.git src/github.com/golang/lintgit clone https://github.com/golang/mod.git src/github.com/golang/modgit clone https://github.com/golang/text.git src/github.com/golang/textgit clone https://github.com/golang/crypto.git src/github.com/golang/crypto然后复...
- 下一篇
Leetcode 54:Spiral Matrix 螺旋矩阵
54:Spiral Matrix 螺旋矩阵 Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. 给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。 Example 1: Input: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] Output: [1,2,3,6,9,8,7,4,5] Example 2: Input: [ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12] ] Output: [1,2,3,4,8,12,11,10,9,5,6,7] 解题思路: 参考例二,观察索引改变方式:(0,0)--->(0,3)、(0,3)--->((2,3)--->(2,0)--->(1,0)--->(1,2) 从(0,3)看,分别是:向下 横坐标自增1,到2;向左:纵坐标自减1 ...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- CentOS7,CentOS8安装Elasticsearch6.8.6
- CentOS6,CentOS7官方镜像安装Oracle11G
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- CentOS8编译安装MySQL8.0.19
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- Windows10,CentOS7,CentOS8安装Nodejs环境
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7