推箱子

给定一个字符串 s；

s[i] 若为 0 代表第 i 个位置上没有箱子；

s[i] 若为 1 代表第 i 个位置上有一个箱子；

请你输出一个数组 ans，元素 ans[i] 代表将其他位置上的所有箱子都推到第 i 个位置的最少次数；

每次只能推动一个箱子到隔壁格子。

完善代码

class Solution {
public:
    vector<int> minOperations(string boxes) {

    }
};

样例说明

输入 s = "110"

输出 ans = [1, 1, 3]

数据范围

\(1 \leq\) s.size() \(\leq 2000\)。

暴力模拟

时间复杂度为 \(O(n^2)\)。

代码示例

class Solution {
public:
    vector<int> minOperations(string boxes) {
        vector<int> ans(boxes.size(), 0);
        for (int i = 0; i < int (boxes.size()); i ++)
            for (int j = 0; j < int (boxes.size()); j ++)
                ans[i] += abs(i - j) * (boxes[j] - '0');
        return ans;
    }
};

逐步积累

对于位置 i 若我已知将 \(0 \sim i - 1\) 的箱子都推到 i - 1 位置需要消耗 a[i - 1] 那么多次，并且此时 i - 1 号位置上的箱子数为 b[i - 1]；

那么将 \(0 \sim i\) 位置上的箱子都推动到 i 位置上需要的次数就为：a[i] += a[i - 1] + b[i - 1]，此时箱子数为 b[i] = s[i] + b[i - 1]；

若我还知道将位置 i + 1 \(\sim\) n 上的箱子都推到 i + 1 位置需要消耗 a[i + 1] 那么多次，并且此时 i + 1 号位置上的箱子数为 b[i + 1];

那么将 i \(\sim\) n 上的箱子都推到 i 位置需要消耗的次数为：a[i] += a[i + 1] + b[i + 1]，此时箱子数为 b[i] = s[i] + b[i + 1]；

我只需要从头到尾，从尾到头各遍历一次就能累计求出结果；

时间复杂度为 \(O(n)\)。

代码示例

class Solution {
public:
    vector<int> minOperations(string boxes) {
        int n = boxes.size();
        vector<int> ans, a, b;
        ans = a = b = vector<int>(n, 0);
        for (int i = 0; i < n; i ++)
        {
            b[i] += boxes[i] - '0';
            if (i == 0) continue;
            b[i] += b[i - 1];
            ans[i] += a[i] += a[i - 1] + b[i - 1];
        }
        a = b = vector<int>(n, 0);
        for (int i = n - 1; i >= 0; i --)
        {
            b[i] += boxes[i] - '0';
            if (i == n - 1) continue;
            b[i] += b[i + 1];
            ans[i] += a[i] += a[i + 1] + b[i + 1];
        }
        return ans;
    }
};