leetcode算法【118】杨辉三角

刺骨的言语ヽ痛彻心扉 2022-11-25 11:36 115阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

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

![在这里插入图片描述][20200808133812929.png]

在杨辉三角中，每个数是它左上方和右上方的数的和。
    示例:
    
    输入: 5
    输出:
    [
         [1],
        [1,1],
       [1,2,1],
      [1,3,3,1],
     [1,4,6,4,1]
    ]

#### 方案： ####

*  简单题

class Solution { 
            public List<List<Integer>> generate(int numRows) { 
    
                // =上一行的 n-1项+n项
    
                if (numRows == 0) return new LinkedList<>( );
                else { 
                    LinkedList<List<Integer>> res = new LinkedList<>( );
                    List<Integer> last = new LinkedList<>( );
                    last.add(1);
                    for (int i = 1; i <= numRows; i++) { 
                        List<Integer> now = new LinkedList<>( );
                        for (int j = 0; j < i; j++) { 
                            if (j==0||j==i-1){ 
                                now.add(1);
                            }else
                            { 
                                now.add(last.get(j-1)+last.get(j));
                            }
                        }
                        res.add(now);
                        last = now;
                    }
                    return res;
                }
            }
        }

##### 复杂度计算 #####

*  时间复杂度：O(n!)
 *  空间复杂度：O(n!)

[Git]: https://github.com/ch98road/leetcode
[20200808133812929.png]: /images/20221124/5c2938f24b0b479aad37cf5400f9b8e3.png