我要招人

去企业版

首页 > 试题广场 >

杨辉三角(二)

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

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

给定一个非负索引值 num ，请返回杨辉三角中从上到下第 num 层。索引值从 0 开始。

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

数据范围： $0 \le num \le 33 \$

例如当输入3时，对应的输出为[1,3,3,1]，

杨辉三角的第3行（从0开始算起）部分如下图蓝色部分所示：

示例1

输入

输出

[1]

示例2

输入

输出

[1,3,3,1]

算法知识视频讲解

Java

pein531

和“NC245 杨辉三角(一)”的思路一样，但由于只要求返回一层，我们仅需要滚动数组，每次循环仅保存要计算当前层所依赖的上一层即可。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型 
     * @return int整型一维数组
     */
    public int[] getRow (int num) {
        // write code here
        if(num == 0){
            return new int[]{1};
        }else if(num == 1){
            return new int[]{1, 1};
        }else{
            // 先构建第二层
            List<Integer> lastLayer = new ArrayList<>();
            lastLayer.add(1);
            lastLayer.add(1);
            List<Integer> layer = new ArrayList<>();
            for(int i = 2; i <= num; i++){
                layer.clear();
                layer.add(1);
                for(int k = 1; k < i; k++){
                    layer.add(lastLayer.get(k) + lastLayer.get(k - 1));
                }
                layer.add(1);
                lastLayer = new ArrayList<>(layer);
            }
            // 把列表结果转成数组
            int[] res = new int[layer.size()];
            for(int i = 0; i < layer.size(); i++){
                res[i] = layer.get(i);
            }
            return res;
        }
    }
}

发表于 2021-12-16 12:04:05 回复(0)

Java

牛客652619682号

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型
     * @return int整型一维数组
     */
    public int[] getRow (int num) {
        // write code here
        // write code here
        int[][] arr = new int[num + 1][];

        for (int i = 0; i <= num; i++) {
            arr[i] = new int[i + 1];
            for (int j = 0; j <= i; j++) {
                if ( j == 0 || j == i) {
                    arr[i][j] =1;
                } else {
                    arr[i][j] = arr[i -1 ][j] + arr[i -1 ][j - 1];
                }
            }
        }
        return arr[num];
    }
}

编辑于 2024-01-08 13:16:15 回复(0)

C++

一品统合

动态规划 + 滚动数组

class Solution {
public:
    /**
     * 动态规划+滚动数组实现，倒序实现状态转移，防止状态覆盖
     * @param num int整型 
     * @return int整型vector
     */
    vector<int> getRow(int num) {
        vector<int> res;
        for (int i = 0; i <= num; i++) {
            res.push_back(1);
            for (int j = i - 1; j > 0; j--) {
                res[j] = res[j] + res[j - 1];
            }
        }

        return res;
    }
};

发表于 2023-05-15 23:02:44 回复(0)

小谷围做题家

package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param num int整型 
 * @return int整型一维数组
*/
func getRow( num int ) []int {
    pre:=[]int{1}
    for i:=1;i<=num;i++{
        tmp:=make([]int,i+1)
        for j:=0;j<i+1;j++{
            if j-1<0||j==i{
                tmp[j]=1
            }else{
                tmp[j]=pre[j-1]+pre[j]
            }
        }
        pre=tmp
    }
    return pre
}

发表于 2023-03-09 07:53:06 回复(0)

Java

coffee_*

public int[] getRow (int n) {
        // write code here
        int num=n+1;

        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[num-1];
    }

发表于 2022-10-24 21:26:12 回复(0)

Python 3

danspace

class Solution:
    def getRow(self , num: int) -> List[int]:
        # write code here        
        prev = [1]
        if num==0: return prev
        for i in range(1,num+1):
            cur = [1]
            for j in range(len(prev)-1):
                cur.append(prev[j]+prev[j+1])
            cur.append(1)
            prev = cur
        return cur

发表于 2022-04-22 11:25:48 回复(0)

Java

wyllyh123456

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型 
     * @return int整型一维数组
     */
    public int[] getRow (int num) {
        if(num == 0){
            return new int[]{1};
        }
        int[][] dp = new int[2][num + 1];
        for (int i = 0; i <= num; i++) {
            for (int j = 0; j <= i; j++) {
                if(j == i || j == 0){
                    dp[i % 2][j] = 1;
                }else{
                    dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + dp[(i - 1) % 2][j];
                }
            }
        }
        return dp[num % 2];
    }
}

发表于 2022-02-17 14:38:44 回复(0)

Java

菲尼克斯弗兰克

1 1

1 2 1

1 3 3 1 这样存在数组里就可以了，然后顺序计算由上一行计算下一行即可

public int[] getRow (int num) {
    int[][] dp = new int[num+1][];
    dp[0] = new int[]{1};
    if (num == 0) return dp[0];
    for (int i = 1; i <= num; i++) {
        dp[i] = new int[i+1];
        for (int j = 0; j < i+1; j++) {
            if (j == 0) dp[i][j] = dp[i-1][j];
            else if (j == i) dp[i][j] = dp[i-1][j-1]; 
            else dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
        }
    }
    return dp[num];
}

发表于 2022-02-05 14:36:11 回复(0)

Java

血雨探花12138

public int[] getRow (int num) {
int[][] arr = new int[num+1][];
int i,j;
for(i=0;i<num+1;i++){
arr[i] = new int[i+1];
if(i==0)arr[0][0]=1;
else{
for(j=0;j<=i;j++){
int t1 = j-1<0?0:arr[i-1][j-1];
int t2 = j==i?0:arr[i-1][j];
arr[i][j] = t1+t2;
}
}
}
return arr[num];
}

发表于 2022-01-12 19:03:54 回复(0)