美文网首页
字节跳动面试算法题 一堆火柴棒长度的序列,切分成不下降的火柴棒长

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

作者: 稻云麦花 | 来源:发表于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_kn的一种整数划分。

    子问题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

    1. b=ka \; \Rightarrow c=a.
    2. b=ka+r \; (1 \le r \ge a-1)
      1. k \ge (a-2).
        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. k < (a-2).c_0=\lfloor \frac{b}{k+1} \rfloor = b \; div \; (k+1),则c=c_0. 下为证明.
        1. \because b > ka.
          1. 所以拆分的小棒不可能少于k 根.
        2. 假设划分成 p(p > k) 根小棒,最短的小棒c_1 > c_0.
          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. 考虑划分成k+1 根小棒.
          1. 注意有 b=c_0 \cdot (k+1)+r_0 (0 \le r_0 < k+1).
          2. k+1c_0 的小棒,然后剩余的 r_0r_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. 一方面,对于当前小棒来讲,划分小棒数应该尽可能小;

    2. 另一方面,显然划分的最短小棒棒长会作为前面的小棒的划分上限,所以这个最短小棒越长越好。

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

    相关文章

      网友评论

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

          本文链接:https://www.haomeiwen.com/subject/rfkgmhtx.html