Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle.
Note that the row index starts from 0.
In Pascal's triangle, each number is the sum of the two numbers directly above it.
Example:
Input: 3
Output: [1,3,3,1]
Follow up:
Could you optimize your algorithm to use only O(k) extra space?
杨辉三角想必大家并不陌生,应该最早出现在初高中的数学中,其实就是二项式系数的一种写法。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
杨辉三角形第n层(顶层称第0层,第1行,第n层即第 n+1 行,此处n为包含0在内的自然数)正好对应于二项式 展开的系数。例如第二层 1 2 1 是幂指数为2的二项式 展开形式 的系数。
杨辉三角主要有下列五条性质:
- 杨辉三角以正整数构成,数字左右对称,每行由1开始逐渐变大,然后变小,回到1。
- 第行的数字个数为个。
- 第行的第个数字为组合数 。
- 第行数字和为 。
- 除每行最左侧与最右侧的数字以外,每个数字等于它的左上方与右上方两个数字之和(也就是说,第行第个数字等于第 行的第 个数字与第个数字的和)。这是因为有组合恒等式:。可用此性质写出整个杨辉三角形。
由于题目有额外限制条件,程序只能使用 O(k) 的额外空间,那么这样就不能把每行都算出来,而是要用其他的方法, 我最先考虑用的是第三条性质,算出每个组合数来生成第n行系数,代码请参见评论区一楼。本地调试输出前十行,没啥问题,拿到 OJ 上测试,程序在第 18 行跪了,中间有个系数不正确。那么问题出在哪了呢,仔细找找,原来出在计算组合数那里,由于算组合数时需要算连乘,而整型数 int 的数值范围只有 -32768 到 32768 之间,那么一旦n值过大,连乘肯定无法计算。而丧心病狂的 OJ 肯定会测试到成百上千行,所以这个方法不行。那么我们再来考虑利用第五条性质,除了第一个和最后一个数字之外,其他的数字都是上一行左右两个值之和。那么我们只需要两个 for 循环,除了第一个数为1之外,后面的数都是上一次循环的数值加上它前面位置的数值之和,不停地更新每一个位置的值,便可以得到第n行的数字,具体实现代码如下:
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> res(rowIndex + );
res[] = ;
for (int i = ; i <= rowIndex; ++i) {
for (int j = i; j >= ; --j) {
res[j] += res[j - ];
}
}
return res;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/119
类似题目:
参考资料:
https://leetcode.com/problems/pascals-triangle-ii/
https://leetcode.com/problems/pascals-triangle-ii/discuss/38420/Here-is-my-brief-O(k)-solution
LeetCode All in One 题目讲解汇总(持续更新中...)
[LeetCode] Pascal's Triangle II 杨辉三角之二的更多相关文章
-
[LeetCode] 119. Pascal&#39;s Triangle II 杨辉三角之二
Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle. Note t ...
-
[LeetCode] 119. Pascal&#39;s Triangle II 杨辉三角 II
Given an index k, return the kth row of the Pascal's triangle. For example, given k = 3,Return [1,3, ...
-
Leetcode#118. Pascal&#39;s Triangle(杨辉三角)
题目描述 给定一个非负整数 numRows,生成杨辉三角的前 numRows 行. 在杨辉三角中,每个数是它左上方和右上方的数的和. 示例: 输入: 5 输出: [ [1], [1,1], [1,2, ...
-
LeetCode 118. Pascal&#39;s Triangle (杨辉三角)
Given numRows, generate the first numRows of Pascal's triangle. For example, given numRows = 5,Retur ...
-
每天一道LeetCode--118. Pascal&#39;s Triangle(杨辉三角)
Given numRows, generate the first numRows of Pascal's triangle. For example, given numRows = 5,Retur ...
-
LeetCode Pascal&#39;s Triangle II (杨辉三角)
题意:给出杨辉三角的层数k,返回最后一层.k=0时就是只有一个数字1. 思路:滚动数组计算前一半出来,返回时再复制另一半.简单但是每一句都挺长的. 0ms的版本: class Solution { p ...
-
LeetCode(119):杨辉三角 II
Easy! 题目描述: 给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行. 在杨辉三角中,每个数是它左上方和右上方的数的和. 示例: 输入: 3 输出: [1,3,3,1] 进阶: ...
-
LeetCode: Pascal&#39;s Triangle II 解题报告
Pascal's Triangle II Total Accepted: 19384 Total Submissions: 63446 My Submissions Question Solution ...
-
学会从后往前遍历,例 [LeetCode] Pascal&#39;s Triangle II,剑指Offer 题4
当我们需要改变数组的值时,如果从前往后遍历,有时会带来很多麻烦,比如需要插入值,导致数组平移,或者新的值覆盖了旧有的值,但旧有的值依然需要被使用.这种情况下,有时仅仅改变一下数组的遍历方向,就会避免这 ...
随机推荐
-
STM32 DMA USART ADC
转载自:http://www.cnblogs.com/UQYT/articles/2949794.html 这是一个综合的例子,演示了ADC模块.DMA模块和USART模块的基本使用. 我们在这里设置 ...
-
USACO 5.4 Twofive(DP)
非常不容易的一题,思路就是DP之后输出路径.但是此题,路径和DP的方式不一样,路径要按字典序输出. 开始写了一个版本,N 10000的时候就是过不了,后来才发现,自己的写法有问题,无法保证字典序.看了 ...
-
steps animation
<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8&quo ...
-
通过spring,在项目的任意位置获取当前Request
需要引入: import javax.servlet.http.HttpServletRequest; import org.springframework.web.context.request.R ...
-
转: adroid音视延迟 10ms的原因与解答
https://github.com/hehonghui/android-tech-frontier/blob/master/issue-9/Android%2010ms%E9%97%AE%E9%A2 ...
-
Perl 关于 use strict 的用法
什么场合要用 use strict 当你的程序有一定的行数时,尤其是在一页放不下时,或者是你找不到发生错误的原因时. 为什么要用 use strict? 众多的原因之一是帮你寻找因为错误拼写造成的错误 ...
-
删除除了 id 号不同,其他都相同的学生冗余信息
删除除了 id 号不同,其他都相同的学生冗余信息2.学生表 如下:id 号 学号 姓名 课程编号 课程名称 分数1 2005001 张三 0001 数学 692 2005002 李四 0001 数学 ...
-
用php 进行对文件的操作 (上)
如何让自己磁盘中的文件夹和目录显示在网页上?那就来看一下,用php是怎么来操作他们的吧 php中文件,一般包含两块内容,文件和目录 先来一句一句的看代码,及他的作用 运行后看一下结果 file 指的是 ...
-
如何在Anaconda中把python环境更新更高版本
把Anaconda中的python从3.5.5更新到3.6版本,不想卸载重新安装.办法如下: 开始->Anaconda Promot 在Anaconda Promot中,输入: conda up ...
-
在ASP.NET Web API和ASP.NET Web MVC中使用Ninject
先附上源码下载地址 一.准备工作 1.新建一个名为MvcDemo的空解决方案 2.新建一个名为MvcDemo.WebUI的空MVC应用程序 3.使用NuGet安装Ninject库 二.在ASP.N ...