LeetCode 1769 - Minimum Number of Operations to Move All Balls to Each Box

https://chowdera.com/2021/03/20210326160903226c.html

Give you a length of n Binary string of boxes , among boxes[i] The value of is '0' It means the first one i A box is empty Of , and boxes[i] The value of is '1' There is... In the box One Pellet .

In one step , You can take One The ball moves from a box to an adjacent box . The first i A box and j Two adjacent boxes need to satisfy abs(i - j) == 1 . Be careful , After operation , There may be more than one ball in some boxes .

Returns a length of n Array of answer , among answer[i] It's moving all the balls to the second i What a box needs Minimum Operands .

Every answer[i] It all depends on the box The initial state Calculate .

https://leetcode-cn.com/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/

有 n 个盒子。给你一个长度为 n 的二进制字符串 boxes ，其中 boxes[i] 的值为 '0' 表示第 i 个盒子是 空 的，而 boxes[i] 的值为 '1' 表示盒子里有 一个 小球。

在一步操作中，你可以将 一个 小球从某个盒子移动到一个与之相邻的盒子中。第 i 个盒子和第 j 个盒子相邻需满足 abs(i - j) == 1 。注意，操作执行后，某些盒子中可能会存在不止一个小球。

返回一个长度为 n 的数组 answer ，其中 answer[i] 是将所有小球移动到第 i 个盒子所需的 最小 操作数。

每个 answer[i] 都需要根据盒子的 初始状态 进行计算。

输入：boxes = "110"

输出：[1,1,3]

解释：每个盒子对应的最小操作数如下：

1) 第 1 个盒子：将一个小球从第 2 个盒子移动到第 1 个盒子，需要 1 步操作。

2) 第 2 个盒子：将一个小球从第 1 个盒子移动到第 2 个盒子，需要 1 步操作。

3) 第 3 个盒子：将一个小球从第 1 个盒子移动到第 3 个盒子，需要 2 步操作。将一个小球从第 2 个盒子移动到第 3 个盒子，需要 1 步操作。共计 3 步操作。

示例 2：

输入：boxes = "001011"

输出：[11,8,5,4,3,4]

X. O(n) - left sum and right sum

https://leetcode.com/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/discuss/1075595/Java%3A-O(n)-left-sum-and-right-sum

    public int[] minOperations(String boxes) {
        int n = boxes.length();

        int[] left = new int[n];
        int[] right = new int[n];
        int[] ans = new int[n];

        int count = boxes.charAt(0) - '0';
        for(int i = 1 ; i < n ; i++){
            left[i] = left[i - 1] + count;
            count += boxes.charAt(i) - '0';
        }

        count = boxes.charAt(n - 1) - '0';
        for(int i = n - 2 ; i >=0 ; i--){
            right[i] = right[i + 1] + count;
            count += boxes.charAt(i) - '0';
        }
		
        for(int i = 0 ; i < n ; i++) {
            ans[i] = left[i] + right[i];
        }

        return ans;
    }

You can just get rid of the temp arrays. As problem asks us to return a new answer array, we won't consider that space in complexity analysis and hence space complexity is constant.

  public int[] minOperations(String boxes) {        
        int[] ans = new int[boxes.length()];
		int cnt = boxes.charAt(0) - '0';
		for(int i=1;i<boxes.length(); i++) {
			ans[i] = ans[i-1] + cnt;
			cnt += boxes.charAt(i) - '0';
		}
		
		int runner = 0; 
		cnt = boxes.charAt(boxes.length()-1) - '0';
		for(int i=boxes.length()-2;i>=0; i--) {
			runner += cnt; 
			ans[i] += runner;
			cnt += boxes.charAt(i) - '0'; 
		}
        return ans;  
  }

https://leetcode.com/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/discuss/1077682/Java-oror-DP-oror-beats-100-oror-2ms-oror-O(boxes.length)-O(1)

public int[] minOperations(String boxes) {
    int left = 0, right = 0, lsum = 0, rsum = 0, len = boxes.length();
	for (int i = 0; i < len; i++) {
		if (boxes.charAt(i) == '1') {
			right++;
			rsum += i;
		}
	}

	int[] ans = new int[len];

	for (int i = 0; i < len; i++) {
		ans[i] = lsum + rsum;
		if (boxes.charAt(i) == '1') {
			left++;
			right--;
		}
		lsum = lsum + left;
		rsum = rsum - right;
	}

	return ans;
}

https://leetcode.com/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/discuss/1075474/C%2B%2BJava-O(n)-LTR-%2B-RTL

We first "move" balls from left to right, and track how many ops it takes for each box.

For that, we count how many balls we got so far in cnt, and accumulate it in ops.

Then, we do the same from right to left.

public int[] minOperations(String boxes) {
    int[] res = new int[boxes.length()];
    for (int i = 0, ops = 0, cnt = 0; i < boxes.length(); ++i) {
       res[i] += ops;
       cnt += boxes.charAt(i) == '1' ? 1 : 0;
       ops += cnt;
    }    
    for (int i = boxes.length() - 1, ops = 0, cnt = 0; i >= 0; --i) {
        res[i] += ops;
        cnt += boxes.charAt(i) == '1' ? 1 : 0;
        ops += cnt;
    }
    return res;
}

https://chowdera.com/2021/03/20210326160903226c.html

What needs to be considered is , How to move to by all x The number of operations answer[x] Find all move to x+1 The number of operations answer[x+1]. about x+1 The ball on the left , Each ball will be operated once more , about x The ball on the right , Each will operate less than once . So , You just have to figure out x+1 The number of balls on the left side left(x+1) and x The number of balls on the right right(x) that will do . That is to say answer[x+1]=answer[x]+left(x+1)-right(x).

At present, we don't have to ask for it every time left and right, Save the position of the ball in line , Compare the current position and x,x+1 The relationship between , It can be calculated directly left and right The change of , But this code is easier to understand . You can try to optimize it yourself .

vector<int> minOperations(string boxes) { vector<int> positions; int n = boxes.size(); vector<int> answer(n, 0); for (int i = 0; i < n; i++) { if (boxes[i] == '1') { positions.push_back(i); if (i) answer[0] += i; } } for (int i = 1; i < n; i++) { // answer[i]=answer[i-1]+left(i)-right(i-1) int left = lower_bound(positions.begin(), positions.end(), i) - positions.begin(); int right = positions.end() - upper_bound(positions.begin(), positions.end(), i - 1); answer[i] = answer[i - 1] + left - right; } return answer; }

https://www.taodudu.cc/news/show-2114813.html

这个思路是：我们先找到把所有的 1 移到下标为 0 的起始位置需要的最小操作数为 $res[0]$。然后其余把所有 1 移到 $i$ 位置的操作数 = 把所有 1 移到 $i-1$ 位置的的操作数 -（右边的所有 1） + （左边的所有 1），即转移方程是：

$$res[i]=res[i-1]-(ones-visited)+visited$$

原理是什么呢？因为把所有位置移动到 $res[i]$ 位置相对于 $res[i-1]$ 位置来说，所有它右边位置的 1 少移动了一次，它左边位置的 1 多移动了一次。

时间复杂度：$O(N)$，空间复杂度：$O(1)$.

https://shareablecode.com/snippets/minimum-number-of-operations-to-move-all-balls-to-each-box-c-solution-leetcode-u8Vu-zhvF

    vector<int> minOperations(string boxes) {
        vector<int> result(size(boxes)); 
        for (int i = 0, accu = 0, cnt = 0; i < size(boxes); ++i) {
           result[i] += accu;
           cnt += (boxes[i] == '1') ? 1 : 0;
           accu += cnt;
        }
        for (int i = size(boxes) - 1, accu = 0, cnt = 0; i >= 0; --i) {
            result[i] += accu;
            cnt += (boxes[i] == '1') ? 1 : 0;
            accu += cnt;
        }
        return result;
    }

X.

https://www.taodudu.cc/news/show-2114813.html

本题的数据规模为 2000，用 $O(N^2)$ 的解法竟然能过。这个方法比较简单，直接对每个位置向左右两边统计具体各个 1 的位置之和。

    def minOperations(self, boxes: str) -> List[int]:
        N = len(boxes)
        res = [0] * N
        for i in range(N):
            left = [i - j for j in range(i) if boxes[j] == "1"]
            right = [j - i for j in range(i + 1, N) if boxes[j] == "1"]
            res[i] = sum(left) + sum(right)
        return res

https://kickstart.best/1769-minimum-number-of-operations-to-move-all-balls-to-each-box/

vector<int> minOperations(string boxes) {

int n = boxes.size();

vector<int> ret(n, 0);

for(int i = 0; i < n; ++i) {

for(int j = 0; j < n; ++j) {

if(boxes[j] == '1') {

ret[i] += abs(i - j);

}

}

}

return ret;

}