先给题
示例: 输入: 3 你可以优化你的算法到 O(k) 空间复杂度吗? 来源:力扣(LeetCode) 这道题多的就不说了就是要找规律 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; }
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 }
|
|