LeetCode - 118 - 杨辉三角(pascals-triangle)

栏目: IT技术 · 发布时间: 5年前

内容简介:LeetCode - 118 - 杨辉三角(pascals-triangle)

Create by jsliang on 2019-6-27 07:33:45
Recently revised in 2019-6-27 08:53:00

一 目录

不折腾的前端,和咸鱼有什么区别

| 目录 | | --- | | 一 目录 | | 二 前言 | | 三 解题 | | 四 执行测试 | | 五 LeetCode Submit | | 六 知识点 | | 七 解题思路 | | 八 进一步探索 |

二 前言

  • 难度:简单

  • 涉及知识:数组

  • 题目地址:https://leetcode-cn.com/problems/pascals-triangle/

  • 题目内容

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

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

  3. 示例:

  4. 输入: 5

  5. 输出:

  6. [

  7. [1],

  8. [1,1],

  9. [1,2,1],

  10. [1,3,3,1],

  11. [1,4,6,4,1]

  12. ]

三 解题

小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 的解题思路。

  • 解题代码

  1. var generate = function(numRows) {

  2. if (numRows === 0) {

  3. return []

  4. }

  5. if (numRows === 1) {

  6. return [[1]];

  7. }

  8. let fullResult = [

  9. [1],

  10. [1, 1],

  11. ];

  12. let recursion = function(numRows) {

  13. if (numRows === 2) {

  14. return fullResult[1];

  15. }

  16. let prevArr = recursion(numRows - 1);

  17. let result = [];

  18. for (let i = 0; i < prevArr.length; i++) {

  19. if (prevArr[i] && prevArr[i + 1]) {

  20. result.push(prevArr[i] + prevArr[i + 1]);

  21. }

  22. }

  23. result = [1, ...result, 1];

  24. fullResult.push(result);

  25. return result;

  26. }

  27. recursion(numRows);

  28. return fullResult;

  29. };

四 执行测试

  1. numRows: 5

  2. return

  1. [

  2. [1],

  3. [1,1],

  4. [1,2,1],

  5. [1,3,3,1],

  6. [1,4,6,4,1]

  7. ]

五 LeetCode Submit

  1. Accepted

  2. 15/15 cases passed (76 ms)

  3. Your runtime beats 87.82 % of javascript submissions

  4. Your memory usage beats 11.38 % of javascript submissions (34 MB)

六 知识点

push()push() 方法将一个或多个元素添加到数组的末尾,并返回该数组的新长度。 push() 详细介绍

七 解题思路

天才第一步,梁氏破解路

当然是选择最简单粗暴的暴力破解啦:

  1. var generate = function(numRows) {

  2. switch (numRows) {

  3. case 0:

  4. return [];

  5. case 1:

  6. return [

  7. [1]

  8. ];

  9. case 2:

  10. return [

  11. [1],

  12. [1, 1]

  13. ];

  14. case 3:

  15. return [

  16. [1],

  17. [1, 1],

  18. [1, 2, 1],

  19. ];

  20. case 4:

  21. return [

  22. [1],

  23. [1, 1],

  24. [1, 2, 1],

  25. [1, 3, 3, 1],

  26. ];

  27. case 5:

  28. return [

  29. [1],

  30. [1, 1],

  31. [1, 2, 1],

  32. [1, 3, 3, 1],

  33. [1, 4, 6, 4, 1],

  34. ];

  35. // case 6……

  36. }

  37. };

开玩笑开玩笑~

不过,只有 15 个测试用例,暴力破解应该是最快的,哈哈。

回归正题,还是使用正常的暴力破解解题思路(卧槽,不还是暴力破解):

首先,观察多几遍题意:

  1. [

  2. [1],

  3. [1,1],

  4. [1,2,1],

  5. [1,3,3,1],

  6. [1,4,6,4,1]

  7. ]

就是说,我左边的 1 和右边的 1,是固定不动的,即:

[1,...,1]

然后,看到上面,我们应该明白,我们只需要把中间的和求出来,直接通过 ES6 的扩展运算符插入数组进去,就可以获取到第 numRows 行的代码:

[1,...prevResult,1]

最后,就是求出 prevResult

所以还是使用递归吧,在 numRows 为 2 的时候,返回 [1,1],遍历一遍结果为 [2],塞到数组中即为:[1,2,1],以此类推:

  • numsRows===3: [1,2,1]

  • numsRows===4: [1,3,3,1]

  • ……

这样,我们就完成了暴力破解的解法啦~

感觉 jsliang 还是念念不忘 switch...case...,感觉是最优解有木有!

八 进一步探索

jsliang 目前的习惯就是:

如果自己做出来了,那就看看别人的思路,兴许会眼前一亮呢……

可惜的是这一次还真没有,看起来也没简洁到哪去。

不过还是贴上来吧,我也就不讲解啦:

攻略 1

  1. var generate = function(numRows) {

  2. // 规律 a[i][j] = a[i-2][j-1]+a[i-2][j]

  3. let arr = [];

  4. if (numRows == 0) {

  5. return arr;

  6. }

  7. for (let i = 1; i < numRows + 1; i++) {

  8. var temp = [];

  9. for (let j = 0; j < i; j++) {

  10. if (j == 0 || j == i - 1) {

  11. temp.push(1);

  12. } else {

  13. temp.push(arr[i - 2][j - 1] + arr[i - 2][j]);

  14. }

  15. }

  16. arr.push(temp);

  17. }

  18. return arr;

  19. };

通过 for 遍历求出每层的值,再添加到 arr 中。

攻略 2

  1. var generate = function(numRows) {

  2. const res = [];

  3. for (let i = 0; i < numRows; i++) {

  4. if (i === 0) {

  5. res.push([1]); // 第一行 基础行

  6. } else {

  7. const arrs = [1]; // 初始化当前行的第一个元素为1

  8. const preRows = res[i - 1]; // 上一行数据

  9. for (let j = 0; j < preRows.length; j++) {

  10. // 上一行遍历获取左上方和右上方的数的和

  11. arrs.push(preRows[j] + (preRows[j + 1] || 0));

  12. }

  13. res.push(arrs);

  14. }

  15. }

  16. return res;

  17. };

比攻略 1 优秀点,可以吸取下经验。

那么,本题就此结束啦~


不折腾的前端,和咸鱼有什么区别!

LeetCode - 118 - 杨辉三角(pascals-triangle)

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

LeetCode - 118 - 杨辉三角(pascals-triangle)
jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

世界是平的

世界是平的

[美] 托马斯·弗里德曼 / 何帆、肖莹莹、郝正非 / 湖南科学技术出版社 / 2006-11 / 56.00元

当学者们讨论世界这20年发展的历史,并把目光聚集在2000年到2004年3月这一段时间时,他们将说些什么?9·11恐怖袭击还是伊拉克战争?或者,他们将讨论:科技的汇集与传播使得印度、中国和许多发展中国家成为世界商品和服务产品供给链上的一员,从而为世界大的发展中国家中的中产阶级带来了大量的财富,使这两个国家在全球化浪潮中占据更有利的位置?随着世界变得平坦,我们必须以更快的速度前进,才能在竞争中赢得胜......一起来看看 《世界是平的》 这本书的介绍吧!

SHA 加密
SHA 加密

SHA 加密工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器