Leetcode#118. Pascal's Triangle(杨辉三角)

it2022-05-06  0

题目描述

给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。

在杨辉三角中,每个数是它左上方和右上方的数的和。

示例:

输入: 5 输出: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]

思路

对任意的n>0有 f(1, n)=1,(n>0)

f(1, 2)=1,(n=2)

f(i,j) = f(i-1, j-1)+f(i, j-1),i>2,j>2

代码实现

package Array; import java.util.ArrayList; import java.util.Collections; import java.util.List; /** * 118. Pascal's Triangle(杨辉三角) * 给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。 */ public class Solution118 { public static void main(String[] args) { Solution118 solution118 = new Solution118(); int numRows = 1; List<List<Integer>> res = solution118.generate(numRows); System.out.println(res); } /** * 对任意的n>0有 * f(1, n)=1,(n>0) * f(1, 2)=1,(n=2) * f(i,j) = f(i-1, j-1)+f(i, j-1),i>2,j>2 * * @param numRows * @return */ public List<List<Integer>> generate(int numRows) { if (numRows == 0) { return Collections.emptyList(); } List<List<Integer>> res = new ArrayList<>(); for (int i = 0; i < numRows; i++) { List<Integer> sub = new ArrayList<>(); for (int j = 0; j <= i; j++) { if (j == 0 || j == i) { sub.add(1); } else { List<Integer> upSub = res.get(i - 1); sub.add(upSub.get(j - 1) + upSub.get(j)); } } res.add(sub); } return res; } }

转载于:https://www.cnblogs.com/wupeixuan/p/9543916.html


最新回复(0)