沈阳高端网站制作公司,上海鹭城建设集团网站,艺术设计公司名字,分销 社交 电商系统#x1f4da;博客主页#xff1a;爱敲代码的小杨.
✨专栏#xff1a;《Java SE语法》
❤️感谢大家点赞#x1f44d;#x1f3fb;收藏⭐评论✍#x1f3fb;#xff0c;您的三连就是我持续更新的动力❤️
#x1f64f;小杨水平有限#xff0c;欢迎各位大佬指点…
博客主页爱敲代码的小杨.
✨专栏《Java SE语法》
❤️感谢大家点赞收藏⭐评论✍您的三连就是我持续更新的动力❤️
小杨水平有限欢迎各位大佬指点相互学习进步 文章目录 1.题目描述示例1示例2提示 2. 解题思路3. 代码4. 复杂度分析 1.题目描述
给定一个非负整数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 numRosw 30
题目链接
2. 解题思路
杨辉三角的性质
三角形的每一行的第一个数字和最后一个数字都是1。每一个三角的元素等于上一行此位置左边的元素与上一行此位置元素的和。
题解
杨辉三角的第0行只有一个数1。对于 1 ≤ i numRows。用pervRow表示杨辉三角的第 i - 1行用curRow表示杨辉三角的第 i 行.
将 1 添加到curRow表示当前行的首个数是1当前行的中间 i - 1个数分别等于其上方两数之和因此对于 1 j i有curRow[j] pervRow[j] pervRow[j - 1] 依次将每个pervRow[j] pervRow[j - 1]添加到curRow中。将 1添加到curRow表示当前行的末尾数是1.此时得到完整的curRow将curRow添加到杨辉三角。
3. 代码
class Solution {public ListListInteger generate(int numRows) {// 定义一个二维数组ListListInteger ret new ArrayList();ListInteger list new ArrayList();list.add(1);ret.add(list);for (int i 1; i numRows; i) {// 每循环一次 就是一行ListInteger curRow new ArrayList();curRow.add(1); // 一行的第一个元素// 处理中间元素ListInteger pervRow ret.get(i - 1);for (int j 1; j i; j) {int x pervRow.get(j) pervRow.get(j - 1);curRow.add(x);}//最后一个元素curRow.add(1);ret.add(curRow);}return ret;}
}运行结果 4. 复杂度分析
时间复杂度O(numRows2)因为计算总数为 1 2 3 … numRows。空间复杂度O(numRows2)因为每次计算都会被保留下来因此空间复杂度的规模与时间复杂度相同。
