LeetCode(119):杨辉三角 II

Stella981
• 阅读 625

Easy!

题目描述:

给定一个非负索引 _k_,其中 k ≤ 33,返回杨辉三角的第 k 行。

LeetCode(119):杨辉三角 II

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

示例:

输入: 3
输出: [1,3,3,1]

进阶:

你可以优化你的算法到 O(k) 空间复杂度吗?

解题思路:

杨辉三角想必大家并不陌生,应该最早出现在初高中的数学中,其实就是二项式系数的一种写法。

        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(119):杨辉三角 II 展开的系数。例如第二层1 2 1是幂指数为2的二项式LeetCode(119):杨辉三角 II 展开形式LeetCode(119):杨辉三角 II 的系数。

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

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

由于题目有额外限制条件,程序只能使用O(k)的额外空间,那么这样就不能把每行都算出来,而是要用其他的方法,。最先考虑用的是第三条性质,算出每个组合数来生成第n行系数,代码如下:

C++ 解法一:

 1 /**
 2  * NOT Correct!
 3  */
 4 class Solution {
 5 public:
 6     vector<int> getRow(int rowIndex) {
 7         vector<int> out;
 8         if (rowIndex < 0) return out;
 9         
10         for (int i = 0; i <= rowIndex; ++i) {
11             if ( i == 0 || i == rowIndex)
12                 out.push_back(1);
13             else
14                 out.push_back (computeCnk(rowIndex, i));
15         }
16         return out;
17     }
18     
19     int computeCnk(int n, int k) {
20         if (k > n) return 0;
21         else if (k > n/2) k = n - k;
22         int numerator = 1, denomator = 1;
23         for (int i = 0; i < k; ++i) {
24             numerator *= n - i;
25             denomator *= k - i;
26         }
27         if (denomator != 0) return numerator/denomator;
28         else return 0;
29     }
30 };

本地调试输出前十行,没啥问题,拿到OJ上测试,程序在第18行跪了,中间有个系数不正确。那么问题出在哪了呢,仔细找找,原来出在计算组合数那里,由于算组合数时需要算连乘,而整形数int的数值范围只有-32768到32768之间,那么一旦n值过大,连乘肯定无法计算。而丧心病狂的OJ肯定会测试到成百上千行,所以这个方法不行。那么我们再来考虑利用第五条性质,除了第一个和最后一个数字之外,其他的数字都是上一行左右两个值之和。那么我们只需要两个for循环,除了第一个数为1之外,后面的数都是上一次循环的数值加上它前面位置的数值之和,不停地更新每一个位置的值,便可以得到第n行的数字。

C++ 解法二:

 1 class Solution {
 2 public:
 3     vector<int> getRow(int rowIndex) {
 4         vector<int> out;
 5         if (rowIndex < 0) return out;
 6         
 7         out.assign(rowIndex + 1, 0);
 8         for (int i = 0; i <= rowIndex; ++i) {
 9             if ( i == 0) {
10                 out[0] = 1;
11                 continue;
12             }
13             for (int j = rowIndex; j >= 1; --j) {
14                 out[j] = out[j] + out[j-1];
15             }
16         }
17         return out;
18     }
19 };
点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
DaLongggggg DaLongggggg
3年前
python刷题-杨辉三角形
问题描述杨辉三角形又称Pascal三角形,它的第i1行是(ab)i的展开式的系数。  它的一个重要性质是:三角形中的每个数字等于它两肩上的数字相加。  下面给出了杨辉三角形的前4行:1111211331  给出n,输出它的前n行。输入格式输入包含一个数n。输出格式输出杨辉三角形的前n行。每一行从这一行的第一个数开始依次
Stella981 Stella981
3年前
Android So动态加载 优雅实现与原理分析
背景:漫品Android客户端集成适配转换功能(基于目标识别(So库35M)和人脸识别库(5M)),导致apk体积50M左右,为优化客户端体验,决定实现So文件动态加载.!(https://oscimg.oschina.net/oscnet/00d1ff90e4b34869664fef59e3ec3fdd20b.png)点击上方“蓝字”关注我
Stella981 Stella981
3年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Stella981 Stella981
3年前
Leetcode 363.矩形区域不超过k的最大数值和
矩形区域不超过k的最大数值和给定一个非空二维矩阵 _matrix_和一个整数_k_,找到这个矩阵内部不大于_k_的最大矩形和。示例:输入:matrix\\1,0,1\,\0,2,3\\,k2输出:2解释: 矩形区域 \\0,1\,
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
10个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这