資訊專欄INFORMATION COLUMN
摘要：迭代法復(fù)雜度時(shí)間空間思路簡單的按照楊輝三角形的規(guī)則計(jì)算就行了。代碼加入第一個(gè)加入中間的數(shù)加入最后一個(gè)逆序相加法復(fù)雜度時(shí)間空間思路同樣用迭代的方法，根據(jù)上一層的值算下一層，不過這里每一層都在同一個(gè)上操作。
Pascal"s Triangle I
迭代法 復(fù)雜度Given numRows, generate the first numRows of Pascal"s triangle.
For example, given numRows = 5, Return
[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]
時(shí)間 O(N) 空間 O(k^2)
思路簡單的按照楊輝三角形的規(guī)則計(jì)算就行了。
代碼public class Solution {
public List> generate(int numRows) {
List> res = new ArrayList>();
if(numRows <= 0) return res;
List one = new ArrayList();
one.add(1);
res.add(one);
for(int i = 1; i < numRows; i++){
List line = new ArrayList();
// 加入第一個(gè)1
line.add(1);
// 加入中間的數(shù)
for(int j = 1; j < i; j++){
line.add(res.get(i-1).get(j-1) + res.get(i-1).get(j));
}
// 加入最后一個(gè)1
line.add(1);
res.add(line);
}
return res;
}
}
Pascal"s Triangle II
逆序相加法 復(fù)雜度Given an index k, return the kth row of the Pascal"s triangle.
For example, given k = 3, Return [1,3,3,1].
Note: Could you optimize your algorithm to use only O(k) extra space?
時(shí)間 O(N) 空間 O(k)
思路同樣用迭代的方法，根據(jù)上一層的值算下一層，不過這里每一層都在同一個(gè)List上操作。如果我們從后向前計(jì)算，而且每次計(jì)算都用到上一個(gè)位置的數(shù)的話，我們會重復(fù)計(jì)算好幾次，導(dǎo)致結(jié)果錯(cuò)誤。這里的技巧在于從后向前計(jì)算，并且每次計(jì)算用當(dāng)前位置的值和上一位置的值，來更新當(dāng)前位置的值。最后再在后面加個(gè)1，就是這一層的結(jié)果了。
代碼public class Solution {
public List getRow(int k) {
List line = new ArrayList();
// 加入第一個(gè)1
line.add(1);
if(k <= 0) return line;
for(int i = 1; i <= k; i++){
// 計(jì)算j+1位置的值，是根據(jù)j位置的值和j+1位置的值得到的，相當(dāng)于往后位移一位
for(int j = line.size() - 2; j >= 0; j--){
line.set(j + 1, line.get(j) + line.get(j + 1));
}
// 加上最后一個(gè)1
line.add(1);
}
return line;
}
}
公式法
復(fù)雜度
時(shí)間 O(K) 空間 O(1)
思路更“暴力”的方法，是直接使用公式，對于第k(k>=1)層下標(biāo)為i(i>=0)的位置，數(shù)字應(yīng)該為num[i-1] * (k - i) / i，由于這個(gè)乘法可能溢出，我們用一個(gè)long型臨時(shí)變量將其存起來。
注意rowIndex是0開始的，公式中k是1開始的
代碼public class Solution {
public List getRow(int rowIndex) {
// rowIndex是0開始的，我們將它加1，得到k
int k = rowIndex + 1;
ArrayList line = new ArrayList();
line.add(1);
long tmp = 1;
for(int i = 1; i < k; i++){
// 使用公式 上一個(gè)數(shù)乘以(k-i)再除以i
tmp = tmp * (k - i) / i;
line.add((int)tmp);
}
return line;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64596.html
摘要：首先要對特殊情況進(jìn)行處理小于等于的情況。然后循環(huán)，每一次產(chǎn)生一個(gè)，個(gè)有個(gè)元素，每個(gè)的第一個(gè)和第個(gè)元素都是對于中間的那些元素，則找出前一個(gè)的對應(yīng)位置的兩個(gè)元素加和即可得到。這一道題只要求返回形式的一行的元素即可。 118 Pascals Triangle 題目詳情 Given numRows, generate the first numRows of Pascals triangle....
摘要：楊輝三角給定一個(gè)非負(fù)整數(shù)，生成楊輝三角的前行。在楊輝三角中，每個(gè)數(shù)是它左上方和右上方的數(shù)的和。另外可以在內(nèi)層循環(huán)加判斷在不等于時(shí)才加上，這樣可省略代碼段，但是這個(gè)會在每次進(jìn)入第一次循環(huán)后判斷一次。本著減少資源消耗的原則，應(yīng)當(dāng)提到外面。 118:Pascals Triangle 楊輝三角 Given a non-negative integer numRows, generate the...
摘要：楊輝三角給定一個(gè)非負(fù)整數(shù)，生成楊輝三角的前行。在楊輝三角中，每個(gè)數(shù)是它左上方和右上方的數(shù)的和。另外可以在內(nèi)層循環(huán)加判斷在不等于時(shí)才加上，這樣可省略代碼段，但是這個(gè)會在每次進(jìn)入第一次循環(huán)后判斷一次。本著減少資源消耗的原則，應(yīng)當(dāng)提到外面。 118:Pascals Triangle 楊輝三角 Given a non-negative integer numRows, generate the...
摘要：公眾號愛寫作者愛寫給定一個(gè)非負(fù)索引，其中，返回楊輝三角的第行。在楊輝三角中，每個(gè)數(shù)是它左上方和右上方的數(shù)的和。示例輸入輸出進(jìn)階你可以優(yōu)化你的算法到空間復(fù)雜度嗎解題思路和之前寫的那篇號楊輝三角基本類似。 公眾號：愛寫bug（ID：icodebugs）作者：愛寫bug 給定一個(gè)非負(fù)索引 k，其中 k ≤ 33，返回楊輝三角的第 k 行。 Given a non-negative index...
摘要：公眾號愛寫作者愛寫給定一個(gè)非負(fù)索引，其中，返回楊輝三角的第行。在楊輝三角中，每個(gè)數(shù)是它左上方和右上方的數(shù)的和。示例輸入輸出進(jìn)階你可以優(yōu)化你的算法到空間復(fù)雜度嗎解題思路和之前寫的那篇號楊輝三角基本類似。 公眾號：愛寫bug（ID：icodebugs）作者：愛寫bug 給定一個(gè)非負(fù)索引 k，其中 k ≤ 33，返回楊輝三角的第 k 行。 Given a non-negative index...
閱讀 1917·2021-11-24 11:16
閱讀 3265·2021-09-10 10:51
閱讀 3217·2021-08-03 14:03
閱讀 1272·2019-08-29 17:03
閱讀 3253·2019-08-29 12:36
閱讀 2239·2019-08-26 14:06
閱讀 502·2019-08-23 16:32
閱讀 2695·2019-08-23 13:42
