LeetCode 118：楊輝三角 II Pascal's Triangle II

xiaodao 發布于2019-07-31 11:25 / 2303人閱讀

摘要：公眾號愛寫作者愛寫給定一個非負索引，其中，返回楊輝三角的第行。在楊輝三角中，每個數是它左上方和右上方的數的和。示例輸入輸出進階你可以優化你的算法到空間復雜度嗎解題思路和之前寫的那篇號楊輝三角基本類似。

公眾號：愛寫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

GPU云服務器云服務器 pascal_triangle 實例類型ii II quartus ii

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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