当前位置 博文首页 > 一条coding:【leetcode刷题】34.杨辉三角——Java版
?欢迎订阅《leetcode》专栏,每日一题,每天进步?
帕斯卡可能是马可波罗的亲戚,马可波罗回到欧洲后,把杨辉三角告诉了帕斯卡,最后帕斯卡漂亮了抄袭了杨辉三角
——leetcode此题热评
哈喽,大家好,我是一条。
糊涂算法,难得糊涂
在大佬的支持下努力刷题,以后可能会一天多更。
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》
为了回馈各位粉丝,礼尚往来,给大家准备了一些算法教学视频和电子书
需要的小伙伴可以私信我领取,不过一定要先关注哦!不然无法发私信!
cs上一篇:大番薯:编程术语英汉对照下一篇:没有了