?歡迎訂閱《leetcode》專欄，每日一題，每天進步?
帕斯卡可能是馬可波羅的親戚，馬可波羅回到歐洲后，把楊輝三角告訴了帕斯卡，最后帕斯卡漂亮了抄襲了楊輝三角
——leetcode此題熱評
前言
哈嘍，大家好，我是一條，
糊涂演算法，難得糊涂
在大佬的支持下努力刷題，以后可能會一天多更，
Question
118. 楊輝三角難度：簡單
給定一個非負整數 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
Solution
楊輝三角是高中時就接觸的知識，一個重要特性：每個數是它左上方和右上方的數的和
聽起來是不是像爬樓梯，還是用動態規劃，
- 行和列雙重回圈
- 如果是首尾元素，設為1
- 其他元素等于它左上方和右上方的數的和
Code
所有
leetcode代碼已同步至github歡迎
star
/**
* @author yitiaoIT
*/
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
for (int i = 0; i < numRows; ++i) {
List<Integer> row = new ArrayList<Integer>();
for (int j = 0; j <= i; ++j) {
if (j == 0 || j == i) {
row.add(1);
} else {
row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
}
}
ret.add(row);
}
return ret;
}
}
Result
復雜度分析
- 時間復雜度：O(N^2)
🌈尋寶
?今天是堅持刷題更文的第34/100天
?各位的點贊、關注、收藏、評論、訂閱就是一條創作的最大動力
?更多演算法題歡迎關注專欄《leetcode》
為了回饋各位粉絲，禮尚往來，給大家準備了一些演算法教學視頻和電子書
需要的小伙伴可以私信我領取，不過一定要先關注哦！不然無法發私信！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/295159.html
標籤：java
上一篇：??導圖整理陣列6:四陣列的四數之和,詳解Counter類實作哈希表計數,力扣454??
下一篇：# Day14-Java基礎