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

爱写bug

发布于 2019-08-01 10:39:18

3880

发布于 2019-08-01 10:39:18

文章被收录于专栏：爱写Bug

爱写bug（ID：icodebugs）

给定一个非负索引 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.

img

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

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<Integer>() ：

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> nums = new ArrayList<Integer>();
        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<Integer> 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<Integer>型并返回
    }
}

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

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-07-07，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自爱写Bug 微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度