楊輝三角Ⅱ

丹楓無跡 2022-08-13 發(fā)布于北京

展開全文

先給題
給定一個非負索引 k，其中 k ≤ 33，返回楊輝三角的第 k 行。

在楊輝三角中，每個數(shù)是它左上方和右上方的數(shù)的和。

示例:

輸入: 3
輸出: [1,3,3,1]
進階：

你可以優(yōu)化你的算法到 O(k) 空間復(fù)雜度嗎？

來源：力扣（LeetCode）
鏈接：https:///problems/pascals-triangle-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

這道題多的就不說了就是要找規(guī)律
只有1個1的是第0行

1.O(k！) 空間復(fù)雜度

    vector<int> getRow(int rowIndex) {
        vector<int> v;
        vector<int> v1;
        v.push_back(1);//第0行
        int sum = 1;
        for(int i = 1; i < rowIndex; i++) {
            v.push_back(1);//每行的第一個元素為1
            for(int j = sum + 1; j < sum + i; j++) {
                v.push_back(v[j - i - 1] + v[j - i]);
            }
            v.push_back(1);
            sum += i + 1;
        }
        v1.push_back(1);
        for(int i = sum + 1; i <sum + rowIndex; i++) {
            v1.push_back(v[i - rowIndex - 1] + v[i - rowIndex]);
        }
        if(rowIndex != 0)
            v1.push_back(1);
        return v1;
    }

View Code

題解當(dāng)中是開辟的二維數(shù)組，我這里用的是一維數(shù)組。

2.O(k) 空間復(fù)雜度

這里用的是滾動數(shù)組的思想，開辟兩個數(shù)組，靈活的讓他們改變

 1     vector<int> getRow(int rowIndex) {
 2         vector<int> bef,aft;
 3         for (int i = 0; i <= rowIndex; ++i) {
 4             bef.resize(i + 1);
 5             bef[0] = bef[i] = 1;
 6             for (int j = 1; j < i; ++j) {
 7                 bef[j] = aft[j - 1] + aft[j];
 8             }
 9             aft = bef;
10         }
11         return aft;
12     }