1、描述

16.11难度简单20你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度。
返回的长度需要从小到大排列。
示例：
输入：
shorter = 1
longer = 2
k = 3
输出： {3,4,5,6}

提示：

0 < shorter <= longer
0 <= k <= 100000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/diving-board-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2、关键字

1、两种类型

3、思路

以为是dp，但是找不到转移方程，又以为是树的遍历，但是有重合，
最后是全覆盖的所有可能性，
有人说看到k的范围是100000，就得知道，时间复杂度只能是O(N),意思就是只能一层循环了。
然后这个题
1、要么为空直接返回
2、要么长短相等直接返回
3、或者长度不等，遍历一遍就好了

4、notes

如果找不到dp思路，找不到dfs思路，找不到解法思路，就想一下全部的可能性。

5、复杂度

时间：O(k) 一层循环
空间：O(1) tem

6、code

class Solution {
public:vector<int> divingBoard(int shorter, int longer, int k) {vector<int> v;if(k==0) return v; // 空直接返回if(shorter==longer) {  // 相等直接给出答案v.push_back(k*shorter);}else{  // 从最短，到最长遍历一遍，就好了，一次少一个短的，变成一个长的v.push_back(shorter*k);int tem=longer-shorter;  // 差值for(int i=1;i<=k;i++){  // 长的还是有1块到k块v.push_back(v.back()+tem);   }}return v;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！