拼多多校招笔试算法题：一行公式搞定“多多的魔术盒子”

By Long Luo

众多IT大厂中拼多多虽然工作强度很大，但在给钱方面非常大方。大厂给的钱多，但要求也高。下面就来挑战拼多多 2020 年校招笔试算法题 ¹ 中第一题：多多的魔术盒子 ² ，看看难度如何。

最少的操作次数该怎么做？

根据题意，我们关键是要找到最少次数这个方法，那如何操作才能使用最少次数呢？

当面对复杂问题时，我们需要从简单情况入手，分析其中规律，找到突破口。

1. \(N = 1\) 时，显然选择 \(X = 1\) ，需要 \(1\) 次操作；
2. \(N = 2\) 时，可以先选择 \(X = 1\) ，再选择 \(X = 2\) ，需要 \(2\) 次操作；
3. \(N = 3\) 时，只有先选择 \(X = 2\) ，再选择 \(X = 1\) ，最少需要 \(2\) 次操作；
4. \(N = 4\) 时，可以先选择 \(X = 2\) 或者 \(X = 3\) ，最少需要 \(3\) 次操作；

通过分析发现，每次操作之后，球的数量都会动态变化。如果每次都选择中间的数字，这样每次操作之后，如果 \(N\) 为奇数的话，可以变成 \(2\) 个对称相同的数组， \(N\) 为偶数的话，则 \(2\) 个数组中元素值会相差 \(1\) ，再选择元素值更多的数组进行消除，这样可以实现操作次数最少。

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

private static int leastTimes_power(int n) {
    int ans = 1;

    for (int i = 0; i <= Math.sqrt(n); i++) {
        if (Math.pow(2, i) <= n) {
            ans = i;
        } else {
            break;
        }
    }

    return ans + 1;
}

为什么每次选取中间的数字进行操作次数最少呢？下面我们就来严谨的证明下！

为什么这样操作次数最少？

对于 \(N\) 个魔法盒子中的球，可以视为一个数组 \(A\) ：对于 \([1, 2, 3 \cdots, N - 1, N]\) 。第一次操作选择哪个数呢？为不失普遍性，假设选择了任意正整数 \(k\) ，这样序号大于等于 \(k\) 的盒子中球的数量都要减去 \(k\) ，那么减少之后的数组 \(B\) 为： \([1, 2, 3 \cdots, k-1, 0, 1, 2, \cdots N - k]\) 。

那么第二次操作选哪个数呢？分析数组 \(B\) ，在第一次操作选择了 \(k\) 之后，数组 \(B\) 以 \(0\) 为中心，分为 \(2\) 个部分，左边是 \([0, 1, \cdots k - 1]\) ，右边是 \([1, 2, \cdots , N - k]\) 。这里有没有想到分治法？问题相同但规模更小！

这里又可以分成 \(3\) 种情况：

1. 如果 \(k - 1 = N - k\) ，左右两边数字相同，那么只要能消除左边部分，右边也可以消除；
2. 如果 \(k - 1 > N - k\) ，左边元素比右边多，只要能够消除掉左边的部分，右边的自然也会消除；
3. 如果 \(k - 1 < N - k\) ，左边元素比右边少，同理可得，只需要消除右边部分。

综合，每次选择 \(k\) 之后，数组可以拆分为两个部分，而答案只和其中元素更多的部分有关。设函数 \(f(N)\) 表示 \(N\) 时为最少操作次数，不难得到下列方程

\[ f(N) = \min(\max(f(1), f(N-2)), \max(f(2), f(N-3)), \cdots, \max(f(\frac{N}{2}, \frac{N}{2}))) + 1 \tag{1} \label{1} \]

可以直观看出函数 \(f(N)\) 是递增的，但既然是证明就需要严谨，下面我们来简单证明下：

证明 \(f(N)\) 是递增函数

对于 \(N\) 个盒子，在选择了 \(k\) 之后，我们可以得到下列表达式：

\[ f(N) = 1 + \min_{1 \le k \le N} \max \left( f(k-1), f(N-k) \right) \tag{2} \label{2} \]

要证对于任意正整数 \(N\) ，有 \(f(N+1) \ge f(N)\) 。

我们可以使用归纳法：

1. 显然 \(f(1) = 1\) ，故命题对 \(N = 1\) 成立。

2. 假设对所有 \(m \le N\) 都有 \(f(m+1) \ge f(m)\) 。

比较 \(f(N+1)\) 与 \(f(N)\) 。由递推式，

\[ \begin{aligned} f(N) &= 1 + \min_{1 \le k \le N} \max \left( f(k-1), f(N-k) \right)), \\ f(N+1) &= 1 + \min_{1 \le k \le N + 1} \max \left( f(k-1), f(N+1-k) \right)) \end{aligned} \]

对任意固定的 \(k\) ( \(1 \le k \le N\) )，由归纳假设可得： \(f(N+1-k) \ge f(N-k)\) 。

故有对于任意 \(k\) 都满足：

\[ \max(f(k-1),f(N+1-k)) \ge \max(f(k-1),f(N-k)) \tag{3} \label{3} \]

因此将两边对 \(k\) 取最小得到

\[ \min_{1 \le k \le N} \max \left( f(k-1), f(N+1-k) \right) \ge \min_{1 \le k \le N} \max \left( f(k-1), f(N-k) \right) \]

两边同时 \(+1\) 可得：

\[ 1 + \min_{1 \le k \le N} \max \left( f(k-1), f(N+1-k) \right) \ge 1 + \min_{1 \le k \le N} \max \left( f(k-1), f(N-k) \right) \]

因此有：

\[ f(N+1) = 1 + \min_{1 \le k \le N + 1} \max \left( f(k-1), f(N+1-k) \right) \ge 1 + \min_{1 \le k \le N} \max \left( f(k-1), f(N+1-k) \right) \]

结合可得：

\[ f(N+1) \ge 1 + \min_{1 \le k \le N} \max \left( f(k-1), f(N-k) \right)) = f(N). \]

这样就证明了对于所有正整数 \(N\) 都有 \(f(N+1) \ge f(N)\) 。

根据上述证明 \(f(N)\) 是递增函数，那么公式 \(\eqref{1}\) 可以化简为：

\[ f(N) = \min(f(N-2), f(N-3), \cdots , f(\frac{N}{2})) + 1 = f(\frac{N}{2}) + 1 \tag{4} \label{4} \]

容易得出：

\[ \begin{aligned} f(N) &= f(\frac {N}{2}) + 1 \\ f(\frac {N}{2}) &= f(\frac {N}{4})+1 \\ &\cdots \\ f(1) &= 1 \end{aligned} \]

等式两边相加，合并同类项最终可以得到：

\[ f(N) = \log_{2}{N} + 1 \]

则代码实现为：

1
2
3

private static int leastTimes(int n) {
    return (int) (Math.log(n) / Math.log(2)) + 1;
}

总结

这道校招题难度并不大，也就 Medium 难度吧！解题关键在于读懂题意，通过分析题意找到如何实现最少次数操作。在没有头绪的情况下，可以先从最简单的情况开始分析，找到突破口。

参考资料