[数据结构与算法]0039力扣118题---杨辉三角

力扣118题---杨辉三角

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

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

示例 1:输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例2:输入: numRows = 1
输出: [[1]]

提示:

1 <= numRows <= 30

方法代码:

? ? public List<List<Integer>> generate(int numRows) {
? ? ? ? //结果值
? ? ? ? List<List<Integer>> ret = new ArrayList<List<Integer>>();
? ? ? ? //控制层数
? ? ? ? for (int i = 0; i < numRows; i++) {
? ? ? ? ? ? //每一行的元素
? ? ? ? ? ? List<Integer> row = new ArrayList<Integer>();
? ? ? ? ? ? for (int j = 0; j <= i; j++) {
? ? ? ? ? ? ? ? //每行首尾为1
? ? ? ? ? ? ? ? if (j == 0 || j == i) {
? ? ? ? ? ? ? ? ? ? row.add(1);
? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? //每个格子的值都是他正上面和左上角元素的和
? ? ? ? ? ? ? ? ? ? row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? //把结果存放到ret中
? ? ? ? ? ? ret.add(row);
? ? ? ? }
? ? ? ? return ret;
? ? }

IEDA中测试：

import java.util.*;

public class Main {
? ? public static void main(String[] args) {
? ? ? ? int n = 5;
? ? ? ? Main solution = new Main();
? ? ? ? System.out.println(solution.generate(n));
? ? }

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

输出：
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

==================================================================

二维数组实现杨辉三角Java代码:

? ? ? ? int n = 5;
? ? ? ? int[][] array = new int[n][n];
? ? ? ? for (int i = 0; i < n; i++) {
? ? ? ? ? ? for (int j = 0; j <= i; j++) {
? ? ? ? ? ? ? ? if (j == 0 || j == i) {
? ? ? ? ? ? ? ? ? ? array[i][j] = 1;
? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? array[i][j] = array[i - 1][j - 1] + array[i - 1][j];
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }

IDEA中测试：

public class Main {
? ? public static void main(String[] args) {
? ? ? ? int n = 8;
? ? ? ? int[][] array = new int[n][n];
? ? ? ? for (int i = 0; i < n; i++) {
? ? ? ? ? ? for (int j = 0; j <= i; j++) {
? ? ? ? ? ? ? ? if (j == 0 || j == i) {
? ? ? ? ? ? ? ? ? ? array[i][j] = 1;
? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? array[i][j] = array[i - 1][j - 1] + array[i - 1][j];
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? for (int i = 0; i < n; i++) {
? ? ? ? ? ? for (int j = 0; j <= i; j++) {
? ? ? ? ? ? ? ? System.out.printf("%3d", array[i][j]);
? ? ? ? ? ? }
? ? ? ? ? ? System.out.println();
? ? ? ? }
? ? }
}

输出：
? 1
? 1 ?1
? 1 ?2 ?1
? 1 ?3 ?3 ?1
? 1 ?4 ?6 ?4 ?1
? 1 ?5 10 10 ?5 ?1
? 1 ?6 15 20 15 ?6 ?1
? 1 ?7 21 35 35 21 ?7 ?1

一维数组直接打印出杨辉三角Java代码:

public class Main {
? ? public static void main(String[] args) {
? ? ? ? int n = 8;
? ? ? ? int top = 1;
? ? ? ? int[] arr = new int[n + 1];
? ? ? ? for (int i = 1; i < n + 1; i++) {
? ? ? ? ? ? for (int j = 1; j <= i; j++) {
? ? ? ? ? ? ? ? int temp = arr[j];
? ? ? ? ? ? ? ? arr[j] = top + temp;
? ? ? ? ? ? ? ? top = temp;
? ? ? ? ? ? ? ? System.out.printf("%3d", arr[j]);
? ? ? ? ? ? }
? ? ? ? ? ? System.out.println();
? ? ? ? }
? ? }
}

输出：
? 1
? 1 ?1
? 1 ?2 ?1
? 1 ?3 ?3 ?1
? 1 ?4 ?6 ?4 ?1
? 1 ?5 10 10 ?5 ?1
? 1 ?6 15 20 15 ?6 ?1
? 1 ?7 21 35 35 21 ?7 ?1