杨辉三角__牛客网

Java

AriesLi

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> generate(int numRows) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>(numRows);
        for(int i=0; i<numRows; i++){
            ArrayList<Integer> l = new ArrayList<>(i+1);
            l.add(1);
            for(int j=1; j<=i; j++){
                if(i==j) {
                    l.add(1);
                    break;
                }
                l.add(list.get(i-1).get(j-1)+list.get(i-1).get(j));
            }
            list.add(l);
        }
        return list;
    }
}

发表于 2020-01-11 10:08:03 回复(0)

Java

武培轩

Leetcode#118. Pascal's Triangle（杨辉三角）

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> 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](/profile/547241) */
    public List> generate(int numRows) {
        if (numRows == 0) {
            return Collections.emptyList();
        }
        List> res = new ArrayList();
        for (int i = 0; i < numRows; i++) {
            List sub = new ArrayList();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    sub.add(1);
                } else {
                    List upSub = res.get(i - 1);
                    sub.add(upSub.get(j - 1) + upSub.get(j));
                }
            }
            res.add(sub);
        }
        return res;
    }
}

编辑于 2018-09-02 19:08:59 回复(0)

Java

吭哧吭哧埋头干

    public ArrayList<ArrayList<Integer>> generate(int numRows) {
        ArrayList<ArrayList<Integer>> row = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> temp = new ArrayList<Integer>();
        if(numRows<=0)
            return row;
        temp.add(1);
        row.add(temp);
        for (int i = 1; i < numRows; i++) {
            temp = new ArrayList<Integer>();
            temp.add(1);
            for (int j = 1; j < i ; j++) {    
                temp.add(row.get(i-1).get(j-1)+row.get(i-1).get(j));
            }
            temp.add(1);
            row.add(temp);
        }
        return row;
    }

发表于 2018-08-21 15:49:07 回复(0)

C/C++

J.Fan

class Solution {
public:
    vector<vector<int> > generate(int numRows) {
        vector<vector<int>> vRes;
        if(numRows == 0)
            return vRes;
        vector<int> v;
        v.push_back(1);
        vRes.push_back(v);
        for(int i=1;i<numRows;i++)
        {
            vector<int> vTmp;
            for(int j=0;j<=i;j++)
            {
                if(j-1>=0 && j<vRes[i-1].size())
                    vTmp.push_back(vRes[i-1][j-1]+vRes[i-1][j]);
                else
                    vTmp.push_back(1);
            }
            vRes.push_back(vTmp);
        }
        return vRes;
    }
};

发表于 2018-08-15 20:29:01 回复(0)

oceanbase-jonny

class Solution {
public:
vector<vector<int> > generate(int numRows) {
vector<vector<int>> result;
if(numRows>0){
vector<int> a;
a.push_back(1);
result.push_back(a);
int flag=2;
while(flag<=numRows){
vector<int> b(flag,0);
for(int i=1;i<flag-1;++i){
b[i]=a[i-1]+a[i];
}
b[0]=1;
b[flag-1]=1;
result.push_back(b);
a=b;
++flag;
}
}
return result;
}
};

发表于 2018-05-10 09:56:00 回复(0)

Hotwill

class Solution {
public:
    vector<vector<int> > generate(int numRows){
        vector<vector<int>> ***;
        for (int i = 0; i < numRows; ++i){
            ***.emplace_back(i + 1, 1);
            for (int j = 1; j < i; ++j)
                ***[i][j] = ***[i - 1][j - 1] + ***[i - 1][j];
        }
        return ***;
    }
};

发表于 2017-09-03 17:14:58 回复(0)

透明猫猫

vector<vector<int> > generate(int numRows)
    {
        vector<vector<int>> res;
        if(numRows==0)
            return res;
        vector<int> first;
        first.push_back(1);
        res.push_back(first);
        if(numRows==1)
            return res;
        for(int i=1; i<numRows; i++)
        {
            vector<int> tmp;
            tmp.push_back(1);
            for(int j=i-1; j>=1; j--)
                tmp.push_back(res[i-1][j]+res[i-1][j-1]);
            tmp.push_back(1);
            res.push_back(tmp);
        }
        return res;
    }

发表于 2017-08-30 15:40:39 回复(0)

爬格子的瘦书生

class Solution {
public:
    vector<vector<int> > generate(int numRows) {
        vector<vector<int> >res;
        
        if(numRows <= 0)
            return res;
        
        generate(0,numRows,res);
        
        return res;
    }
    
    void generate(int row ,int rows, vector<vector<int> >&res){
        
        vector<int>v;
        if(row == 0 && row < rows){
           v.push_back(1);
           res.push_back(v);
           
           generate(row+1, rows, res);
           
        }
        else if(row == 1 && row < rows){
           
           v.push_back(1);          
           v.push_back(1);
           res.push_back(v);
           generate(row+1, rows, res);
        }
        else if( row > 1 && row < rows){
            
            v = vector<int>(row+1 ,1);
            for(int i = 1; i < v.size()-1; ++i)
                v.at(i) = res.at(row-1).at(i-1) + res.at(row-1).at(i);
            
            res.push_back(v);
            
             generate(row+1, rows, res);
        }
        else
        	return ;
        
        
    }
};

发表于 2017-08-30 00:49:51 回复(0)

Java

阿拉要洗澡

//简单咯

import java.util.ArrayList;

public class Solution {

ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();

public ArrayList<ArrayList<Integer>> generate(int numRows) {

if(numRows==0){

return result;

}

ArrayList<Integer> list=new ArrayList<Integer>();

list.add(1);

result.add(list);

if(numRows==1){

return result;

}

generateCore(1,numRows);

return result;

}

public void generateCore(int index,int numRows) {

if(numRows==index){

return;

}

ArrayList<Integer> list=new ArrayList<Integer>();

list.add(1);

for(int i=0;i<index-1;i++){

list.add( result.get(index-1).get(i)+result.get(index-1).get(i+1) );

}

list.add(1);

result.add(list);

generateCore(index+1,numRows);

}

发表于 2017-08-12 19:37:25 回复(0)

C/C++

nbgao

class Solution {
public:
    vector<vector<int> > generate(int numRows) {
        vector<vector<int> > res;
        for(int i=0;i<numRows;i++)
        {
        	vector<int> v;
        	for(int j=0;j<=i;j++)
        	{
        		if(j==0 || j==i)
        			v.push_back(1);
        		else if(i != 0)
        			v.push_back(res[i-1][j-1]+res[i-1][j]);
			}
			res.push_back(v);
		}
		return res;
    }
};

发表于 2017-08-09 00:46:36 回复(0)

小刀初试

注意两侧都是1，条件判断一下。

    vector<vector<int> > generate(int numRows) {
        vector<vector<int> > vs;        
        for(int i=0;i<numRows;++i){
            vector<int> v;
            for(int j=0;j<=i;++j){
                if (j==0 || j==i) v.push_back(1);
                else v.push_back(vs[i-1][j-1]+vs[i-1][j]);
            }
            vs.push_back(v);
        }
        return vs;
    }

发表于 2016-08-08 15:16:05 回复(0)

王大爷

class Solution {
public:
    vector<vector<int> > generate(int numRows) {
        vector<vector<int>> res;
        for(int i=0;i<numRows;++i){
            vector<int> tmp(i+1,1);
            for(int j=1;j<i;++j)
                tmp[j]=res[i-1][j-1]+res[i-1][j];
            res.push_back(tmp);
        }
        return res;
    }
};

编辑于 2017-09-02 10:24:35 回复(1)

shijiacheng

/**
 * 118.Pascal's Triangle
 * 杨辉三角
 * 给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
 * 在杨辉三角中，每个数是它左上方和右上方的数的和。 示例: 输入: 5 输出:
 * [
 * [1],
 * [1,1],
 * [1,2,1],
 * [1,3,3,1],
 * [1,4,6,4,1]
 * ]
 */
public class Solution {
    public static void main(String[] args) {

        Solution solution = new Solution();
        List<List<Integer>> result = solution.generate(5);
        System.out.println(result.toArray());
    }

    public List<List<Integer>> generate(int numRows) {
        if (numRows < 0) {
            return null;
        }
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> eachRow = new ArrayList<>();
            eachRow.add(1);
            for (int j = 1; j < i; j++) {
                if (i - 1 >= 0) {
                    List<Integer> lastRow = result.get(i - 1);
                    int num = lastRow.get(j - 1) + lastRow.get(j);
                    eachRow.add(j, num);
                }
            }
            if (i > 0) {
                eachRow.add(i, 1);
            }
            result.add(i, eachRow);
        }
        return result;

    }
}

发表于 2018-08-09 23:10:44 回复(0)

Java

詆調壹點

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> generate(int numRows) {
		ArrayList<ArrayList<Integer>> list = new ArrayList<>();
		for (int i = 0; i < numRows; i ++) {
			ArrayList<Integer> temp = new ArrayList<>();
			for (int j = 0; j <= i; j ++) {
				if(j == 0 || j == i) temp.add(1);
				else temp.add(list.get(i - 1).get(j - 1) + list.get(i - 1).get(j));
			}
			list.add(temp);
		}
		return list;
	}
}

编辑于 2017-03-19 22:04:35 回复(0)

牛客85499681号

#include<iostream>

#include<vector>

class Solution {

public:

/**

*

* @param numRows int整型

* @return int整型vector<vector<>>

*/

vector<vector<int> > generate(int numRows) {

vector<vector<int>> vec;

for(int i = 1 ; i <= numRows ; i++){

vector<int> tmp;

for(int j = 1; j <= i; j++){

tmp.push_back(yanghui(i, j));

}

vec.push_back(tmp);

}

// write code here

return vec;

}

int yanghui(int n, int m){

if(m == 1|| n == m) return 1;

return yanghui(n - 1, m) + yanghui(n -1, m -1);

}

};

发表于 2024-07-29 14:09:53 回复(0)

C++

好菜啊我

/*
思路：动态规划

第i行的杨辉三角基于第i-1行求得

状态定义：
F[i][j]:第i行第j列的值

从第三行开始，不算左右两端，F[i][j] = F[i-1][j]+F[i-1][j-1];

状态转移方程：
F[i][j] = F[i-1][j]+F[i-1][j-1];

*/
class Solution {
public:
    /**
     * 
     * @param numRows int整型 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > generate(int numRows) {
        if(numRows <= 0){
            return vector<vector<int>>();
        }

        vector<vector<int>> results;
        
        //循环创建数组每一行
        for(int i=0;i<numRows;i++){
            vector<int> temp(i+1,1);
            results.push_back(temp);
        }

        //填充元素
        for(int i=2;i<results.size();i++){
            for(int j=1;j<results[i].size()-1;j++){
                results[i][j] = results[i-1][j]+results[i-1][j-1];
            }
        }

         return results;
    }
};

发表于 2023-04-11 20:48:46 回复(0)

诗悦网络内推_有问必答

Erlang动态规划

解题思路

沿着题目思路写，首先构建第一轮的元素，后面每一轮的元素由上一轮元素决定，于是构建Map用于存储上一轮的数据方便取值（取不到的数据为0，符合题意）

该题属于动态规划里面明确指出前后关系的了，有些题需要自己去挖掘这个前后关系~

代码

-spec generate(NumRows :: integer()) -> [[integer()]].
generate(NumRows) ->
    do_generate(1, _LastMap = #{}, _Args = #{rows => NumRows, nums => []}).

do_generate(1, _, Args) ->
    do_generate(2, #{1 => 1}, Args#{nums := [[1]]});
do_generate(N, LastMap, Args = #{rows := NumRows, nums := Nums}) when N =
    Fun = fun(Index, Acc) ->
            L = maps:get(Index - 1, LastMap, 0),
            R = maps:get(Index, LastMap, 0),
            Num = L + R,
            [Num | Acc]
    end,
    SeqNums = lists:seq(1, N),
    RowNums = lists:foldl(Fun, [], SeqNums),
    Map = maps:from_list(lists:zip(SeqNums, RowNums)),
    NewRowNums = lists:reverse(RowNums),
    do_generate(N + 1, Map, Args#{nums := [NewRowNums | Nums]});
do_generate(_, _, _Args = #{nums := Nums}) ->
    lists:reverse(Nums).

发表于 2021-11-03 13:16:24 回复(0)

C/C++

华科不平凡

利用对称性简化：

//
// Created by jt on 2020/9/2.
//
#include <vector>
using namespace std;

class Solution {
public:
    /**
     *
     * @param numRows int整型
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > generate(int numRows) {
        // write code here
        vector<vector<int> > res;
        for (int i = 1; i <= numRows; ++i) {
            vector<int> vec(i, 1);
            for (int j = (i-1) / 2; j > 0; --j) {
                vec[j] = res[i-2][j] + res[i-2][j-1];
                vec[(i-1)-j] = vec[j];
            }
            res.push_back(vec);
        }
        return res;
    }
};

发表于 2020-09-02 12:13:54 回复(0)

Aileon

class Solution: # dp   python2.7
    def generate(self , numRows ):
        # write code here
        res = []
        dp = [1]
        if numRows == 0:
            return res
        res.append(dp[:])
        for _ in range(numRows-1):
            l = len(dp)
            for j in range(l-1,0,-1):
                dp[j] = dp[j] + dp[j-1]
            dp.append(1)
            res.append(dp[:])
        return res

发表于 2020-08-31 11:13:25 回复(0)

C/C++

Pony_Bai

class Solution {
public:
    vector<vector<int> > generate(int numRows) {
        vector<vector<int>>res;
        for(int i=0;i<numRows;++i)
        {
            vector<int>temp(i+1,1);
            for(int j=1;j<i;++j)
                temp[j]=res.back()[j-1]+res.back()[j];
            res.push_back(temp);
        }
        return res;
    }
};

发表于 2020-06-06 22:51:33 回复(0)

杨辉三角

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题