LeetCode（119）：杨辉三角 II

Easy！

题目描述：

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

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

示例:

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

进阶：

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

解题思路：

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

1　　　　　　　　１
2　　　　　　　１　１
3　　　　　　１　２　１
4　　　　　１　３　３　１
5　　　　１　４　６　４　１
6　　　１　５　10　10　５　１
7　　１　６　15　20　15　６　１
8　１　７　21　35　35　21　７　１
9１　８　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}$ 的系数。

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

杨辉三角以正整数构成，数字左右对称，每行由1开始逐渐变大，然后变小，回到1。
第 $n$ 行的数字个数为 $n$ 个。
第 $n$ 行的第 $k$ 个数字为组合数 $C_{n-1}^{k-1}$ 。
第 $n$ 行数字和为 $2^{n-1}$ 。
除每行最左侧与最右侧的数字以外，每个数字等于它的左上方与右上方两个数字之和（也就是说，第 $n$ 行第 $k$ 个数字等于第 $n-1$ 行的第 $k-1$ 个数字与第 $k$ 个数字的和）。这是因为有组合恒等式： $C_{n}^{i}=C_{n-1}^{i-1}+C_{n-1}^{i}$ 。可用此性质写出整个杨辉三角形。

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

C++ 解法一：

1 1 /**
2 2  * NOT Correct!
3 3  */
4 4 class Solution {
5 5 public:
6 6     vector<int> getRow(int rowIndex) {
7 7         vector<int> out;
8 8         if (rowIndex < 0) return out;
9 9         
1010         for (int i = 0; i <= rowIndex; ++i) {
1111             if ( i == 0 || i == rowIndex)
1212                 out.push_back(1);
1313             else
1414                 out.push_back (computeCnk(rowIndex, i));
1515         }
1616         return out;
1717     }
1818     
1919     int computeCnk(int n, int k) {
2020         if (k > n) return 0;
2121         else if (k > n/2) k = n - k;
2222         int numerator = 1, denomator = 1;
2323         for (int i = 0; i < k; ++i) {
2424             numerator *= n - i;
2525             denomator *= k - i;
2626         }
2727         if (denomator != 0) return numerator/denomator;
2828         else return 0;
2929     }
3030 };

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

C++ 解法二：

1 1 class Solution {
2 2 public:
3 3     vector<int> getRow(int rowIndex) {
4 4         vector<int> out;
5 5         if (rowIndex < 0) return out;
6 6         
7 7         out.assign(rowIndex + 1, 0);
8 8         for (int i = 0; i <= rowIndex; ++i) {
9 9             if ( i == 0) {
1010                 out[0] = 1;
1111                 continue;
1212             }
1313             for (int j = rowIndex; j >= 1; --j) {
1414                 out[j] = out[j] + out[j-1];
1515             }
1616         }
1717         return out;
1818     }
1919 };

LeetCode（119）：杨辉三角 II

评论区

相关推荐