区分黑球与白球

There are n balls on a table, each ball has a color black or white.

You are given a 0-indexed binary string s of length n, where 1 and 0 represent black and white balls, respectively.

In each step, you can choose two adjacent balls and swap them.

Return the minimum number of steps to group all the black balls to the right and all the white balls to the left.

 

Example 1:

Input: s = "101"
Output: 1
Explanation: We can group all the black balls to the right in the following way:
- Swap s[0] and s[1], s = "011".
Initially, 1s are not grouped together, requiring at least 1 step to group them to the right.

Example 2:

Input: s = "100"
Output: 2
Explanation: We can group all the black balls to the right in the following way:
- Swap s[0] and s[1], s = "010".
- Swap s[1] and s[2], s = "001".
It can be proven that the minimum number of steps needed is 2.

Example 3:

Input: s = "0111"
Output: 0
Explanation: All the black balls are already grouped to the right.

 

Constraints:

• 1 <= n == s.length <= 105
• s[i] is either '0' or '1'.

/*
 * 题目思路：
 * 使用Java Stream实现与上述Java代码相同的逻辑。通过遍历字符数组计算黑色球的数量和需要移动的步数。
 */
import java.util.stream.IntStream;

public class Solution {
    public int minMovesToMoveBalls(String s) {
        int[] result = IntStream.range(0, s.length()).mapToObj(i -> s.charAt(i)).reduce(new int[]{0, 0}, (acc, c) -> {
            if (c == '1') {
                acc[0]++;
            } else {
                acc[1] += acc[0];
            }
            return acc;
        }, (a, b) -> new int[]{a[0] + b[0], a[1] + b[1]});
        return result[1];
    }
}

题解的思路是通过一次遍历来统计将所有白球移至左侧（或黑球移至右侧）所需的最小交换次数。具体实现为：初始化两个变量，`b_cnt` 用来记录至当前位置为止遇到的黑球数量，`ans` 用来累计总的交换次数。当遇到一个白球（`'0'`）时，意味着这个白球需要通过交换越过之前已经统计过的所有黑球，因此要将`b_cnt`（当前已经遇到的黑球数量）加到`ans`上。当遇到黑球（`'1'`）时，仅将`b_cnt`加一，表示又遇到了一个黑球，不需要额外操作。

O(n)

O(1)