原题
给定一个非负整数 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/
相关推荐
-
leetcode40-组合总和II
原题 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字...
-
leetcode1413-逐步求和得到正数的最小值
原题 给你一个整数数组 nums 。你可以选定任意的 正数 startValue 作为初始值。 你需要从左到右遍历 nums 数组，并将 startValue 依次累加上 nums...
-
leetcode402-移掉K位数字
原题 给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。 注意： num 的长度小于 10002 且 ≥ k。 num 不会包含任何前导零。 ...
-
leetcode167-两数之和II-输入有序数组
原题 给定一个已按照 升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值index1和index2，其中index1必须小于index2。 说明...
-
leetcode496-下一个更大元素I
原题 给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。 nums...
-
剑指offer05-替换空格
原题（来源Leetcode） 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。 示例1: 输入： s = "We are happy." 输出： "We%20are%2...
-
leetcode219-存在重复元素II
原题 给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。 示例1...
-
leetcode136-只出现一次的数字
原题 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 说明： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗...
-
leetcode111-二叉树的最小深度
原题 给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,nul...
-
leetcode18-四数之和
原题 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 ta...