链接
https://leetcode-cn.com/problems/diving-board-lcci/
耗时
解题：12 min
题解：20 min
题意
你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度。
返回的长度需要从小到大排列。
0 < shorter <= longer
0 <= k <= 100000
思路
shorter 和 longer 的木板分别从 0 到 k 对应各选一次即可，每次长度为
i
∗
l
o
n
g
e
r
+
(
k
−
i
)
∗
s
h
o
r
t
e
r
i*longer+(k-i)*shorter
i∗longer+(k−i)∗shorter。
上述长度序列是递增的，没有相同项，最后也无需排序。证明如下：
设：
a
i
=
i
∗
l
o
n
g
e
r
+
(
k
−
i
)
∗
s
h
o
r
t
e
r
a_i = i*longer+(k-i)*shorter
ai=i∗longer+(k−i)∗shorter
合并同类项：
a
i
=
i
∗
(
l
o
n
g
e
r
−
s
h
o
r
t
e
r
)
+
k
∗
s
h
o
r
t
e
r
a_i = i*(longer-shorter)+k*shorter
ai=i∗(longer−shorter)+k∗shorter，
i
i
i 唯一，故没有相同的项。
那么
a
i
+
1
=
(
i
+
1
)
∗
(
l
o
n
g
e
r
−
s
h
o
r
t
e
r
)
+
k
∗
s
h
o
r
t
e
r
a_{i+1} = (i+1)*(longer-shorter)+k*shorter
ai+1=(i+1)∗(longer−shorter)+k∗shorter，
a
i
+
1
−
a
i
=
(
l
o
n
g
e
r
−
s
h
o
r
t
e
r
)
>
0
a_{i+1}-a_i = (longer-shorter) > 0
ai+1−ai=(longer−shorter)>0，所以
a
i
a_i
ai 递增。
注意：当
k
=
0
k=0
k=0 时，会产生错误，特判
k
=
=
0
k==0
k==0 返回空。shorter 可以等于 longer，当它们相等时，会产生错误，也需特判返回{k*shorter}。
AC代码
class Solution {
public:
vector<int> divingBoard(int shorter, int longer, int k) {
if(k == 0) return {};
if(shorter == longer) return {k*shorter};
vector<int> ans;
for(int i = 0; i <= k; ++i) {
ans.push_back(i*longer+(k-i)*shorter);
}
return ans;
}
};
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
