JS leetcode 杨辉三角Ⅱ 题解分析

壹 ❀ 引

今天是的题目来自leetcode的119. 杨辉三角 II,还记得几天前,我第一次遇到118. 杨辉三角,一段代码调试半天写不出来,这次遇到升级版终于开开心心快快乐乐轻松解题,题目描述如下:

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

JS leetcode 杨辉三角Ⅱ 题解分析

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

示例:

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

按照惯例,我先说说我的解题思路,然后再看看优质的解题方案。

贰 ❀ 解题思路

由于在JS leetcode 杨辉三角 超详细题解分析这篇文章中,我已经详细给出了杨辉三角的一些规律,这里就简笔带过。

首先这道题与之前的杨辉三角还是有点区别,之前的题目输入3,第三层为[1,2,1],而本题输入3输出的却是[1,3,3,1],说明本题可以理解成k为0时输出[1]

其次,能帮助解答本题的三个杨辉三角规律分别是:

  • 杨辉三角的第N层有N个元素,比如第一层一个,第二层2个。
  • 杨辉三角每层的第一个和最后一个元素毕竟是1
  • 杨辉三角第N层的第i个元素等于N-1层的第 i-1 个元素与N-1层的第 i 个元素的和

好了,说说我的想法,我需要2个数组,一个用于保存当前层元素的数组current,还需要一个数组previous用来存N-1层数组的元素。

比如第一层时current数组为[1],previous为[]空数组。

第二层时previous就变成了[1],current变成了[1,1]

第三层时previous变成[1,1],current变成[]1,2,1]

也就是说在进入下层时总是将current赋予previous,而previous又会成为下层元素计算的关键。

思路说了,直接贴我的实现:

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function (rowIndex) {
    // 建立两个数组,一个表示当层,一个表示上一层
    // 用于保存上一层
    var previous = [];
    // 外层for决定要建到第几层,注意,这题0表示第一次,所以是i <= rowIndex而不是i < rowIndex
    for (var i = 0; i <= rowIndex; i++) {
        // 内层for决定这层有几个数字,i层有i个
        var current = []
        for (var j = 0; j <= i; j++) {
            // 这两种情况表示每层的第一个元素和最后一个元素
            if (j === 0 || j === i) {
                current.push(1);
            } else {
                // 除去第一个和最后一个元素,它都应该等于上层两个数字的和
                current.push(previous[j - 1] + previous[j]);
            };
        };
        // 记录当前层,用于下一层计算
        previous = current;
    };
    return current;
};

注释写的贼详细了,就不过多解释了。

叁 ❀ 更棒的做法

这里引用leetcode用户ClarkChainer动态规划的思路:

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
let getRow = function (rowIndex) {
    // 创建第一层数组
    let resultArr = [1];
    for (let i = 0; i < rowIndex; i++) {
        // 每次往数组前面加个数字0
        resultArr.unshift(0);
        for (let j = 0; j <= i; j++) {
            // 套用我们前面说的杨辉三角的规律
            resultArr[j] = resultArr[j] + resultArr[j + 1];
        };
    };
    return resultArr;
};

我看到这段代码第一感觉就是妙啊!!!!!!!!

这里一开始我们就相当于把杨辉三角的第一层创建好了,作为初始数组。前面说了,N层有N个元素,N+1层也就比N层多一个元素。而前面已知公式:

N[i] = [N-1][i-1] + [N-1][i]

而这里巧就巧在,我们在N层的前面加入了一个元素,相当于把这一层的的元素往后推了一位,此时计算公式就变成了:

N[i] = [N-1][i] + [N-1][i+1]

通过此公式来一一计算本层每个元素的值。

相比我要创建2个数组分别保存当前与上一层,这个答案好就好在只一个数组加上一个公式,模拟了我用2个数组做的事情。

JS leetcode 杨辉三角Ⅱ 题解分析

那么关于本题就说到这里了。

上一篇:Android属性动画完全解析(中),ValueAnimator和ObjectAnimator的高级用法


下一篇:国产化达梦数据库数据迁移文档:oracle11g数据库转达梦8数据库实例演示