使列表中每个位置上的硬币数量相等所需的最少硬币移动次数

Question

在一次采访中，我遇到了以下问题：

给出一个大小为n的数组coin，其中coin[i]表示位于i位置的硬币数量。“移动”包括将一些硬币从i位置移动到i+1位置或i-1位置。重新分配硬币所需的最低移动次数是多少，以便每个位置都有一个硬币？你被保证有相同数量的硬币，因为有槽，以分发他们。

作为一个例子，给定输入

 [3, 0, 0, 0, 3, 0, 1]

输出是

[1, 1, 1, 1, 1, 1, 1]

需要四个步骤：

• 将两枚硬币从第0组移动到第1组。
• 将一枚硬币从第一桩移动到第二桩。
• 将一枚硬币从第四组移动到第三组。
• 将一枚硬币从第四组移动到第五组。

解决这个问题的有效方法是什么？

Answer 1

你只需扫描内部边界，并计数哪些是需要传输的。此计数是最低移动次数。

找到这个最小值的Python代码：

def nb_moves(game):
    N=len(game)-1 # number of inside borders.
    sum = -1
    for i in range(N):
        sum += game[i]
        if i == sum : N -= 1 # no transfer needed between cells i and i+1 . 
    return N

实际上，让N来计算吧。N显然是移动次数的最小值。此外，可以达到这一最低限度：

• 单元格可以分组为零和块，其中N在边框中的总数。
• 没有任何单元格必须由两边填充，因为这个单元格中的最终硬币数将大于1。
• 如果有两个单元格必须由双方清空，这是首先完成的:两个边界在两个移动中处理，将块分割成两个平衡块，并将一个单元格设置为1。
• 其余的块是单调的，可以从左到右或从右到左求解。

这样，每一个内部边界都会被跨越一次，而且只有一次。

一个实现在@templatetypedef的文章中得到了很好的解释。

有些尝试：

In [275]: solve([3, 0, 0, 0, 3, 0, 1])
Out[275]: 4

In [276]: solve([2,2,0,0])
Out[276]: 3

In [277]: solve([1,2,0,1])
Out[277]: 1

Answer 2

在O(n)时间内，我们可以用一个很好的观察来解决这个问题。诀窍是查看数组的最左边元素。如果你这样做，可能会发生以下三种情况：

• 最左边的值是1，在这种情况下，我们永远不想移动这枚硬币，也不需要在这里移动硬币。因此，我们可以想象将这个元素从数组中删除，并解决其余的子问题。例如，数组[1, 0, 0, 3]将转换为数组[0, 0, 3]。
• 最左边的值大于1。在这种情况下，我们知道除了一枚硬币外，我们必须将所有硬币移出这个位置，把它们移到右边。因此，我们可以这样做，在最左边留下一个1，然后通过上述情况下的逻辑忽略这个元素。例如，[3, 2, 0, 0, 0]将变成[1, 4, 0, 0, 0]，然后我们会删除1以获得[4, 0, 0, 0]。
• 最左边的值是0。在这种情况下，我们需要做一系列的动作来覆盖这个插槽。问题是我们采取了哪些行动来做到这一点。我们在这里需要做的观察是，最有效的方法是找到第一个槽k，其中位置k或之前的硬币数之和至少为k，然后从这堆硬币中挑选足够的硬币到达最左边的位置，使k-1移动，将这些硬币送过去。要知道为什么会这样，首先要注意的是，没有最优的策略，从位置k的右边发送任何硬币，通过位置k来填补最左边槽的空白，因为如果我们这样做，我们在前k个槽中就会有太多的硬币，所以必须送回一些硬币。因此，这意味着我们知道任何最优解都必须包括使用来自前k个槽的硬币来填补缺口。现在，想象一下，有一个更好的解决方案，比把硬币从堆k向左移动。这就意味着我们试图用少于k-1的硬币来覆盖第一个k-1槽，留下一个只能靠左移动k的洞。换句话说，任何解决方案都会涉及到k个左移，所以首先向左移动k永远不会是次优。

下面是在时间O(N)中运行的上述思想的一个实现：

int moves = 0;
for (int i = 0; i < n; i++) {
    /* Case 1 requires no action. */

    /* Case 2: leftmost pile has more than one coin. */
    if (coins[i] > 1) {
        coins[i + 1] += coins[i] - 1;
        /* No need to edit coins[i]; we won't touch it again. */
    }

    /* Case 3: Find a pile and shift it back. */
    else if (coins[i] == 0) {
        /* Total up coins until a free spot is found. */
        int k = 1;
        int zeroes = 1;
        int cumTotal = coins[i + k];

        while (cumTotal <= k) {
            k++;
            if (coins[k] == 0) zeroes++;
            cumTotal += coins[i + k];
        }

        /* Remove from that pile enough coins to cover all the zeroes encountered. */
        coins[k] -= zeroes;
        moves += k;

        /* Continue our scan after this position. */
        i = k;
    }
}
return moves;

Answer 3

一次只能移动一枚硬币：

这个问题的一个简单解决方案是迭代所有位置和每个有0硬币的位置，从左到右迭代找到一个有多个硬币的位置，并保持跟踪总移动要求将硬币从该位置带到初始位置。

int minimumCoinMoves(vector<int>&coins) {
    int n = coins.size();
    int moves = 0;
    for (int i = 0; i < n; ++i) {
        if (coins[i] == 0) {
            for (int j = 0; j < n; ++j) {
                if (coins[j] > 1) { // fill up ith place with coin in jth place
                    coins[i] = 1;
                    coins[j]--;
                    moves += abs(j - i); // total moves from jth to ith place
                    break;
                }
            }
        }
    }
    return moves;
}

如果我们假设我们有n硬币，那么这种方法将花费O(n * n)的时间复杂性。在n值很大的情况下，这种复杂性可能不可行。我们可以通过简单地修改上面的解决方案来跟踪其他向量中的额外硬币的位置，并从所有位置从0硬币的位置从左到右检索硬币，从而降低我们的复杂性。

int minimumCoinMoves(vector<int>&coins) {
    int n = coins.size();
    int moves = 0;
    vector<int>extraCoinIndices;
    for (int i = 0; i < n; ++i) {
        if (coins[i] > 1) {
            extraCoinIndices.push_back(i);
        }
    }
    int ptr = 0;
    for (int i = 0; i < n; ++i) {
        if (coins[i] == 0) {
            moves += abs(extraCoinIndices[ptr] - i);
            coins[i] = 1;
            coins[ extraCoinIndices[ptr] ]--;
            if (coins[ extraCoinIndices[ptr] ] == 1) ptr++;
        }
    }
    return moves;
}

编辑：

一次可以移动任意数量的硬币：

如果我们认为任何数量的硬币可以在移动中从一个位置移动，我们可以在O(n)中做以下更改来解决它。

int minimumCoinWithAnyNumberMoves(vector<int>&coins) {
    int n = coins.size();
    int moves = 0;
    int farZero = -1;
    int extraCoins = 0;
    for (int i = 0; i < n; ++i) {
        if (coins[i] == 0) {
            if (extraCoins > 0) {
                extraCoins--;
                moves++;
                continue;
            }
            farZero = (farZero == -1) ? i : farZero;
        } else {
            if (farZero == -1) {
                if (extraCoins > 0) moves++;
                extraCoins += (coins[i] - 1);
                continue;
            }
            assert(extraCoins == 0);
            int totZeros = i - farZero;
            moves += totZeros;
            if (coins[i] <= totZeros) {
                farZero = farZero + coins[i];
            } else {
                farZero = -1;
                extraCoins += (coins[i] - totZeros - 1);
            }
        }
    }
    return moves;
}