前言
哈喽，大家好，我是一条。
糊涂算法，难得糊涂
在大佬的支持下努力刷题，以后可能会一天多更。
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》
为了回馈各位粉丝，礼尚往来，给大家准备了一些算法教学视频和电子书
需要的小伙伴可以私信我领取，不过一定要先关注哦！不然无法发私信！
/
