打印杨辉三角
LeetCode——杨辉三角
题目描述:
给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。
在杨辉三角中,每个数是它左上方和右上方的数的和。
示例:
输入: 5
输出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/pascals-triangle
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
我们先找规律,每一行的第一个数字和最后一个数字都为1,然后其余的数字都等于上一行同列的数字和上一行列数减一的数字相加之和。
我们定义一个列表,列表中的每个元素都是用来存储整型元素的列表。
首先我们判断参数numRows是不是为0,如果为0我们直接返回空列表。
如果numRows不为0,我们就先初始化杨辉三角的第一行,第一行只有一个数字,为1。
接下来我们从第二行开始遍历到numRows,我们在每一层循环中都new一个新的列表用来存储该行的数字,然后先把1存进去,然后我们存储上一行的列表,用于计算该行的数字。遍历该行第二个数字到倒数第二个数字,按照刚才找到的规律计算每一个数字。遍历完后我们在该行的末尾加上一个1。最后我们把存储该层数字的numRow列表加入到总列表中。
循环完所有层后,我们返回总列表triangle。
这里提供Java和Python的代码。
Java代码:
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<List<Integer>>();
if (numRows == 0)
return triangle;
triangle.add(new ArrayList<Integer>());
triangle.get(0).add(1);
for (int i = 2; i <= numRows; i++){
List<Integer> numRow = new ArrayList<Integer>();
List<Integer> preRow = triangle.get(i - 2);
numRow.add(1);
for (int j = 1; j < i - 1; j++){
numRow.add(preRow.get(j) + preRow.get(j - 1));
}
numRow.add(1);
triangle.add(numRow);
}
return triangle;
}
}
LeetCode测试结果:
Python代码:
class Solution(object):
def generate(self, numRows):
"""
:type numRows: int
:rtype: List[List[int]]
"""
triangle = []
if numRows == 0:
return triangle
triangle.append([1])
for i in range(2, numRows + 1):
numRow = [1]
preRow = triangle[i - 2]
for j in range(1, i - 1):
numRow.append(preRow[j] + preRow[j - 1])
numRow.append(1)
triangle.append(numRow)
return triangle
LeetCode测试结果:
本文地址:https://blog.csdn.net/weixin_45295612/article/details/110424965
上一篇: MySQL全面瓦解之查询的正则匹配详解
下一篇: input 只允许输入数字 且去掉e