首页 > 试题广场 >

杨辉三角(一)

[编程题]杨辉三角(一)
  • 热度指数：3023 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个非负整数 num ，生成杨辉三角的前 num 行。
杨辉三角中，每个数是左上方和右上方的数之和。

数据范围：

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

示例1

输入

1

输出

[[1]]
示例2

输入

4

输出

[[1],[1,1],[1,2,1],[1,3,3,1]]
算法知识视频讲解
查看答案及解析
添加回答
Java
BlueProtocol头像 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
pein531头像 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)
C#
苦行潜修者头像 苦行潜修者
using System;
using System.Collections.Generic;

class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型
     * @return int整型二维数组
     */
    public List<List<int>> generate (int num) {
        // write code here
        List<List<int>> lsls = new List<List<int>>();
        lsls.Add(new List<int>() {
            1
        });
        for (int i = 1; i < num; i++) {
            List<int> ls = new List<int>();
            lsls.Add(ls);
            for (int j = 0; j < i + 1; j++) {
                int nUB = j - 1 < 0 || j > lsls[i - 1].Count ? 0 : lsls[i - 1][j - 1];
                int nU = j >= lsls[i - 1].Count ? 0 : lsls[i - 1][j];
                ls.Add(nUB + nU);
            }
        }
        return lsls;
    }
}
编辑于 2024-03-31 22:54:17 回复(0)
Java
煎饼狗子6999头像 煎饼狗子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)
C++
牛客125976120号头像 牛客125976120号
C++的朋友写的对新手不太友好，我来个简单的。 
#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;
    }
};


发表于 2023-06-30 17:56:45 回复(0)
Go
小谷围做题家头像 小谷围做题家 
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
}

发表于 2023-03-06 21:39:26 回复(0)
Python3
贪吃的刚子在泡池子头像 贪吃的刚子在泡池子
class Solution:
    def generate(self , num: int) -> List[List[int]]:
        # write code here
        g = [[1]]   #先定义第一行[[1]]
        if num ==1:
            return g
        for n in range(1,num):    
            t = [1]    #每一行的第一个元素为1
            for i in range(1,n):
                j = g[n-1][i] + g[n-1][i-1]     #第n行的第i个元素，为上一行的第i个元素和i-1个元素之和
                t.append(j)
            t.append(1)   #每一行的最后一个元素为1
            g.append(t)
        return g

发表于 2023-02-21 10:46:34 回复(0)
Java
coffee_*头像 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)
爱睡觉的杨大爷头像 爱睡觉的杨大爷 
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;
    }
}

发表于 2022-08-09 10:21:26 回复(0)
C++
牛客32644957号头像 牛客32644957号
递归 
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;
        }
    }
};


发表于 2022-07-28 14:29:40 回复(0)
Python 3
danspace头像 danspace 
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

发表于 2022-04-22 11:20:30 回复(0)
C++
ClivenZ头像 ClivenZ 
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;
    }
};

发表于 2022-01-27 10:43:10 回复(0)
Python 3
Joy_9头像 Joy_9 
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

发表于 2022-01-12 08:05:13 回复(0)
Java
牛客196305255号头像 牛客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)
五五六头像 五五六
#include <stdio.h>
#define N 14
void main()
{
    int i, j, k, n=0, a[N][N];  /*定义二维数组a[14][14]*/
    while(n<=0||n>=13){  /*控制打印的行数不要太大，过大会造成显示不规范*/
       
        scanf("%d",&n);
    }
    for(i=1;i<=n;i++)
        a[i][1] = a[i][i] = 1;  /*两边的数令它为1，因为现在循环从1开始，就认为a[i][1]为第一个数*/
    for(i=3;i<=n;i++)
        for(j=2;j<=i-1;j++)
            a[i][j]=a[i-1][j-1]+a[i-1][j];  /*除两边的数外都等于上两顶数之和*/ 
    for(i=1;i<=n;i++){
        for(k=1;k<=n-i;k++)
            printf("   ");  /*这一行主要是在输出数之前打上空格占位，让输出的数更美观*/
        for(j=1;j<=i;j++)  /*j<=i的原因是不输出其它的数，只输出我们想要的数*/
            printf("%6d",a[i][j]);
        
        printf("\n");  /*当一行输出完以后换行继续下一行的输出*/
    }
    printf("\n");
}
发表于 2021-12-02 13:34:42 回复(0)
提交观点

问题信息

动态规划 数组
难度：
15条回答 2207浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号