我要招人

去企业版

首页 > 试题广场 >

杨辉三角(一)

[编程题]杨辉三角(一)

热度指数：3714 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

杨辉三角中，每个数是左上方和右上方的数之和。

数据范围： $1 \le num \le 30 \$

例如当输入为4时，对应的返回值为[[1],[1,1],[1,2,1],[1,3,3,1]]，打印结果如下图所示：

示例1

输入

输出

[[1]]

示例2

输入

输出

[[1],[1,1],[1,2,1],[1,3,3,1]]

算法知识视频讲解

Java

小飞快跑

核心在于

1、杨辉三角，将三角左靠齐，每一个位置的值等于坐标位置上的“上面的值”和“上面的值的前一个值”的和

2、初始化二维数组先确定行的数量，如果行列同时初始化，就会导致空值处为 0

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; j++) {
                if (j == 0 || i == j) {
                     arr[i][j] = 1;               
                }else{
                    int a = arr[i - 1][j - 1];
                    int b = arr[i - 1][j]; 
                    arr[i][j] = a + b;
                }  
            }
        }
        return arr;
    }

发表于 2024-10-09 15:36:11 回复(0)

Java

丹尼尔巴比Q了

public int[][] generate (int num) {
    // write code here
    int[][] dp = new int[num][];
    // dp[0] = new int[]{1};
    for(int i=0;i<num;i++){
        int[] cur = new int[i+1];
        for(int j=0;j<i+1;j++){
            if(j==0||j==i)
                cur[j]=1;
            else cur[j] = dp[i-1][j-1]+dp[i-1][j];
        }
        dp[i] = cur;
    }
    return dp;
}

发表于 2024-08-01 22:05:48 回复(0)

Java

煎饼狗子6999

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++){

arr[i][j]=1;

}

for(int j=1;j<arr[i].length-1;j++){

arr[i][j]=arr[i-1][j-1]+arr[i-1][j];

}

return arr;

发表于 2023-12-16 11:04:32 回复(0)

Java

coffee_*

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;
    }
}

发表于 2022-10-24 21:14:30 回复(0)

Java

BlueProtocol

	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;
	}

发表于 2022-10-13 10:48:03 回复(0)

Java

牛客196305255号

 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;
    }

发表于 2022-01-02 23:02:07 回复(0)

Java

pein531

把杨辉三角左对齐一下就可以发现：除了端点位置，对于一个中间的普遍位置而言，它的值等于其正上方和正上方左边的两个元素之和，根据这个规律进行递推，生成每一层的结果就好。

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;
        }
    }
}

发表于 2021-12-16 11:53:13 回复(0)