119. Pascal's Triangle II

Myth丶恋晨 2022-06-11 05:25 144阅读 0赞

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,  
Return `[1,3,3,1]`.

Note:  
Could you optimize your algorithm to use only O(k) extra space?

问题描述：给定一个索引k，返回杨辉三角的第k层。层数从0开始，即第0层返回1，第一层返回1 1，第二层返回1 2 1，……以此类推，层数k+1为第k层的数的个数。

注：优化算法，只使用O(k)额外的空间，即算法空间复杂度为O(n)。

分析：用迭代的方法，第k层的值根据上一层(k-1)的值计算，每一层都在同一个List上操作。第k层位置j的值等于(k-1层位置j的值)+(k-1层位置j-1的值)，位置j的值在覆盖位置(j+1)的值时会用到，所以在覆盖位置j的值时先将未覆盖的值保留，程序中用(pre\_num = cur\_num;)实现。

public class Solution {
        public List<Integer> getRow(int rowIndex) {
           List<Integer> list = new ArrayList<Integer>();
            list.add(1);
            if (rowIndex >= 1)
                list.add(1);
    
            for(int i=2;i<=rowIndex;i++){
                if (rowIndex == 0 && rowIndex == 1)
                    return list;
                if(rowIndex >= 2){
                    list.add(1);
                    int pre_num = list.get(0);
                    for (int j = 1;j<list.size()-1;j++) {
                        int cur_num = list.get(j);
                        list.set(j, cur_num + pre_num);
                        pre_num = cur_num;
                    }
                }
            }
            return list;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，144人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode - Easy - 119. Pascal‘s Triangle II

Topic Array Description [https://leetcode.com/problems/pascals-triangle-ii/][h

女爷i/ 2022年12月28日 11:25/ 0 赞/ 114 阅读

相关 LeetCode－118. Pascal's Triangle，119. Pascal's Triangle II

118 Problem: > Given numRows, generate the first numRows of Pascal’s triangle.For exa

浅浅的花香味﹌/ 2022年08月20日 13:28/ 0 赞/ 138 阅读

相关 119. Pascal's Triangle II （杨辉三角第k行）

Given an index k, return the kth row of the Pascal's triangle. For example, given k = 3

男娘i/ 2022年07月15日 01:20/ 0 赞/ 133 阅读

相关 119. Pascal's Triangle II （杨辉三角第k行）

Given an index k, return the kth row of the Pascal's triangle. For example, given k = 3

女爷i/ 2022年07月15日 01:20/ 0 赞/ 108 阅读

相关 119. Pascal's Triangle II

Given an index k, return the kth row of the Pascal's triangle. For example, given k = 3

Myth丶恋晨/ 2022年06月11日 05:25/ 0 赞/ 145 阅读

相关 leetcode 119. Pascal's Triangle II 杨辉三角形2

Given an index k, return the kth row of the Pascal’s triangle. For example, given k = 3

旧城等待，/ 2022年06月08日 04:17/ 0 赞/ 161 阅读

相关 119. Pascal's Triangle II

Given an index k, return the kth row of the Pascal's triangle. For example,

我就是我/ 2022年05月31日 23:14/ 0 赞/ 155 阅读

相关【LeetCode with JavaScript】119. Pascal’s Triangle II

原题网址：[https://leetcode.com/problems/pascals-triangle-ii][https_leetcode.com_problems_pas

Love The Way You Lie/ 2022年05月24日 08:42/ 0 赞/ 149 阅读

相关 LeetCode 119.Pascal's Triangle II (杨辉三角 II)

题目描述：给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。 ![PascalTriangleAnimated2.gif][] 在杨辉三角中，每个数是

淡淡的烟草味﹌/ 2022年05月08日 00:36/ 0 赞/ 161 阅读

相关 leetcode--Pascal's Triangle II

Given an index k, return the kth row of the Pascal's triangle. For example, given k = 3

短命女/ 2021年10月24日 03:46/ 0 赞/ 342 阅读