leetcode算法【119】杨辉三角 II

向右看齐 2022-11-25 11:37 116阅读 0赞

### 文章目录 ###

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

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

#### 题目 ####

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。

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

在杨辉三角中，每个数是它左上方和右上方的数的和。
    
    示例:
    
    输入: 3
    输出: [1,3,3,1]
    进阶：
    
    你可以优化你的算法到 O(k) 空间复杂度吗？

#### 方案1： ####

*  简单题，不过和118不一样，他这是下标，从0开始

class Solution { 
            public List<Integer> getRow(int rowIndex) { 
    
                List<Integer> last = new LinkedList<>( );
                List<Integer> now = new LinkedList<>( );
    
                last.add(1);
                for (int i = 1; i <= rowIndex + 1; i++) { 
                    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));
                        }
                    }
                    last = now;
                }
                return now;
                
            }
        }

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

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

#### 方案2： ####

*  用公式，C几取几那个

class Solution { 
            public List<Integer> getRow(int rowIndex) { 
                List<Integer> now = new LinkedList<>( );
                long tmp = 1;
                int row = rowIndex + 1;
                for (int i = 0; i <= rowIndex; i++) { 
                    if (i == 0 || i == rowIndex) { 
                        now.add(1);
                    } else { 
                        tmp = tmp * (row - i) / i;
                        now.add((int) tmp);
                    }
                }
                return now;
            }
        }

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

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

[Git]: https://github.com/ch98road/leetcode
[20200808134524897.png]: /images/20221124/3a56939d48b147a7b081011ea632d307.png