题目要求

思路

这道题的归类是记忆化搜索，我开始看到这题马上就想打一个DP，解完以后看了看题解，发现了一种好的思路。

用这种思路，我在排除两种特例（即$k==0$和$shorter==longer$）之后，定义一个长度为$k+1$的vector，利用式子$nums[i]+=k\ast shorter+i\ast differ$，循环一遍就能达到$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】跳水板的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。