首页 > 试题广场 >

杨辉三角

[编程题]杨辉三角

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

给出一个值numRows，生成杨辉三角的前numRows行

示例1

输入

输出

[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

算法知识视频讲解

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

HW柯可

利用杨辉三角形的这个规律：第n行的第1个数为1，第二个数为1×(n-1)，第三个数为1×(n-1)×（n-2）/2，第四个数为1×(n-1)×（n-2）/2×（n-3）/3…依此类推。

import java.util.ArrayList;

public class Solution {
    public ArrayList<ArrayList<Integer>> generate(int numRows) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        for(int n = 1; n <= numRows; n++){
            ArrayList<Integer> list = new ArrayList<>();
            long number = 1;
            for(int i = 1; i <= n; i++){
                list.add((int)number);
                number = number * (n - i) / i;
            } 
            res.add(list);
        }
        return res;
    }
}

编辑于 2019-07-25 13:41:57 回复(0)

Java

whynotybb

    ArrayList<ArrayList<Integer>> res=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(res.get(i-1).get(j-1)+res.get(i-1).get(j));
        }
        res.add(temp);
    }
    return res;

发表于 2019-07-20 22:00:23 回复(0)

Java

🐲龍🐉

    public ArrayList<ArrayList<Integer>> generate(int numRows) {
      ArrayList<ArrayList<Integer>> results = new ArrayList();
      if (numRows < 1) {
        return results;
      }
      ArrayList<Integer> list1 = new ArrayList();
      list1.add(1);
      results.add(list1);
      for(int i = 2; i <= numRows; i++) {
        ArrayList<Integer> lastRow = results.get(i - 2);
        ArrayList<Integer> listI = new ArrayList();
        for (int j = 1; j <= i; j++) {
          if (j == 1 || j == i) {
            listI.add(1);
          } else {
            listI.add(lastRow.get(j - 2) + lastRow.get(j - 1));
          }
        }
        results.add(listI);
      }
      return results;
    }

发表于 2019-05-09 11:46:39 回复(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)

Java

jRomann

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> generate(int numRows) {
       ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        if(numRows==0) return list;
        for(int i=0;i<numRows;i++){
            list.add(getRow(i));
        }
        return list;
    }
    public ArrayList<Integer> getRow(int rowIndex) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(rowIndex==0) {
            res.add(1);
            return res;}
        int[][] a = new int[rowIndex+1][rowIndex+1];
        for (int i = 0; i < rowIndex+1; i++) {
        Arrays.fill(a[i], 1);
    }
        //a[0][0]=1;a[1][0]=1;a[1][1]=1;
        for(int i=2;i<rowIndex+1;i++){
            for(int j=1;j<i;j++){
                a[i][j]=a[i-1][j]+a[i-1][j-1];
            }
        }
        res.add(1);
        for(int i =1;i<rowIndex;i++){
            res.add(a[rowIndex][i]);
        }
        res.add(1);
        return res;
    }
}

发表于 2018-05-30 16:57:57 回复(0)

Java

小白VI

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

发表于 2018-02-14 11:57:31 回复(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)

Java

pp11

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> generate(int numRows) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        if (numRows <= 0)
            return list;
        ArrayList<Integer> first = new ArrayList<Integer>();
        first.add(1);
        list.add(first);
        if (numRows == 1)
            return list;
        for (int k = 2; k <= numRows; ++k) {
            ArrayList<Integer> last = list.get(list.size() - 1);
            ArrayList<Integer> temp = new ArrayList<Integer>();
            temp.add(1);
            for (int i = 1; i < k - 1; ++i) {
                temp.add(last.get(i - 1) + last.get(i));
            }
            temp.add(1);
            list.add(temp);
        }
        return list;
    }
}

发表于 2017-07-31 22:20:10 回复(0)

Java

萨仁朝格图（大家去脉脉沟通）

import java.util.ArrayList; public class Solution { public ArrayList<arraylist><integer>> generate(int numRows) { ArrayList<arraylist><integer>> result = new ArrayList<arraylist><integer>>(); ArrayList<integer> addr; for(int i = 0; i < numRows; i ++){ addr = new ArrayList<integer>(); for(int j = 0; j <= i; j ++){ addr.add(getSum(result, i-1, j -1, j)); } result.add(addr); } return result; } public int getSum(ArrayList<arraylist><integer>> result,int index, int i, int j){ if(index < 0) return 1; if(result == null || result.size() == 0) return 1; if(i < 0 || j >= result.get(index).size()) return 1; else return result.get(index).get(i) + result.get(index).get(j); } }</integer></arraylist></integer></integer></integer></arraylist></integer></arraylist></integer></arraylist>

发表于 2017-07-25 11:21:41 回复(0)

Java

Holiday_12138

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

编辑于 2017-06-21 16:53:29 回复(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)

Java

城市里的养猫者

public class Solution {
public List<List<Integer>> generate(int numRows)
{ List<List<Integer>> allrows = new ArrayList<List<Integer>>();
	ArrayList<Integer> row = new ArrayList<Integer>(); for(int i=0;i<numRows;i++)
	{
		row.add(0, 1); for(int j=1;j<row.size()-1;j++)
			row.set(j, row.get(j)+row.get(j+1));
		allrows.add(new ArrayList<Integer>(row));
	} return allrows;
	
}