LeetCode.118 杨辉三角
站长
· 阅读数 1
题目描述：
杨辉三角 - 杨辉三角 - 力扣（LeetCode） (leetcode-cn.com)
给定一个非负整数 numRows， 生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1
输出: [[1]]
提示:
1 <= numRows <= 30
思路分析
杨辉三角的原理还是蛮简单的，这个动图这么通俗易懂，上学时代学这个的时候，也不用多久大家都能做出来。
杨辉三角具有以下性质：
- 每行数字左右对称，第一位和最后一位都是1，中间是逐渐变大，然后再逐渐变小到1。
- 每个数字等于上一行的左右两个数字之和(上面动图很简单就看出来了)
当我们知晓这两个性质之后，我们就已经弄清楚了杨辉三角的规律了，接下来就是转化为代码就好了。
AC代码
class Solution {
fun generate(numRows: Int): List<List<Int>> {
val res = arrayListOf<List<Int>>()
for (i in 0 until numRows) {
val row = arrayListOf<Int>()
//注意第一位和最后一位固定为1
for (j in 0 until i + 1) {
if (j == 0 || j == i) {
row.add(1)
} else {
row.add(res[i - 1][j - 1] + res[i - 1][j])
}
}
res.add(row)
}
return res
}
}
总结
这题虽然是简单题，按照正常思维去写的话确实也不难，分分钟做出来。
但是逛题解的时候，还发现了一个老哥的清奇的解法
取巧解法：错一位再逐个相加，28ms/12.5MB - 杨辉三角 - 力扣（LeetCode） (leetcode-cn.com)
他发现了规律，利用了数学的解法
同时还有利用高大上的动态规划的解法的
最通俗易懂的动态规划解决杨辉三角 - 杨辉三角 - 力扣（LeetCode） (leetcode-cn.com)
不得不说，解题永无止境，没看之前，我都在想，这题不就这么解吗，还能玩出什么花来？结果果然被大佬打脸。