每日一道 LeetCode (28):杨辉三角
共 1233字,需浏览 3分钟
· 2020-08-24
❝每天 3 分钟,走上算法的逆袭之路。
❞
前文合集
代码仓库
GitHub:https://github.com/meteor1993/LeetCode
Gitee:https://gitee.com/inwsy/LeetCode
题目:杨辉三角
题目来源:https://leetcode-cn.com/problems/pascals-triangle/
给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。
在杨辉三角中,每个数是它左上方和右上方的数的和。
示例:
输入: 5 输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
套路总结
好像又出现一个新的世界,不再是二叉树了,昨天的文章忘了做总结了,今天在这里补上吧。
看到二叉树的题目,应该要想到两点基本的解题方案,要么是做 「迭代」 ,要么是做 「递归」 。
这两种方式分别对应了 「广度优先搜索」 和 「深度优先搜索」 。
「迭代」 一般使用队列来做,每一次迭代是迭代一层的所有节点。
「递归」 则是先查找子树,先一股脑的递归到一个叶子节点,再往上反。
剩下的操作就要视题目场景而定了,我也没办法一概而定,遇到题目不会做就是做题还少,多做点题就会做了。
解题思路
杨辉三角,这道题我应该在近 10 年前上大学的时候,刚接触编程的时候做过。
上面题目中给出的图形可能不是很容易理解,它前后两行没有对齐,如果对齐以后是下面这样。
这个图其实已经把杨辉三角的特点以及计算方式画的很清晰了。
首先杨辉三角的几个特点我们来总结一下:
开头第一行永远只有一个数字 1 。 除了第一行,每一行的开头和结尾都是数字 1 ,这也导致第二行的数是两个 1 。 从第三行开始,除掉开头和结尾的两个 1 ,剩下的第 i
个位置的数字值是由上面一行的第i
位和第i - 1
位两个数字加起来而得到。
差不多,能看到这三个特点就能做这道题了。
解题答案
直接看代码吧,注释啥的我都写在代码上了,比较清晰,应该不会存在不理解的情况。
public List> generate(int numRows) {
List> triangle = new ArrayList>();
// 如果是 0 ,直接返回空
if (numRows == 0) {
return triangle;
}
// 直接给第一行赋值,永远是 1
triangle.add(new ArrayList<>());
triangle.get(0).add(1);
for (int i = 1; i < numRows; i++) {
// 定义当前行
List row = new ArrayList<>();
// 定义上一行
List prevRow = triangle.get(i - 1);
// 当前行开头为 1
row.add(1);
// 计算每一个数值,结果是上一行的 j 和 j + 1 位置的和
for (int j = 1; j < i; j++) {
row.add(prevRow.get(j - 1) + prevRow.get(j));
}
// 当前行添加末尾数字 1
row.add(1);
// 把当前行添加到要返回的列表中
triangle.add(row);
}
return triangle;
}
这段代码看不懂就真的千不该万不该了,逻辑很清晰,完全顺序逻辑,从第一行开始构造,代码中的 for
循环是用来构造每一层的结构,构造完成后添加到最终要返回的那个列表中。
属实看不懂的话自己加一个 main
方法,多 debug 几次,懂了以后一定要自己不看代码自己实现一遍,加深记忆。
感谢机械工业出版社华章科技的大力支持
当当实付满200-40优惠码:TZSEAM
叠加每满100减50活动,
实现花160买400的书!
有效期:8月24日至9月6日
下周一开始可用,提前选书放购物车啦