JS leetcode 杨辉三角 超详细题解分析

2021-03-06 03:27

阅读:796

标签:cal   比较   其它   function   problems   img   一点   tps   基本概念   

壹 ? 引

刷leetcode的第四天,原题出处为杨辉三角,题目描述如下:

给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。

技术图片

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

示例:

输入: 5
输出:

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

那么按照惯例,我们先来分析题目。

贰 ? 解题思路

当我看到杨辉三角时,其实我是懵逼的,大学没数学,再往前追溯学过的东西早忘了,所以要实现这段程序,肯定得先了解杨辉三角基本概念。

百度一番,发现有如下结论:

技术图片
  1. 每行数字的开始与结尾都是1,比如上图三角形的两边都是由1组成。
  2. 每个数字等于它上方两数的和。
  3. 第n行的数字有n个,第一行有1个,第二行有2个...

当然杨辉三角的结论远不止这些,但知道的越多反而对我们程序实现的关键因素造成了干扰,我们需要知道的就上面三条就足够了。

OK。先说说我的思路,我们来将上面的结论转化成逻辑,为了方便理解,我们将杨辉三角理解成一个金字塔。

比如现在用户传入了一个数字5,我们可知金字塔一共就有五层,比较特殊的是,这个金字塔得从头部往下建;其次,在第n层会有n个数字,且这一层的左右两边都是1。

所以我们可以根据用户传入的数字来决定金字塔要建立多少层(遍历多少次):

var generate = function (numRows) {
    //最终返回的数组
    var result = [];
    //外层遍历控制金字塔要建几层,从上往下建
    for (var i = 0; i 

这里的 i 就代表当前层数,需要注意的是数组索引是从0开始,所以0其实对应的就是第一层,有那么一点点绕,还是要尝试去理解。

而在第 i 层会有 i个数字,所以我们得再嵌套一个循环,用来决定这一层的数字个数,以及数字内容(是1,还是上层数字两数的和)。

var generate = function (numRows) {
    //最终返回的数组
    var result = [];
    //外层遍历控制金字塔要建几层,从上往下建
    for (var i = 0; i 

可以看到j 这句代码,金字塔每层有多少个元素,其实是受层数i影响的,由于我们索引是从0开始,所以这里使用了

现在问题来了,我怎么确定这一层的数字分别是啥呢?

我们可以这么去理解,首先如果当前层索引为0的数字肯定是1;其次,当前层的最后一个数字一定也是1,最后个数字怎么表示?这层元素有几个是靠 i 决定的,i为0有一个数字(arr[0]),i为1时有2个数字(arr[0],arr[1]),可以发现最后个数字其实就是索引为 i 的情况。

除去上面两种情况,其它的数字都满足等于上层上方两数字的和,当前层为 i ,上层也就是 i-1,以第三层为例不难发现,第二个数字等于上层第一个与第二个元素的和。

所以第n个元素等于上层第n-1个元素与n个元素的和,由此我们得到如下添加当前层元素的代码:

// 每层第一个与最后一个一定是1,反之,等于上次正上方两数的和
if (j === 0 || j === i) {
    arr.push(1);
} else {
    // 等于上一层也就是i-1层的j-1与j的合
    arr.push(result[i - 1][j - 1] + result[i - 1][j])
};

由于题目要求是给定一个非负整数,所以得考虑0的情况,因此完整实现应该是这样:

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function (numRows) {
    //最终返回的数组
    var result = [];
    // 如果传入的是0或负数,直接返回空数组
    if (numRows === 0) {
        return [];
    };
    //外层遍历控制金字塔要建几层,从上往下建
    for (var i = 0; i 

当然,我在写代码之前确实有比较清晰的思路,但是在实现上部分细节没考虑好,比如我想的是当层数i>=3时才考虑元素相加的情况,所以走了不少弯路。上述代码实现参考了leetcode用户raymond-yan的实现。

另外,我在看leetcode关于数组结构卡片介绍时,提到了动态规划的概念,虽然我现在对于动态规划没有过深的理解,但是想到内层数字的length以及元素由外层数组来决定,觉得非常奇妙!!!心里总有点悟到了的感觉,哈哈哈。

那么关于杨辉三角就说到这里了!

JS leetcode 杨辉三角 超详细题解分析

标签:cal   比较   其它   function   problems   img   一点   tps   基本概念   

原文地址:https://www.cnblogs.com/echolun/p/12900771.html


评论


亲,登录后才可以留言!