帕斯卡三角形&杨辉三角

今天药忘吃喽~ 2022-02-25 10:18 272阅读 0赞

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

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

**示例:**

输入: 5
    输出:
    [
         [1],
        [1,1],
       [1,2,1],
      [1,3,3,1],
     [1,4,6,4,1]
    ]

**解法**

思路1：循环遍历

public List<List<Integer>> generate(int numRows) {
    		List<List<Integer>> res = new ArrayList<List<Integer>>();
    		if(numRows<1) {
    			return res;
    		}
    		List<Integer> list = new ArrayList<Integer>();
    		list.add(1);
    		res.add(list);
    		for(int i=2;i<=numRows;i++) {
    			List<Integer> pre = res.get(res.size()-1);
    			List<Integer> cur = new ArrayList<Integer>();
    			for(int j=0;j<i;j++) {
    				if(j==0) {
    					cur.add(pre.get(0));
    				}else if (j ==i-1) {
    					cur.add(pre.get(pre.size()-1));
    				}else {
    					cur.add(pre.get(j-1)+pre.get(j));
    				}
    			}
    			res.add(cur);
    		}
    		return res;
        }

思路1代码优化

/**
     * 时间复杂度O(n^2)
     * 空间复杂度O(n^2)
     * @param numRows
     * @return
     */
    public List<List<Integer>> generate(int numRows) {
    		List<List<Integer>> res = new ArrayList<List<Integer>>();
    		if(numRows<1) {
    			return res;
    		}
    		res.add(new ArrayList<Integer>());
    		res.get(0).add(1);
    		for(int i=2;i<=numRows;i++) {
    			List<Integer> pre = res.get(res.size()-1);
    			List<Integer> cur = new ArrayList<Integer>();
    			//每一行头，总是为1
    			cur.add(1);
    			for(int j=1;j<i-1;j++) {
    				cur.add(pre.get(j-1)+pre.get(j));
    			}
    			cur.add(1);
    			//每一行尾，总是为1
    			res.add(cur);
    		}
    		return res;
        }

思路2：递归

暂时无实现，后续补上

发表评论取消回复

表情：

评论列表（有 0 条评论，272人围观）

还没有评论，来说两句吧...

相关阅读

相关杨辉三角

一、什么是杨辉三角 > 杨辉三角：是二项式系数在三角形中的一种几何排列。 > 杨辉三角的每个数等于它上方两数之和。 > ![在这里插入图片描述][20201206

末蓝、/ 2022年12月26日 15:26/ 0 赞/ 313 阅读

相关菱形杨辉三角形c语言,C++输出上三角/下三角/菱形/杨辉三角形(实现代码)

1.输出上三角形第一行1个星，第二行3个星，第三行5个星，第四行7个星，第五行9个星。分析：三角形的形状由输出的空白和星组成，通过分析每一行输出几个空格，几个星，就可完

秒速五厘米/ 2022年10月14日 15:54/ 0 赞/ 210 阅读

相关杨辉三角（Pascal三角形）

递归算法 import java.util.Scanner; public class TangHuiTriangle {

谁践踏了优雅/ 2022年08月04日 15:43/ 0 赞/ 229 阅读

相关杨辉三角

package day05; import java.util.Scanner; /\\ \ java基础:键盘录入/二维数组 \ Author: \ Desc

蔚落/ 2022年06月07日 14:13/ 0 赞/ 299 阅读

相关杨辉三角

题目描述按要求输入如下格式的杨辉三角 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 最多输出10层

逃离我推掉我的手/ 2022年05月05日 09:56/ 0 赞/ 319 阅读

相关杨辉三角

import java.util.Scanner; public class Main \{ public static void main(String\[\] ar

柔光的暖阳◎/ 2022年04月22日 08:38/ 0 赞/ 268 阅读

相关 LeetCode 118 杨辉三角（帕斯卡三角）

题目描述：（卤煮太懒，直接贴图了） ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nL

女爷i/ 2022年04月06日 06:16/ 0 赞/ 218 阅读

相关帕斯卡三角形&杨辉三角

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。在杨辉三角中，每个数是它左上方和右上方的数的和。示例: 输入: 5 输出:

今天药忘吃喽~/ 2022年02月25日 10:18/ 0 赞/ 273 阅读

相关杨辉三角

打印杨辉三角代码： import java.util.; public class test1 { / 输出杨辉三角 /

太过爱你忘了你带给我的痛/ 2021年09月23日 08:58/ 0 赞/ 525 阅读

相关杨辉三角

\include<stdio.h> void f(int a\[\]\[10\],int n) \{ int i=0,j=0; for(i=0;i<n;

港控/mmm°/ 2021年06月24日 13:58/ 0 赞/ 527 阅读