公司网站更换域名流程,北京市西城区住房建设局官方网站,广州seo站内优化,三星官方网站题记#xff1a;
给定一个非负整数 numRows#xff0c;生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中#xff0c;每个数是它左上方和右上方的数的和。 示例 1: 输入: numRows 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] 示例 2: 输入: numRows 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 numRows 30
题目来源 作者LeetCode 链接https://leetcode.cn/leetbook/read/top-interview-questions-easy/xncfnv/ 来源力扣LeetCode
解题方法
首先观察这个三角形的特点杨辉三角形是一个等边三角形其中左边和右边每个格子的值都是1。
三角形斜的不好看如果我们把这个三角形往左边拉直就会发现除了两边的都是1以外其他每个格子的值都是他正上面格子和左上角格子的和。 来看下代码
public static ListListInteger generate(int numRows) {//结果值ListListInteger res new ArrayList();//每一行的元素ArrayListInteger row new ArrayList();for (int i 0; i numRows; i) {//下面一行都会比上面一行多一个元素我们在第一个位置给他加个1row.add(0, 1);//遍历每一行的结果遍历的时候跳过第一个和最后一个//每个格子的值都是他正上面和左上角元素的和for (int j 1; j row.size() - 1; j)row.set(j, row.get(j) row.get(j 1));//把结果存放到res中res.add(new ArrayList(row));}return res;
}其实上述方法也就是双循环去解决问题
第i层的第j个元素 i-1层的第j个元素 i-1层的第j-1元素
class Solution {/*** param Integer $numRows* return Integer[][]*/function generate($numRows) {$res [];for($i 0; $i $numRows; $i){ $li [];for($j 0; $j $i; $j){if($j 0 || $j $i){ //每一层的开头和结尾都是1 array_push($li, 1);}else{//第i层的第j个元素 i-1层的第j个元素 i-1层的第j-1元素array_push($li, $res[$i - 1][$j] $res[$i - 1][$j - 1]); }}array_push($res, $li);}return $res;}
}$numRows 5;
$solution new Solution();
$res $solution-generate($numRows);
print_r($res);// numRows 1; res [[1]]
// numRows 2; res [[1],[1,1]]
// numRows 3; i0;j0 $li[1] res [[1]]
// i1;j0 $li[1] j1 $li [1,1] res [[1],[1,1]]
// i2;j0 $li[1] j1 $li [1,2] j2 $li [1,2,1] res [[1],[1,1],[1,2,1]]/**输出结果为
Array
([0] Array([0] 1)[1] Array([0] 1[1] 1)[2] Array([0] 1[1] 2[2] 1)[3] Array([0] 1[1] 3[2] 3[3] 1)[4] Array([0] 1[1] 4[2] 6[3] 4[4] 1)
)
**/方法来源 作者数据结构和算法 链接https://leetcode.cn/leetbook/read/top-interview-questions-easy/xncfnv/?discussionjBwyhy 来源力扣LeetCode
作者快乐可以当钱花 链接https://leetcode.cn/leetbook/read/top-interview-questions-easy/xncfnv/?discussionrvqScA 来源力扣LeetCode
