LeetCode 118：杨辉三角 II Pascal's Triangle II

xiaodao 发布于2019-07-31 11:25 / 2241人阅读

摘要：公众号爱写作者爱写给定一个非负索引，其中，返回杨辉三角的第行。在杨辉三角中，每个数是它左上方和右上方的数的和。示例输入输出进阶你可以优化你的算法到空间复杂度吗解题思路和之前写的那篇号杨辉三角基本类似。

公众号：爱写bug（ID：icodebugs）
作者：爱写bug

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

Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal"s triangle.

Note that the row index starts from 0.

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

In Pascal"s triangle, each number is the sum of the two numbers directly above it.

示例:

输入: 3
输出: [1,3,3,1]

进阶：

你可以优化你的算法到 O(k) 空间复杂度吗？

解题思路：

和之前写的那篇118号杨辉三角基本类似。这道题只是不用考虑每行输出，只输出最后一行。这样只在一个数组上修改即可：该数的值 = 该数的值+该数左边的值之和（该数不包括第一个和最后一个数）。

这道题只是不用考虑每一行输出，只输出最后一行。这样只在一个数组上修改即可：该数的值 = 该数的值+该数左边的值之和（该数不包括第一个和最后一个数）。

用两个嵌套循环，外循环是要计算的每行数组，内循环在上一次计算的数组基础上更改数值得出该行数组。

需要注意的是：内循环 j 指针应该从每行的最后一个数开始更改。

如果 j 指针从左开始更改索引的值：

[1][1,1]
[1,2,1]    索引1 的值是索引 0 和 1的和，没问题
[1,3,4,1]    索引2 的值是索引 2 和索引 1的和 为4，而不是预期的3

因为我们是在同一个数组里更改每个数值的，所以如果做左边开始求值，索引 1 的值会从2变为3，此时计算索引2的值，由于该索引左边的值已经改变为3，该索引将不再是预期值。

起先我用的是 ArrayList() ：

class Solution {
    public List getRow(int rowIndex) {
        List nums = new ArrayList();
        nums.add(1);
        for (int i = 1; i <= rowIndex; i++) {
            for (int j = i - 1; j > 0; j--) {
                nums.set(j, nums.get(j) + nums.get(j - 1));
            }
            nums.add(1);
            System.out.println(nums);
        }
        return nums;
    }
}

提交时虽然能通过但是每次调用 set()、add() 导致性能很差很差。

Java：

class Solution {
    public List getRow(int rowIndex) {
        Integer[] nums = new Integer[rowIndex+1];//所有值被默认置为0
        Arrays.fill(nums, 0);
        nums[0] = 1;
        for (int i = 1; i <= rowIndex; i++) {
            for (int j = i; j >0; j--) {
                nums[j] = nums[j] + nums[j-1];//当j为1时，nums[j]为0，不影响最后一个值，不用多带带给每行末尾赋值1
            }
        }
        return Arrays.asList(nums);//转为List型并返回
    }
}

Python3：

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        nums = [1] 
        for i in range(1, rowIndex+1):
            for j in range(i-1, 0, -1):
                nums[j] +=nums[j-1]
            nums.append(1) # 需要给末尾索引赋值1
        return nums

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/45095.html

LeetCode 118：杨辉三角 II Pascal&#039;s Triangle II

摘要：公众号爱写作者爱写给定一个非负索引，其中，返回杨辉三角的第行。在杨辉三角中，每个数是它左上方和右上方的数的和。示例输入输出进阶你可以优化你的算法到空间复杂度吗解题思路和之前写的那篇号杨辉三角基本类似。公众号：爱写bug（ID：icodebugs）作者：爱写bug 给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。 Given a non-negative index...

KaltZK 2019-08-16 18:29 评论0 收藏0
leetcode # 118:Pascal&#039;s Triangle 杨辉三角

摘要：杨辉三角给定一个非负整数，生成杨辉三角的前行。在杨辉三角中，每个数是它左上方和右上方的数的和。另外可以在内层循环加判断在不等于时才加上，这样可省略代码段，但是这个会在每次进入第一次循环后判断一次。本着减少资源消耗的原则，应当提到外面。 118:Pascals Triangle 杨辉三角 Given a non-negative integer numRows, generate the...

CKJOKER 2019-07-31 10:37 评论0 收藏0
leetcode # 118:Pascal&#039;s Triangle 杨辉三角

摘要：杨辉三角给定一个非负整数，生成杨辉三角的前行。在杨辉三角中，每个数是它左上方和右上方的数的和。另外可以在内层循环加判断在不等于时才加上，这样可省略代码段，但是这个会在每次进入第一次循环后判断一次。本着减少资源消耗的原则，应当提到外面。 118:Pascals Triangle 杨辉三角 Given a non-negative integer numRows, generate the...

gggggggbong 2019-08-16 18:23 评论0 收藏0
Leetcode 118&119 Pascal&#039;s Triangle

摘要：首先要对特殊情况进行处理小于等于的情况。然后循环，每一次产生一个，个有个元素，每个的第一个和第个元素都是对于中间的那些元素，则找出前一个的对应位置的两个元素加和即可得到。这一道题只要求返回形式的一行的元素即可。 118 Pascals Triangle 题目详情 Given numRows, generate the first numRows of Pascals triangle....

laznrbfe 2019-08-15 13:40 评论0 收藏0
[LeetCode] 119. Pascal&#039;s Triangle II

Problem In Pascals triangle, each number is the sum of the two numbers directly above it. Example: Input: 3Output: [1,3,3,1]Follow up: Could you optimize your algorithm to use only O(k) extra space? S...

CompileYouth 2019-08-16 13:44 评论0 收藏0