LeetCode-118杨辉三角-II-Pascals-Triangle-II

公众号：爱写 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<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