给定一个非负整数 num ,生成杨辉三角的前 num 行。
杨辉三角中,每个数是左上方和右上方的数之和。
数据范围:
例如当输入为4时,对应的返回值为[[1],[1,1],[1,2,1],[1,3,3,1]],打印结果如下图所示:
public int[][] generate(int num) { // write code her int[][] dp = new int[num][]; for (int i = 0; i < num; i++) { dp[i] = new int[i+1]; for (int j = 0; j < dp[i].length; j++) { dp[i][j] = 1; } for (int j = 1; j < dp[i].length -1; j++) { dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; } } return dp; }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param num int整型 * @return int整型二维数组 */ public int[][] generate (int num) { // write code here if(num == 1){ return new int[][]{{1}}; }else if(num == 2){ return new int[][]{{1}, {1, 1}}; }else{ ArrayList<List<Integer>> lists = new ArrayList<>(); // 先加入前两层 List<Integer> layer = new ArrayList<>(); layer.add(1); lists.add(new ArrayList<>(layer)); layer.add(1); lists.add(new ArrayList<>(layer)); for(int i = 2; i <= num; i++){ List<Integer> lastLayer = lists.get(i - 1); layer = new ArrayList<>(); layer.add(1); for(int k = 1; k < i; k++){ layer.add(lastLayer.get(k) + lastLayer.get(k - 1)); } layer.add(1); lists.add(new ArrayList<>(layer)); } // 把列表结果转成二维数组 int[][] res = new int[num][]; for(int i = 0; i < num; i++){ res[i] = new int[i + 1]; for(int k = 0; k < lists.get(i).size(); k++){ res[i][k] = lists.get(i).get(k); } } return res; } } }
#include <vector> class Solution { public: vector<vector<int> > generate(int num) { // write code here vector<vector<int>> res; for(int i=0;i<num;i++){ //总行数等于num for(int j=0;j<i+1;j++){ //列数和当前行数相等 if(j==0){ //插入新行,第一个数是1 res.push_back({1}); }else if(j==i){ //当前行的最后一位是1 res[i].push_back(1); }else { //公式 res[i].push_back(res[i-1][j-1]+res[i-1][j]); } } } return res; } };
package main import _"fmt" /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param num int整型 * @return int整型二维数组 */ func generate( num int ) [][]int { ans:=[][]int{[]int{1}} for i:=1;i<num;i++{ pre:=ans[len(ans)-1] tmp:=make([]int,i+1) for j:=0;j<i+1;j++{ if j==0{ tmp[j]=1 }else if j==i{ tmp[j]=1 }else{ tmp[j]=pre[j]+pre[j-1] } } ans=append(ans,tmp) } return ans }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * @param num int整型 * @return int整型二维数组 */ public int[][] generate (int num) { // write code here int[][]arr =new int[num][]; for(int i=0;i<num;i++){ arr[i]=new int[i+1]; for(int j=0;j<i+1;j++){ if(j!=0&&j!=i){ arr[i][j]=arr[i-1][j-1]+arr[i-1][j]; }else{ arr[i][j]=1; } } } return arr; } }
import java.util.*; public class Solution { //根据杨辉三角得特性来做,这里为了方便分析,把杨辉三角左对齐 // 1 // 1 1 // 1 2 1 // 1 3 3 1 // 1 4 6 4 1 //每一行都是一个数组,数组最左和最右都是1,dp[i][j]=dp[i-1][j]+dp[i-1][j-1]; public int[][] generate (int num) { int[][] res=new int[num][]; res[0]=new int[1]; //第一个是1 res[0][0]=1; for(int i=1;i<num;i++){ res[i]=new int[i+1]; for(int j=0;j<res[i].length;j++){ if(j==0||j==res[i].length-1){ res[i][j]=1; }else{ res[i][j]=res[i-1][j]+res[i-1][j-1]; } } } return res; } }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param num int整型 * @return int整型vector<vector<>> */ vector<vector<int> > generate(int num) { // write code here vector<vector<int>> result; vector<int> vec; if(num == 1){ vec.push_back(1); result.push_back(vec); return result; } else{ vector<vector<int>> temp_result = generate(num-1); result = temp_result; vector<int> temp_vec; temp_vec.push_back(1); for(int i = 0;i<temp_result[num-2].size()-1;i++){ temp_vec.push_back(temp_result[num-2][i]+temp_result[num-2][i+1]); } temp_vec.push_back(1); result.push_back(temp_vec); return result; } } };
class Solution: def generate(self , num: int) -> List[List[int]]: # write code here prev = [1] res = [[1]] if num== 1: return res for i in range(2,num+1): cur = [1] for j in range(0,len(prev)-1): cur.append(prev[j] + prev[j+1]) cur.append(1) res.append(cur) prev = cur return res
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param num int整型 * @return int整型vector<vector<>> */ vector<vector<int> > generate(int num) { vector<vector<int> > ret; if (num == 0) return ret; vector<vector<int> > arr(num, vector<int>(num, 0)); arr[0][0] = 1; int col = 0; for (int i = 1; i < num; ++i) { for (int j = 0; j < num; ++j) { col = j - 1; if (col < 0) { arr[i][j] = arr[i - 1][col + 1]; } else { arr[i][j] = arr[i - 1][col] + arr[i - 1][col + 1]; } } } for (int i = 0; i < num; ++i) { vector<int> cur; for (int j = 0; j < arr[i].size(); ++j) { if (arr[i][j] != 0) { cur.push_back(arr[i][j]); } } ret.push_back(cur); } return ret; } };
class Solution: def generate(self , num: int) -> List[List[int]]: all_res=[] # write code here for i in range(1,num+1): res=[] for j in range(i): if j==0&nbs***bsp;j==i-1: res.append(1) else: res.append(all_res[i-2][j]+all_res[i-2][j-1]) all_res.append(res) return all_res
public int[][] generate (int num) { int[][] arr=new int[num][]; for(int i=0;i<num;i++) { arr[i]=new int[i+1]; for(int j=0;j<arr[i].length;j++) { if(i==0||j==0||j==arr[i].length-1) arr[i][j]=1; else arr[i][j]=arr[i-1][j-1]+arr[i-1][j]; } } return arr; }