LeetCode--杨辉三角

爱被打了一巴掌 2022-03-06 16:20 279阅读 0赞

题干：

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

![aHR0cHM6Ly91cGxvYWQud2lraW1lZGlhLm9yZy93aWtpcGVkaWEvY29tbW9ucy8wLzBkL1Bhc2NhbFRyaWFuZ2xlQW5pbWF0ZWQyLmdpZg][]

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

**示例:**

输入: 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` 中更新的每个数字， 所以空间需求与时间复杂度相同。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZvbGxvd18yNA_size_16_color_FFFFFF_t_70][] 同名原创公众号： **程序大视界**

[aHR0cHM6Ly91cGxvYWQud2lraW1lZGlhLm9yZy93aWtpcGVkaWEvY29tbW9ucy8wLzBkL1Bhc2NhbFRyaWFuZ2xlQW5pbWF0ZWQyLmdpZg]: /images/20220302/f5af5670b77c4cf9a9cee3b13538f15d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ZvbGxvd18yNA_size_16_color_FFFFFF_t_70]: /images/20220302/fbe8114f99814b62a986a6c04c808bef.png