移动所有球到每个盒子所需的最小操作数 图解题解

这道题到底在问什么

输入

boxes="110"

输出

[1,1,3]

输入

boxes="001011"

输出

[11,8,5,4,3,4]

输入

boxes="011"

输出

[3,1,1]

先想最直接的笨办法

两遍都扫完了。left = [0,0,0,1,2,4] 是每个盒子左半边的代价,right = [11,8,5,3,1,0] 是右半边的代价。现在只要把两张表对应位置相加,每个盒子的最终答案就出来了。一个一个来。（动画第 17 步）

最优解：一步一步想明白

1. 3记牢:目标右移一格,左边每个球多走一步、右边每个球少走一步。左遍 left[i]=left[i-1]+左边球数,右遍 right[i]=right[i+1]+右边球数,合起来 answer[i]=left[i]+right[i]。
2. 4先看清画面。上面这排是盒子 boxes,值是 0 或 1,绿色的三格下标 2、4、5 里各有一个小球,其余是空盒。右边这张表要填的是 left,表示每个盒子左半边球搬过来的代价,现在还空着。我们先从左往右扫一遍把 left 填满,再从右往左扫一遍算 right,最后两个相加就是答案。先看第 0 个盒子。
3. 5左遍从第 0 个盒子开始。它是最左边,左边一个盒子都没有,自然没有球需要从左边搬过来,所以 left[0] 就是 0。计数器 cnt 记的是当前盒子左边有几个球,现在也是 0。把 0 记进 left 表的第 0 格。
4. 6目标挪到第 1 个盒子。先看刚跨过的下标 0 这一格,它是空盒,没有新球加入,cnt 还是 0。目标从 0 右移到 1,左边这 0 个球每个都要多走一步,所以在上一格 left[0] = 0 的基础上再加 cnt = 0,得到 left[1] = 0。
5. 7目标挪到第 2 个盒子。先看刚跨过的下标 1 这一格,它是空盒,没有新球加入,cnt 还是 0。目标从 1 右移到 2,左边这 0 个球每个都要多走一步,所以在上一格 left[1] = 0 的基础上再加 cnt = 0,得到 left[2] = 0。
6. 8目标挪到第 3 个盒子。先看刚跨过的下标 2 这一格,它是个球,现在它落到了目标的左边,cnt 加一变成 1。目标从 2 右移到 3,左边这 1 个球每个都要多走一步,所以在上一格 left[2] = 0 的基础上再加 cnt = 1,得到 left[3] = 1。
7. 9目标挪到第 4 个盒子。先看刚跨过的下标 3 这一格,它是空盒,没有新球加入,cnt 还是 1。目标从 3 右移到 4,左边这 1 个球每个都要多走一步,所以在上一格 left[3] = 1 的基础上再加 cnt = 1,得到 left[4] = 2。
8. 10目标挪到第 5 个盒子。先看刚跨过的下标 4 这一格,它是个球,现在它落到了目标的左边,cnt 加一变成 2。目标从 4 右移到 5,左边这 2 个球每个都要多走一步,所以在上一格 left[4] = 2 的基础上再加 cnt = 2,得到 left[5] = 4。
9. 11左表填满后,换个方向。右遍从最右的第 5 个盒子开始,它右边没有盒子了,没有球要从右边搬过来,所以 right[5] 是 0,记右边球数的 cnt 也从 0 起。这回我们从右往左走。
10. 12目标挪到第 4 个盒子。看刚跨过的右邻居下标 5,它是个球,现在落到目标右边,cnt 加一变成 1。目标从 5 左移到 4,右边这 1 个球每个都要多走一步,所以在 right[5] = 0 上加 cnt = 1,得到 right[4] = 1。
11. 13目标挪到第 3 个盒子。看刚跨过的右邻居下标 4,它是个球,现在落到目标右边,cnt 加一变成 2。目标从 4 左移到 3,右边这 2 个球每个都要多走一步,所以在 right[4] = 1 上加 cnt = 2,得到 right[3] = 3。
12. 14目标挪到第 2 个盒子。看刚跨过的右邻居下标 3,它是空盒,cnt 保持 2。目标从 3 左移到 2,右边这 2 个球每个都要多走一步,所以在 right[3] = 3 上加 cnt = 2,得到 right[2] = 5。
13. 15目标挪到第 1 个盒子。看刚跨过的右邻居下标 2,它是个球,现在落到目标右边,cnt 加一变成 3。目标从 2 左移到 1,右边这 3 个球每个都要多走一步,所以在 right[2] = 5 上加 cnt = 3,得到 right[1] = 8。
14. 16目标挪到第 0 个盒子。看刚跨过的右邻居下标 1,它是空盒,cnt 保持 3。目标从 1 左移到 0,右边这 3 个球每个都要多走一步,所以在 right[1] = 8 上加 cnt = 3,得到 right[0] = 11。
15. 17两遍都扫完了。left = [0,0,0,1,2,4] 是每个盒子左半边的代价,right = [11,8,5,3,1,0] 是右半边的代价。现在只要把两张表对应位置相加,每个盒子的最终答案就出来了。一个一个来。
16. 18第 0 个盒子:左半边代价 left[0] = 0,右半边代价 right[0] = 11,相加得 11。意思是把三个球全搬到最左边的 0 号盒子,一共要走 11 步。
17. 19第 1 个盒子:左半边代价 left[1] = 0,右半边代价 right[1] = 8,相加得 8。记进 answer 的第 1 位。
18. 20第 2 个盒子:左半边代价 left[2] = 0,右半边代价 right[2] = 5,相加得 5。记进 answer 的第 2 位。
19. 21第 3 个盒子:左半边代价 left[3] = 1,右半边代价 right[3] = 3,相加得 4。记进 answer 的第 3 位。
20. 22第 4 个盒子:左半边代价 left[4] = 2,右半边代价 right[4] = 1,相加得 3。记进 answer 的第 4 位。
21. 23第 5 个盒子:左半边代价 left[5] = 4,右半边代价 right[5] = 0,相加得 4。最后一个也算好了。
22. 24六个盒子的答案都填好了,answer = [11,8,5,4,3,4]。回看整套办法:不去为每个盒子从头加一遍,而是抓住相邻答案的差是左右两侧的球数,左扫一遍算 left、右扫一遍算 right,再逐位相加。总共只扫了三趟数组,线性时间就全部拿下。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        n = len(boxes)
        left = [0] * n
        right = [0] * n
        cnt = 0
        for i in range(1, n):
            if boxes[i - 1] == '1':
                cnt += 1
            left[i] = left[i - 1] + cnt
        cnt = 0
        for i in range(n - 2, -1, -1):
            if boxes[i + 1] == '1':
                cnt += 1
            right[i] = right[i + 1] + cnt
        return [a + b for a, b in zip(left, right)]

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> minOperations(string boxes) {
        int n = boxes.size();
        int left[n];
        int right[n];
        memset(left, 0, sizeof left);
        memset(right, 0, sizeof right);
        for (int i = 1, cnt = 0; i < n; ++i) {
            cnt += boxes[i - 1] == '1';
            left[i] = left[i - 1] + cnt;
        }
        for (int i = n - 2, cnt = 0; ~i; --i) {
            cnt += boxes[i + 1] == '1';
            right[i] = right[i + 1] + cnt;
        }
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) ans[i] = left[i] + right[i];
        return ans;
    }
};

import java.util.*;
class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();
        int[] left = new int[n];
        int[] right = new int[n];
        for (int i = 1, cnt = 0; i < n; ++i) {
            if (boxes.charAt(i - 1) == '1') {
                ++cnt;
            }
            left[i] = left[i - 1] + cnt;
        }
        for (int i = n - 2, cnt = 0; i >= 0; --i) {
            if (boxes.charAt(i + 1) == '1') {
                ++cnt;
            }
            right[i] = right[i + 1] + cnt;
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            ans[i] = left[i] + right[i];
        }
        return ans;
    }
}

复杂度

面试官可能追问