LeetCode中杨辉三角题解

LeetCode中杨辉三角题解-java

题目

118. 杨辉三角

难度简单392

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

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

示例:

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

题解

/**

* 帕斯卡三角形

* 1

* 1 1

* 1 2 1

* 1 3 3 1

* 1 4 6 4 1

* 1 5 10 10 5 1

* @param numRows

* @return

*/

方法一：用ArrayList数组存放杨辉三角

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
           从第0行开始构造杨辉三角形   
        for(int i = 0; i < numRows; i++){
               arraylist用来存放杨辉三角此行的数值    
            ArrayList<Integer> arr = new ArrayList<Integer>();
               第i行的长度为i+1    
            for(int j = 0; j <= i; j++){
                   在每行的第0个与最后一个值都为1    
                if(j == 0 || j == i){
                    arr.add(1);
                    中间值为上一行的j-1下标对应值+j下边对应值的和
                }else{
                    arr.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));
                }
            }
               将此行添加到res 中 
            res.add(arr);
        }
        return res;
    }
}

提交详情

复杂度分析

​ 时间复杂度： O(numRows^2)

​ 空间复杂度：

方法二：用二维数组存放杨辉三角

class Solution {
        public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> list = new ArrayList<>();
        // 一个长度均为numRows的二维数组来存放杨辉三角的值
        int[][] arr = new int[numRows][numRows];
        // 从第0行开始构造杨辉三角形  
        for (int i = 0; i < numRows; i++) {
            // 用sublist存放此行杨辉三角的值
            List<Integer> subList = new ArrayList<>();
             // 第i行的长度为i+1    
            for (int j = 0; j <=i ; j++) {
                // 在每行的第0个与最后一个值都为1  
                if(j==0 || j==i){
                    arr[i][j] = 1;
                // 中间值为上一行的j-1下标对应值+j下边对应值的和
                }else{
                    arr[i][j] = arr[i-1][j-1]+arr[i-1][j];
                }
                // 将二维数组中的值添加到sublist中 
                subList.add(arr[i][j]);
            }
            // 将sublist添加到list中
            list.add(subList);
        }
        return list;
    }
}

提交详情

复杂度分析

​ 时间复杂度： O(numRows^2)

​ 空间复杂度：