LeetCode--杨辉三角

原创
2019/03/21 10:29
阅读数 47

题干:

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

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

示例:

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

 

解答一(思路):

1、定义一个List<List<Integer>>用来返回结果list,list用来存储杨辉三角每行的结果集。

2、list中元素的个数代表行数,每行的某个元素等于上一行的左上位+右上位之和。

优点:算法简洁明了,运用递归算法计算每个元素的值。

缺点:占用空间大,static方法返回,需要耗损较大空间,时间复杂度较大。

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> dataList = new ArrayList<List<Integer>>();
        if(numRows == 0){
            return dataList;
        }
        for(int i=1;i<=numRows;i++){
            List<Integer> list = new ArrayList<Integer>();
            for(int j=1;j<=i;j++){
                list.add(num(i,j));
            }
            dataList.add(list);
        }
        return dataList;
    }
    public static int num(int x,int y){
        if(y==1||y==x){
             return 1;
        }
        int c=num(x-1,y-1)+num(x-1,y);
        return c;
    }
}

解答二(LeetCode官方):

方法:动态规划

思路

如果能够知道一行杨辉三角,我们就可以根据每对相邻的值轻松地计算出它的下一行。

算法

虽然这一算法非常简单,但用于构造杨辉三角的迭代方法可以归类为动态规划,因为我们需要基于前一行来构造每一行。

首先,我们会生成整个 triangle 列表,三角形的每一行都以子列表的形式存储。然后,我们会检查行数为 00 的特殊情况,否则我们会返回 [1][1]。如果 numRows > 0numRows>0,那么我们用 [1][1] 作为第一行来初始化 triangle with [1][1],并按如下方式继续填充

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<List<Integer>>();

        // First base case; if user requests zero rows, they get zero rows.
        if (numRows == 0) {
            return triangle;
        }

        // Second base case; first row is always [1].
        triangle.add(new ArrayList<>());
        triangle.get(0).add(1);

        for (int rowNum = 1; rowNum < numRows; rowNum++) {
            List<Integer> row = new ArrayList<>();
            List<Integer> prevRow = triangle.get(rowNum-1);

            // The first row element is always 1.
            row.add(1);

            // Each triangle element (other than the first and last of each row)
            // is equal to the sum of the elements above-and-to-the-left and
            // above-and-to-the-right.
            for (int j = 1; j < rowNum; j++) {
                row.add(prevRow.get(j-1) + prevRow.get(j));
            }

            // The last row element is always 1.
            row.add(1);

            triangle.add(row);
        }

        return triangle;
    }
}

复杂度分析

  • 时间复杂度:O(numRows^2)O(numRows2)

    虽然更新 triangle 中的每个值都是在常量时间内发生的, 但它会被执行 O(numRows^2)O(numRows2) 次。想要了解原因,就需要考虑总共有多少 次循环迭代。很明显外层循环需要运行 numRowsnumRows 次,但在外层循环的每次迭代中,内层 循环要运行 rowNumrowNum 次。因此,triangle 发生的更新总数为 1 + 2 + 3 + \ldots + numRows1+2+3+…+numRows,根据高斯公式 有

    \begin{aligned} \frac{numRows(numRows+1)}{2} &= \frac{numRows^2 + numRows}{2} \\ &= \frac{numRows^2}{2} + \frac{numRows}{2} \\ &= O(numRows^2) \end{aligned}2numRows(numRows+1)​​=2numRows2+numRows​=2numRows2​+2numRows​=O(numRows2)​

  • 空间复杂度:O(numRows^2)O(numRows2)

    因为我们需要存储我们在 triangle 中更新的每个数字, 所以空间需求与时间复杂度相同。

 

 

同名原创公众号: 程序大视界

 

本文同步分享在 博客“程序大视界”(CSDN)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部