C++实现LeetCode(119.杨辉三角之二)

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

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?

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

　　　　　　　　１
１　１
１　２　１
１　３　３　１
１　４　６　４　１
１　５　10　10　５　１
１　６　15　20　15　６　１
１　７　21　35　35　21　７　１
１　８　28　56　70　56　28　８　１

杨辉三角形第n层（顶层称第0层，第1行，第n层即第 n+1 行，此处n为包含0在内的自然数）正好对应于二项式 \left(a+b\right)^{n} 展开的系数。例如第二层 1 2 1 是幂指数为2的二项式\left(a+b\right)^{2} 展开形式a^{2}+2ab+b^{2} 的系数。

由于题目有额外限制条件，程序只能使用 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 + 1);         res[0] = 1;         for (int i = 1; i <= rowIndex; ++i) {             for (int j = i; j >= 1; --j) {                 res[j] += res[j - 1];             }         }         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

到此这篇关于C++实现LeetCode(119.杨辉三角之二)的文章就介绍到这了,更多相关C++实现杨辉三角之二内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(118.杨辉三角)

    C++实现LeetCode(118.杨辉三角)

    [LeetCode] 118.Pascal's Triangle 杨辉三角 Given a non-negative integer numRows, generate the first numRows of Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it. Example: Input: 5 Output: [ [1], [1,1], [1

  • C++实现LeetCode(116.每个节点的右向指针)

    C++实现LeetCode(116.每个节点的右向指针)

    [LeetCode] 116. Populating Next Right Pointers in Each Node 每个节点的右向指针 You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition: struct Node { int val;

  • C++实现LeetCode(115.不同的子序列)

    [LeetCode] 115. Distinct Subsequences 不同的子序列 Given a string S and a string T, count the number of distinct subsequences of S which equals T. A subsequence of a string is a new string which is formed from the original string by deleting some (can be n

  • C++实现LeetCode(110.平衡二叉树)

    [LeetCode] 110.Balanced Binary Tree 平衡二叉树 Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as: a binary tree in which the depth of the two subtrees of everynode never differ by more t

  • C++实现LeetCode(120.三角形)

    [LeetCode] 120.Triangle 三角形 Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum

  • C++实现LeetCode(114.将二叉树展开成链表)

    [LeetCode] 114. Flatten Binary Tree to Linked List 将二叉树展开成链表 Given a binary tree, flatten it to a linked list in-place. For example, Given 1 / \ 2   5 / \   \ 3   4   6 The flattened tree should look like:    1 \ 2 \ 3 \ 4 \ 5 \ 6 click to show hints

  • C++实现LeetCode(111.二叉树的最小深度)

    [LeetCode] 111. Minimum Depth of Binary Tree 二叉树的最小深度 Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. Note: A leaf is a node with no child

  • C++实现LeetCode(117.每个节点的右向指针之二)

    C++实现LeetCode(117.每个节点的右向指针之二)

    [LeetCode] 117. Populating Next Right Pointers in Each Node II 每个节点的右向指针之二 Given a binary tree struct Node { int val; Node *left; Node *right; Node *next; } Populate each next pointer to point to its next right node. If there is no next right node, t

  • C++实现LeetCode(119.杨辉三角之二)

    C++实现LeetCode(119.杨辉三角之二)

    [LeetCode] 119. Pascal's Triangle II 杨辉三角之二 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

  • 基于Java实现杨辉三角 LeetCode Pascal's Triangle

    基于Java实现杨辉三角 LeetCode Pascal's Triangle

    Pascal's Triangle Given numRows, generate the first numRows of Pascal's triangle. For example, given numRows = 5, Return [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] 这道题比较简单, 杨辉三角, 可以用这一列的元素等于它头顶两元素的和来求. 数学扎实的人会看出, 其实每一列都是数学里的排列组合, 第4行, 可以用 C30 =

  • 基于Java实现杨辉三角 LeetCode Pascal's Triangle

    基于Java实现杨辉三角 LeetCode Pascal's Triangle

    Pascal's Triangle Given numRows, generate the first numRows of Pascal's triangle. For example, given numRows = 5, Return [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] 这道题比较简单, 杨辉三角, 可以用这一列的元素等于它头顶两元素的和来求. 数学扎实的人会看出, 其实每一列都是数学里的排列组合, 第4行, 可以用 C30 =

  • C# 中杨辉三角的实现

    C# 中杨辉三角的实现 问题描述:创建一个程序来求三角形.该程序提示用户输入数据,然后显示出杨辉三角的规律. // 输入描述:杨辉三角长,代表数值 // 程序输出:杨辉三角 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication2 { class Program { static void Main(string[] arg

  • python 生成器生成杨辉三角的方法(必看)

    用Python写趣味程序感觉屌屌的,停不下来 #生成器生成展示杨辉三角 #原理是在一个2维数组里展示杨辉三角,空的地方用0,输出时,转化为' ' def yang(line): n,leng=0,2*line - 1 f_list = list(range(leng+2)) #预先分配,insert初始胡会拖慢速度,最底下一行,左右也有1个空格 #全部初始化为0 for i,v in enumerate(f_list): f_list[v] = 0 ZEROLIST = f_list[:] #预

  • Python极简代码实现杨辉三角示例代码

    杨辉三角,又称贾宪三角形,帕斯卡三角形,是二项式系数在三角形中的一种几何排列. 把每一行看做一个list,写一个generator,不断输出下一行的list 实现下列输出效果: # [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,

  • PHP写杨辉三角实例代码

    复制代码 代码如下: <?php //杨辉三角 for ($i=6;$i >= 0;$i--) { for ($j=$i;$j <= 6;$j++) { if ($j <= 6-1) { echo "<b>a</b>"; }else { echo "<br />"; } } } ?> PHP打印杨辉三角自定义 复制代码 代码如下: <form method="post" ac

  • 用Python输出一个杨辉三角的例子

    关于杨辉三角是什么东西,右转维基百科:杨辉三角 稍微看一下直观一点的图: 复制代码 代码如下: 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 11 8 28 56 70 56 28 8 1 杨辉三角有以下几个特点: 每一项的值等于他左上角的数和右上角的数的和,如果左上角或者右上角没有数字,就按0计算.第N层项数总比N-1层多1个 计算第N层的杨辉三角,必须知道N-1层的数字,然后将相邻

  • C语言小程序 杨辉三角示例代码

    复制代码 代码如下: #include <stdio.h>#include <stdlib.h>int main(){ int i,j,k; int line; int *prev, *next; printf("输入要查看杨辉三角的行数(大于2):"); scanf("%d",&line); if(line < 2) {  printf("行数小于2,Goodbye!\n");  exit(1); } fo

随机推荐