做电影网站前途,网站运营与管理的含义,苏州网站建设数据网络,wordpress更换主题显示不出来题目——Leetcode:118. 杨辉三角 给定一个非负整数 numRows#xff0c;生成「杨辉三角」的前 numRows 行。 在「杨辉三角」中#xff0c;每个数是它左上方和右上方的数的和。 示例 1: 输入: numRows 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]示例 2: 输入: numRow…题目——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即 nums[i][0]nums[i][i]1。其余数字等于左上方的数加上正上方的数即 nums[i][j]nums[i−1][j−1]nums[i−1][j]。例如 413, 633 等。递推式如下 图解如下 解法数学法
new ArrayListListInteger();这里是创建一个ArrayList的实例但有一个重要的点需要注意。ArrayList的构造函数接受一个int类型的参数这个参数指定了列表的初始容量initial capacity而不是列表的大小size。
public class Solution {// 方法用于生成杨辉三角public ListListInteger generate(int numRows) {// 创建一个列表来存储杨辉三角的每一行ListListInteger nums new ArrayListListInteger();// 遍历每一行for (int i 0; i numRows; i) {// 为当前行创建一个新的ArrayListListInteger row new ArrayListInteger();// 遍历当前行的每一个元素for (int j 0; j i; j) {// 如果是当前行的第一个元素或最后一个元素则值为1if (j 0 || j i) {row.add(1);} else {// 否则值为上一行相邻两个元素之和// nums.get(i - 1) 获取上一行// .get(j - 1) 获取上一行第j-1个元素// .get(j) 获取上一行第j个元素row.add(nums.get(i - 1).get(j - 1) nums.get(i - 1).get(j));}}// 将当前行添加到nums列表中nums.add(row);}// 返回生成的杨辉三角return nums;}
}
复杂度分析 时间复杂度O(numRows2)。 空间复杂度O(1)。不考虑返回值的空间占用。
