每天 3 分鐘，走上算法的逆襲之路。
前文合集
每日一道 LeetCode 前文合集
代碼倉庫
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<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;
}
這段代碼看不懂就真的千不該萬不該了，邏輯很清晰，完全順序邏輯，從第一行開始構造，代碼中的
for
循環是用來構造每一層的結構，構造完成後添加到最終要傳回的那個清單中。
屬實看不懂的話自己加一個
main
方法，多 debug 幾次，懂了以後一定要自己不看代碼自己實作一遍，加深記憶。
掃描二維碼關注「極客挖掘機」公衆号！作者：極客挖掘機
定期發表作者的思考：技術、産品、營運、自我提升等。
本文版權歸作者極客挖掘機和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。
如果您覺得作者的文章對您有幫助，就來作者個人小站逛逛吧：
極客挖掘機