字节跳动面试算法题一堆火柴棒长度的序列，切分成不下降的火柴棒长

作者: 稻云麦花 | 来源:发表于2020-04-13 11:50 被阅读0次

[TOC]

同学问我一个字节跳动的面试的算法问题

昨晚我的一个同学问了我下面这个问题，说是字节跳动面试的题目：

一根火柴能拆成两份，然后放在原处。
拆了的还可以再拆
最后保证非下降
问最少要拆几次
比如 3 5 13 9 12 变成 3 5 6 7 9 12。1次就好了

我的第一感觉是这个或许应该可以线性复杂度解决，很有可能是有贪心策略的。
首先想到的是，应该从后面开始扫起，因为前面的火柴棒显然不能超过后面的火柴棒的长度。

然后我发现来可能需要解决一个问题，如果前面的火柴棒比后面的长，那么怎么切分它合适？

一个自然的想法是要让最短的小棒尽可能长，这样对于前面的小棒而言上限就更大一些。显然长度上限越大越好（至少上限大的不会比上限小的差）。

但是，我发现需要考虑一个问题，虽然这样有利于前面的小棒切分数尽可能少，但是对当前的方案来讲，是否存在一种划分方案，它切分的出来的最短小棒虽然更短一些，但是对于前面的小棒的限制效果是一样的（比如最短长棒尽可能长可以达到10 ，而另一种切分方案最短小棒是8，而前面的小棒长度是7，那么10和8对于7的限制效果是一样的），但是切分出来的小棒数目更少。

稍微一想，直觉上可以看出不存在这种情况。因为如果最短小棒更短的切割方案，直觉上就是切分的比较零碎，那么切分成的小棒数就不应该更少。当然，这个直觉上是对的结论没有那么显然。所以，我后面的分析去证明了这个结论，即尽可能切的数目小的情况下，最短小棒越长，切分出来的小棒数越少。

所以问题就变成了，知道小棒原始长度和小棒长度上限，让切分成的最短小棒长度尽可能长，最短小棒可以是多长，以及最少要切几次。

于是就有了下面的子问题A和子问题B.

$n=\sum_{i}^{k}{a_i} \quad (a_i \in N^{+})$
则称 $a_1,a_2,\dots,a_k$ 为 $n$ 的一种整数划分。

子问题A(a,b)

输入 $a,b(b>a)$ 。问在 $b$ 的所有划分中，要求划分中的最大数不超过 $a$ ，最小数最大可以是多少。

即求满足下式最大的 $c$ .
$b=\sum_{i}^{k}{b_i} \quad \& \quad \max_{i}^{k}\{b_i\} \le a \quad \& \quad \min_{i}^{k}\{b_i\}=c$

$b=ka \; \Rightarrow c=a.$
1. 1. 显然 $c=a-1.$
  2. 先划分成k根a和一根r的小棒，之后，我们只需要将 $a-1-r \le a-2 \le k$ 根a长度的小棒每根截取 $1$ 加到 $r$ 这个小棒即可构造出最小长度为 $c=a-1$ 的划分方案。
  3. 即 $a \nmid b \wedge b\ge (a-1)^2 \Rightarrow c=a-1.$
2. 令,则. 下为证明.
  1. .
    1. 所以拆分的小棒不可能少于 $k$ 根.
  2. 假设划分成根小棒，最短的小棒.
    1. 则 $b \ge pc_1 \ge (k+1)(c_0+1)$ .
    2. 又 $b=c_0 \cdot (k+1)+r_0 (0 \le r_0 < k+1) \rightarrow b < c_0 \cdot (k+1)+ (k+1)=(c_0+1)(k+1)$ .
    3. 显然矛盾。故不存在最小长度大于 $c_0$ 的方案。
  3. 考虑划分成根小棒.
    1. 注意有 $b=c_0 \cdot (k+1)+r_0 (0 \le r_0 < k+1)$ .
    2. 先 $k+1$ 根 $c_0$ 的小棒，然后剩余的 $r_0$ 给 $r_0$ 根小棒各自加1即可。
    3. 所以存在一种划分方案最短长度为 $c_0$ .

结论

返回 $c$ .

子问题B(a,b,n)

假设拆分可以使用的数限于 $[a,b]$ 之间的正整数，问 $n$ 可否实现整数划分，以及划分的根数最小可以是多少?

讨论可以拆分的数 $n$ 的情况:
$\left[a,b \right] \\ \left[2a,2b \right] \\ \left[3a,3b \right] \\ \dots \\$

$kb \ge (k+1)a \quad(k \in N^{+}) \;\Rightarrow\; k \ge \lceil \frac{a}{b-a} \rceil = (b-1)\; div \; (b-a)$

也就是说 $k=(b-1)\; div \; (b-a)$ ,可由限于 $[a,b]$ 之间的正整数拆分表示的数落在以下有限个区间内：
$\left[a,b \right] \\ \left[2a,2b \right] \\ \left[3a,3b \right] \\ \dots \\ \left[(k-1)a,(k-1)b \right] \\ \left[ka,+\infty \right] \\$

另外，显然，假设长度 $n$ 可以由上述规则进行整数拆分表示，则，如果 $n<=mb$ ,则 $n$ 一定可以划分成的小棒数一定不超过成 $m$ 根。如果 $(m-1)b<n<=mb$ 则不但可以划分成m根小棒，而且至少需要m根小棒才可以划分。换句话说可能存在多余m根小棒的划分方案，但是一定不存在小于m根的方案，并且一定存在一种方案可以划分成m根。

结论

若 $n$ 可划分，划分的最小根数d满足 $(d-1)\cdot b < n \le d \cdot b$ ,即 $d=\lceil \frac{n}{b} \rceil = (n+b-1) \; div \; b$ .

返回是否可以划分及 $d$ .

回到原问题

输入数组 $a[1..n]$ .

算法

r=a[n] # 长度上限
count = 0
for i = n downto 1
    if a[i] <= r
        r = a[i] # 更新长度上限
        continue
    l = A(r) # 长度下限
    ok, d = B(l,r,a[i]-l) // 事实上ok肯定是true，因为长度下限是由子问题A求出来的。
    count += d
    r = l # 更新长度上限
print(count)

正确性说明

长度为 $n$ 的小棒,划分长度上限为 $r$ , 记 $l = A(n), d = 1 + B(l,r,n-l)$ . 则根据以上关于子问题A、B的讨论知道一定存在一种划分方案 $b_1,b_2,\dots,b_{d} \quad (b_1 = l \wedge b_i \ge l)$ .

为了方便讨论，不妨假设划分方案中的数是不下降排列的，即 $\forall i(i<n) \Rightarrow b_i \le b_{i+1}$ .

假设存在一种划分方案 $c_1,c_2,\dots,c_m (m < d)$ .

由子问题A可知 $c_1 \le b_1$ .

因为子问题B是在限定了长度上下限时，求最小划分根数。故有：

$m-1 \ge B(c_1,r,n-c_1) = \lceil \frac{n-c_1}{r} \rceil \ge \lceil \frac{n-b_1}{r} \rceil = B(b_1,r,n-b_1) = d-1$. 即$m \ge d$

显然与假设 $m<d$ 矛盾。

结论1

这就说明划分方案
$b_1,b_2,\dots,b_{d} \quad (b_1 = l \wedge b_i \ge l)$
既是最短的小棒尽可能长的最佳方案，又是划分划分小棒数尽可能少的最佳方案。

一方面，对于当前小棒来讲，划分小棒数应该尽可能小；
另一方面，显然划分的最短小棒棒长会作为前面的小棒的划分上限，所以这个最短小棒越长越好。

而结论1说明我们的划分方案在上面两个方面努力的结果是一致的，所以我们可以采取算法所述的贪心措施。

字节跳动面试算法题一堆火柴棒长度的序列，切分成不下降的火柴棒长

同学问我一个字节跳动的面试的算法问题

子问题A(a,b)

结论

子问题B(a,b,n)

结论

回到原问题

算法

正确性说明

结论1

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

字节跳动面试算法题 一堆火柴棒长度的序列，切分成不下降的火柴棒长

同学问我一个字节跳动的面试的算法问题

子问题A(a,b)

结论

子问题B(a,b,n)

结论

回到原问题

算法

正确性说明

结论1

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

字节跳动面试算法题一堆火柴棒长度的序列，切分成不下降的火柴棒长