資訊專欄INFORMATION COLUMN
摘要：公眾號愛寫作者愛寫給定一個非負(fù)索引，其中，返回楊輝三角的第行。在楊輝三角中，每個數(shù)是它左上方和右上方的數(shù)的和。示例輸入輸出進(jìn)階你可以優(yōu)化你的算法到空間復(fù)雜度嗎解題思路和之前寫的那篇號楊輝三角基本類似。
公眾號：愛寫bug（ID：icodebugs）
作者：愛寫bug
給定一個非負(fù)索引 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.
在楊輝三角中，每個數(shù)是它左上方和右上方的數(shù)的和。
In Pascal"s triangle, each number is the sum of the two numbers directly above it.
示例:
輸入: 3 輸出: [1,3,3,1]
進(jìn)階：
你可以優(yōu)化你的算法到 O(k) 空間復(fù)雜度嗎？
解題思路：和之前寫的那篇118號楊輝三角基本類似。這道題只是不用考慮每行輸出，只輸出最后一行。這樣只在一個數(shù)組上修改即可：該數(shù) 的值 = 該數(shù)的值+該數(shù)左邊的值之和（該數(shù)不包括第一個和最后一個數(shù)）。
這道題只是不用考慮每一行輸出，只輸出最后一行。這樣只在一個數(shù)組上修改即可：該數(shù) 的值 = 該數(shù)的值+該數(shù)左邊的值之和（該數(shù)不包括第一個和最后一個數(shù)）。
用兩個嵌套循環(huán)，外循環(huán)是要計算的每行數(shù)組，內(nèi)循環(huán)在上一次計算的數(shù)組基礎(chǔ)上更改數(shù)值得出該行數(shù)組。
需要注意的是：內(nèi)循環(huán) j 指針應(yīng)該從每行的最后一個數(shù)開始更改。
如果 j 指針從左開始更改索引的值：
[1][1,1]
[1,2,1] 索引1 的值是索引 0 和 1的和，沒問題
[1,3,4,1] 索引2 的值是索引 2 和索引 1的和 為4，而不是預(yù)期的3
因為我們是在同一個數(shù)組里更改每個數(shù)值的，所以如果做左邊開始求值，索引 1 的值會從2變?yōu)?，此時計算索引2的值，由于該索引左邊的值已經(jīng)改變?yōu)?，該索引將不再是預(yù)期值。
起先我用的是 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;
}
}
提交時雖然能通過但是每次調(diào)用 set()、add() 導(dǎo)致性能很差很差。
Java：class Solution {
public List getRow(int rowIndex) {
Integer[] nums = new Integer[rowIndex+1];//所有值被默認(rèn)置為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];//當(dāng)j為1時，nums[j]為0，不影響最后一個值，不用多帶帶給每行末尾賦值1
}
}
return Arrays.asList(nums);//轉(zhuǎn)為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
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/45095.html
摘要：公眾號愛寫作者愛寫給定一個非負(fù)索引，其中，返回楊輝三角的第行。在楊輝三角中，每個數(shù)是它左上方和右上方的數(shù)的和。示例輸入輸出進(jìn)階你可以優(yōu)化你的算法到空間復(fù)雜度嗎解題思路和之前寫的那篇號楊輝三角基本類似。 公眾號：愛寫bug（ID：icodebugs）作者：愛寫bug 給定一個非負(fù)索引 k，其中 k ≤ 33，返回楊輝三角的第 k 行。 Given a non-negative index...
摘要：楊輝三角給定一個非負(fù)整數(shù)，生成楊輝三角的前行。在楊輝三角中，每個數(shù)是它左上方和右上方的數(shù)的和。另外可以在內(nèi)層循環(huán)加判斷在不等于時才加上，這樣可省略代碼段，但是這個會在每次進(jìn)入第一次循環(huán)后判斷一次。本著減少資源消耗的原則，應(yīng)當(dāng)提到外面。 118:Pascals Triangle 楊輝三角 Given a non-negative integer numRows, generate the...
摘要：楊輝三角給定一個非負(fù)整數(shù)，生成楊輝三角的前行。在楊輝三角中，每個數(shù)是它左上方和右上方的數(shù)的和。另外可以在內(nèi)層循環(huán)加判斷在不等于時才加上，這樣可省略代碼段，但是這個會在每次進(jìn)入第一次循環(huán)后判斷一次。本著減少資源消耗的原則，應(yīng)當(dāng)提到外面。 118:Pascals Triangle 楊輝三角 Given a non-negative integer numRows, generate the...
摘要：首先要對特殊情況進(jìn)行處理小于等于的情況。然后循環(huán)，每一次產(chǎn)生一個，個有個元素，每個的第一個和第個元素都是對于中間的那些元素，則找出前一個的對應(yīng)位置的兩個元素加和即可得到。這一道題只要求返回形式的一行的元素即可。 118 Pascals Triangle 題目詳情 Given numRows, generate the first numRows of Pascals triangle....
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...
閱讀 3127·2021-08-03 14:05
閱讀 2169·2019-08-29 15:35
閱讀 704·2019-08-29 13:30
閱讀 3195·2019-08-29 13:20
閱讀 2561·2019-08-23 18:15
閱讀 1829·2019-08-23 14:57
閱讀 2244·2019-08-23 13:57
閱讀 1347·2019-08-23 12:10
