題目要求

思路

這道題的歸類是記憶化搜索，我開始看到這題馬上就想打一個DP，解完以后看了看題解，發(fā)現了一種好的思路。

用這種思路，我在排除兩種特例（即$k==0$和$shorter==longer$）之后，定義一個長度為$k+1$的vector，利用式子$nums[i]+=k?shorter+i?differ$，循環(huán)一遍就能達到$O(n)$。

提交代碼

class Solution { public:vector<int> divingBoard(int shorter, int longer, int k) {if (k == 0) {return vector<int> {};}if (shorter == longer) {return vector<int> {shorter*k};}vector<int> nums(k+1);int differ = longer-shorter;for (int i = 0; i <= k; i++) {nums[i] += k*shorter + i*differ;}return nums;} };

完整代碼

#include <iostream> #include <vector>using namespace std;class Solution { public:vector<int> divingBoard(int shorter, int longer, int k) {if (k == 0) {return vector<int> {};}if (shorter == longer) {return vector<int> {shorter*k};}vector<int> nums(k+1);int differ = longer-shorter;for (int i = 0; i <= k; i++) {nums[i] += k*shorter + i*differ;}return nums;} };int main() {Solution solution = Solution();vector<int> nums = solution.divingBoard(1, 2, 3);cout << "[";int i;for (i = 0; i < nums.size()-1; i++) {cout << nums[i] << ",";}cout << nums[i] << "]" << endl;return 0; }

總結

以上是生活随笔為你收集整理的【LeetCode】跳水板的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。