[LeetCode] Pascal's Triangle II 杨辉三角之二

时间:2022-06-29 18:25:01

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.

[LeetCode] Pascal's Triangle II 杨辉三角之二
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在内的自然数)正好对应于二项式 [LeetCode] Pascal's Triangle II 杨辉三角之二 展开的系数。例如第二层 1 2 1 是幂指数为2的二项式 [LeetCode] Pascal's Triangle II 杨辉三角之二 展开形式 [LeetCode] Pascal's Triangle II 杨辉三角之二 的系数。

杨辉三角主要有下列五条性质:

  1. 杨辉三角以正整数构成,数字左右对称,每行由1开始逐渐变大,然后变小,回到1。
  2. [LeetCode] Pascal's Triangle II 杨辉三角之二行的数字个数为[LeetCode] Pascal's Triangle II 杨辉三角之二个。
  3. [LeetCode] Pascal's Triangle II 杨辉三角之二行的第[LeetCode] Pascal's Triangle II 杨辉三角之二个数字为组合数 [LeetCode] Pascal's Triangle II 杨辉三角之二
  4. [LeetCode] Pascal's Triangle II 杨辉三角之二行数字和为 [LeetCode] Pascal's Triangle II 杨辉三角之二
  5. 除每行最左侧与最右侧的数字以外,每个数字等于它的左上方与右上方两个数字之和(也就是说,第[LeetCode] Pascal's Triangle II 杨辉三角之二行第[LeetCode] Pascal's Triangle II 杨辉三角之二个数字等于第 [LeetCode] Pascal's Triangle II 杨辉三角之二 行的第 [LeetCode] Pascal's Triangle II 杨辉三角之二 个数字与第[LeetCode] Pascal's Triangle II 杨辉三角之二个数字的和)。这是因为有组合恒等式:[LeetCode] Pascal's Triangle II 杨辉三角之二。可用此性质写出整个杨辉三角形。

由于题目有额外限制条件,程序只能使用 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

类似题目:

Pascal's Triangle

参考资料:

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

https://leetcode.com/problems/pascals-triangle-ii/discuss/38420/Here-is-my-brief-O(k)-solution

https://leetcode.com/problems/pascals-triangle-ii/discuss/38478/My-accepted-java-solution-any-better-code

LeetCode All in One 题目讲解汇总(持续更新中...)

[LeetCode] Pascal's Triangle II 杨辉三角之二的更多相关文章

  1. &lbrack;LeetCode&rsqb; 119&period; Pascal&&num;39&semi;s Triangle II 杨辉三角之二

    Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle. Note t ...

  2. &lbrack;LeetCode&rsqb; 119&period; Pascal&&num;39&semi;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, ...

  3. Leetcode&num;118&period; Pascal&&num;39&semi;s Triangle(杨辉三角)

    题目描述 给定一个非负整数 numRows,生成杨辉三角的前 numRows 行. 在杨辉三角中,每个数是它左上方和右上方的数的和. 示例: 输入: 5 输出: [ [1], [1,1], [1,2, ...

  4. LeetCode 118&period; Pascal&&num;39&semi;s Triangle (杨辉三角)

    Given numRows, generate the first numRows of Pascal's triangle. For example, given numRows = 5,Retur ...

  5. 每天一道LeetCode--118&period; Pascal&&num;39&semi;s Triangle(杨辉三角)

    Given numRows, generate the first numRows of Pascal's triangle. For example, given numRows = 5,Retur ...

  6. LeetCode Pascal&&num;39&semi;s Triangle II (杨辉三角)

    题意:给出杨辉三角的层数k,返回最后一层.k=0时就是只有一个数字1. 思路:滚动数组计算前一半出来,返回时再复制另一半.简单但是每一句都挺长的. 0ms的版本: class Solution { p ...

  7. LeetCode(119):杨辉三角 II

    Easy! 题目描述: 给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行. 在杨辉三角中,每个数是它左上方和右上方的数的和. 示例: 输入: 3 输出: [1,3,3,1] 进阶: ...

  8. LeetCode&colon; Pascal&&num;39&semi;s Triangle II 解题报告

    Pascal's Triangle II Total Accepted: 19384 Total Submissions: 63446 My Submissions Question Solution ...

  9. 学会从后往前遍历,例 &lbrack;LeetCode&rsqb; Pascal&&num;39&semi;s Triangle II,剑指Offer 题4

    当我们需要改变数组的值时,如果从前往后遍历,有时会带来很多麻烦,比如需要插入值,导致数组平移,或者新的值覆盖了旧有的值,但旧有的值依然需要被使用.这种情况下,有时仅仅改变一下数组的遍历方向,就会避免这 ...

随机推荐

  1. STM32 DMA USART ADC

    转载自:http://www.cnblogs.com/UQYT/articles/2949794.html 这是一个综合的例子,演示了ADC模块.DMA模块和USART模块的基本使用. 我们在这里设置 ...

  2. USACO 5&period;4 Twofive&lpar;DP&rpar;

    非常不容易的一题,思路就是DP之后输出路径.但是此题,路径和DP的方式不一样,路径要按字典序输出. 开始写了一个版本,N 10000的时候就是过不了,后来才发现,自己的写法有问题,无法保证字典序.看了 ...

  3. steps animation

    <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8&quo ...

  4. 通过spring,在项目的任意位置获取当前Request

    需要引入: import javax.servlet.http.HttpServletRequest; import org.springframework.web.context.request.R ...

  5. 转&colon; adroid音视延迟 10ms的原因与解答

    https://github.com/hehonghui/android-tech-frontier/blob/master/issue-9/Android%2010ms%E9%97%AE%E9%A2 ...

  6. Perl 关于 use strict 的用法

    什么场合要用 use strict 当你的程序有一定的行数时,尤其是在一页放不下时,或者是你找不到发生错误的原因时. 为什么要用 use strict? 众多的原因之一是帮你寻找因为错误拼写造成的错误 ...

  7. 删除除了 id 号不同&comma;其他都相同的学生冗余信息

    删除除了 id 号不同,其他都相同的学生冗余信息2.学生表 如下:id 号 学号 姓名 课程编号 课程名称 分数1 2005001 张三 0001 数学 692 2005002 李四 0001 数学 ...

  8. 用php 进行对文件的操作 (上)

    如何让自己磁盘中的文件夹和目录显示在网页上?那就来看一下,用php是怎么来操作他们的吧 php中文件,一般包含两块内容,文件和目录 先来一句一句的看代码,及他的作用 运行后看一下结果 file 指的是 ...

  9. 如何在Anaconda中把python环境更新更高版本

    把Anaconda中的python从3.5.5更新到3.6版本,不想卸载重新安装.办法如下: 开始->Anaconda Promot 在Anaconda Promot中,输入: conda up ...

  10. 在ASP&period;NET Web API和ASP&period;NET Web MVC中使用Ninject

    先附上源码下载地址 一.准备工作 1.新建一个名为MvcDemo的空解决方案 2.新建一个名为MvcDemo.WebUI的空MVC应用程序 3.使用NuGet安装Ninject库   二.在ASP.N ...