|
先給題
示例: 輸入: 3 你可以優(yōu)化你的算法到 O(k) 空間復(fù)雜度嗎？ 來源：力扣（LeetCode） 這道題多的就不說了就是要找規(guī)律 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);//每行的第一個(gè)元素為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; }
2.O(k) 空間復(fù)雜度這里用的是滾動(dòng)數(shù)組的思想，開辟兩個(gè)數(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 }
|
|
|
