先給題
給定一個非負索引 k，其中 k ≤ 33，回傳楊輝三角的第 k 行，
在楊輝三角中，每個數是它左上方和右上方的數的和，
示例:
輸入: 3
輸出: [1,3,3,1]
進階：
你可以優化你的演算法到 O(k) 空間復雜度嗎？
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/pascals-triangle-ii
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
這道題多的就不說了就是要找規律
只有1個1的是第0行
1.O(k！) 空間復雜度
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
題解當中是開辟的二維陣列，我這里用的是一維陣列，
2.O(k) 空間復雜度
這里用的是滾動陣列的思想，開辟兩個陣列，靈活的讓他們改變
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 }View Code
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259106.html
標籤：其他
上一篇：字串的排列（雙指標）