先給題
給定一個非負(fù)索引 k，其中 k ≤ 33，返回楊輝三角的第 k 行。
在楊輝三角中，每個數(shù)是它左上方和右上方的數(shù)的和。
示例:
輸入: 3
輸出: [1,3,3,1]
進階：
你可以優(yōu)化你的算法到 O(k) 空間復(fù)雜度嗎？
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/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行
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; }
題解當(dāng)中是開辟的二維數(shù)組，我這里用的是一維數(shù)組。
這里用的是滾動數(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 }
