1769.minimum-number-of-operations-to-move-all-balls-to-each-box 移动所有球到每个盒子所需的最小操作数

问题描述

1769.移动所有球到每个盒子所需的最小操作数

解题思路

暴力求解，时间复杂度为\(\Theta(n^2)\);

可以考虑利用前缀和来降低时间复杂度:
设nums[i]是前i + 1个盒子里的球的总个数，res[i]为将所有球移到第i + 1个盒子里所需要的操作数，sum为球总个数，移到第i + 1个盒子相比移到第i个盒子，左边的球各要多移一步，右边的球各少移一步，因此有那么有:res[i] = res[i - 1] + nums[i - 1] - (sum - nums[i - 1])，

代码

class Solution {
public:
    vector<int> minOperations(string boxes) {
        vector<int> nums(boxes.size(), 0);
        int sum = boxes[0] - '0';
        nums[0] = boxes[0] - '0';
        for (int i = 1; i < boxes.size(); i++) {
            if (boxes[i] == '1') {
                nums[i] = nums[i - 1] + 1;
                sum++;
            } else
                nums[i] = nums[i - 1];
        }
        vector<int> res(boxes.size(), 0);
        for (int i = 1; i < boxes.size(); i++) {
            res[0] += i * (boxes[i] - '0');
        }
        for (int i = 1; i < boxes.size(); i++) {
            res[i] = res[i - 1] + nums[i - 1] - (sum - nums[i - 1]);
        }
        return res;
    }
};