1. 首页
  2. LeetCode

每日一道 LeetCode (28):杨辉三角

每日一道 LeetCode (28):杨辉三角

每天 3 分钟,走上算法的逆袭之路。

前文合集

每日一道 LeetCode 前文合集

代码仓库

GitHub: https://github.com/meteor1993/LeetCode

Gitee: https://gitee.com/inwsy/LeetCode

题目:杨辉三角

题目来源:https://leetcode-cn.com/problems/pascals-triangle/

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

每日一道 LeetCode (28):杨辉三角

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

示例:

输入: 5
输出:

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

套路总结

好像又出现一个新的世界,不再是二叉树了,昨天的文章忘了做总结了,今天在这里补上吧。

看到二叉树的题目,应该要想到两点基本的解题方案,要么是做 迭代 ,要么是做 递归

这两种方式分别对应了 广度优先搜索深度优先搜索

迭代 一般使用队列来做,每一次迭代是迭代一层的所有节点。

递归 则是先查找子树,先一股脑的递归到一个叶子节点,再往上反。

剩下的操作就要视题目场景而定了,我也没办法一概而定,遇到题目不会做就是做题还少,多做点题就会做了。

解题思路

杨辉三角,这道题我应该在近 10 年前上大学的时候,刚接触编程的时候做过。

上面题目中给出的图形可能不是很容易理解,它前后两行没有对齐,如果对齐以后是下面这样。

每日一道 LeetCode (28):杨辉三角

这个图其实已经把杨辉三角的特点以及计算方式画的很清晰了。

首先杨辉三角的几个特点我们来总结一下:

  • 开头第一行永远只有一个数字 1 。
  • 除了第一行,每一行的开头和结尾都是数字 1 ,这也导致第二行的数是两个 1 。
  • 从第三行开始,除掉开头和结尾的两个 1 ,剩下的第 i 个位置的数字值是由上面一行的第 i 位和第 i - 1 位两个数字加起来而得到。

差不多,能看到这三个特点就能做这道题了。

解题答案

直接看代码吧,注释啥的我都写在代码上了,比较清晰,应该不会存在不理解的情况。

public List<List<Integer>> generate(int numRows) {
     List<List<Integer>> triangle = new ArrayList<List<Integer>>();
     // 如果是 0 ,直接返回空
     if (numRows == 0) {
          return triangle;
     }

     // 直接给第一行赋值,永远是 1
     triangle.add(new ArrayList<>());
     triangle.get(0).add(1);

     for (int i = 1; i < numRows; i++) {
          // 定义当前行
          List<Integer> row = new ArrayList<>();
          // 定义上一行
          List<Integer> 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;
}

每日一道 LeetCode (28):杨辉三角

这段代码看不懂就真的千不该万不该了,逻辑很清晰,完全顺序逻辑,从第一行开始构造,代码中的 for 循环是用来构造每一层的结构,构造完成后添加到最终要返回的那个列表中。

属实看不懂的话自己加一个 main 方法,多 debug 几次,懂了以后一定要自己不看代码自己实现一遍,加深记忆。

转载声明:本博客由极客挖掘机创作,采用 CC BY 3.0 CN 许可协议。可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

QR code