原题
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例:
输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1] ]
解法
思想
根据上一行生成下一行，避免重复计算
代码
class Solution {
public List<List<Integer>> generate(int numRows) {
List<Integer> row = new ArrayList();
List<List<Integer>> ret = new ArrayList<List<Integer>>();
for(int n = 0;n<numRows;n++){
row = getRow(n+1,row);
ret.add(row);
}
return ret;
}
//n:第n行，nums：上一行（n-1行）的列表
public List<Integer> getRow(int n,List<Integer> nums){
List<Integer> ret = new ArrayList();
ret.add(1);//第一个1不需要计算
if(n==1){//第一行直接返回
return ret;
}
for(int i=1;i<(n+1)/2;i++){//由上一行的数相加得到结果
ret.add(nums.get(i-1)+nums.get(i));
}
int size = n/2;
for(int i=0;i<size;i++){//镜像处理
ret.add(ret.get(size-i-1));
}
return ret;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode118-%e6%9d%a8%e8%be%89%e4%b8%89%e8%a7%92/
相关推荐
-
leetcode264-丑数II
原题 编写一个程序，找出第 n 个丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。 示例: 输入： n = 10 输出： 12 解释： 1, 2, 3, 4, 5, 6, ...
-
leetcode122-买卖股票的最佳时机II
原题 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 注意： 你不能同...
-
leetcode99-恢复二叉搜索树
原题 二叉搜索树中的两个节点被错误地交换。 请在不改变其结构的情况下，恢复这棵树。 示例 1: 输入: [1,3,null,null,2] 1 ...
-
leetcode297-二叉树的序列化与反序列化
原题 序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。...
-
leetcode153-寻找旋转排序数组中的最小值
原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值，...
-
leetcode611-有效三角形的个数
原题 给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。 示例1: 输入： [2,2,3,4] 输出： 3 解释： 有效的组合是: 2,3,4 (使用...
-
leetcode131-分割回文串
原题 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 返回 s 所有可能的分割方案。 示例: 输入: "aab" 输出: [ ["aa","b"], ...
-
leetcode443-压缩字符串
原题 给定一组字符，使用原地算法将其压缩。 压缩后的长度必须始终小于或等于原数组长度。 数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。 在完成原地修改输入数组后，...
-
leetcode189-旋转数组
原题 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。 示例1: 输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4...
-
leetcode26-删除排序数组中的重复项
原题 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空...