🔗 🟡 2938. Separate Black and White Balls 1423

tags: `Weekly Contest 372` `貪心(Greedy)` `雙指標(Two Pointers)` `字串(String)`

題意

桌子上有 $n$ 個球，每個球的顏色不是黑色，就是白色。

給定一個長度為 $n$ 的二進位字串 $s$ ，其中 $1$ 和 $0$ 分別代表黑色和白色的球。

每一步，你可以選擇兩個相鄰的球並將它們互換，返回「將所有黑色球都移到右側，所有白色球都移到左側所需的最小步數」。

思路：貪心(Greedy)

方法一：雙指標(Two Pointers)

使用兩個指針 $left$ 和 $right$ 分別指向字串的開頭和結尾，當 $s[left] = 0$ 時， $left$ 向右移動，直到 $left$ 指向黑色球或 $left \geq right$ 為止；當 $s[right] = 1$ 時， $right$ 向左移動，直到 $right$ 指向白色球或 $left \geq right$ 為止。

此時 $right$ 指向的白色球需要移動到 $left$ 的位置，因此需要移動的步數為 $right - left$ ，並將 $left$ 向右移動， $right$ 向左移動。

由於只有黑白兩種顏色的球，因此當所有白色球都移動到左側原本黑色球的位置時，右側自然就全部都是黑色球了。故移動時只需要考慮白色球移動到左側的步數（或是黑色球移動到右側的步數）即可。

複雜度分析

時間複雜度： $\mathcal{O}(n)$
空間複雜度： $\mathcal{O}(1)$

class Solution:
    def minimumSteps(self, s: str) -> int:
        n = len(s)
        left, right = 0, n - 1
        ans = 0
        while left < right:
            while left < right and s[left] == '0': # find the first 1 from left
                left += 1
            while left < right and s[right] == '1': # find the first 0 from right
                right -= 1
            if left < right: # if left < right, we need to swap s[right] to position left
                ans += right - left # the number of swaps needed
                left += 1
                right -= 1
        return ans

class Solution {
public:
    long long minimumSteps(string s) {
        long long ans = 0;
        int left = 0, right = s.size() - 1;
        while (left < right) {
            while (left < right && s[left] == '0') left++;
            while (left < right && s[right] == '1') right--;
            if (left < right){
                ans += right - left;
                left++;
                right--;
            }
        }
        return ans;
    }
};

方法二：貪心(Greedy)

上述思路可以進一步簡化，由於我們的目的是把所有黑色球移到右側，所有白色球移到左側，因此在每次遇到白色球時，需要將其移動到左側所有黑色球的左方，故我們其實只需要計算每個白色球左邊的黑色球數量即可。

使用一個變數 $cnt$ 來記錄每次遇到白色球時，左邊的黑色球數量，每次遇到白色球時，將 $cnt$ 加到答案中即可；遇到黑色球時，則將 $cnt$ 加一。

複雜度分析

時間複雜度： $\mathcal{O}(n)$
空間複雜度： $\mathcal{O}(1)$

class Solution:
    def minimumSteps(self, s: str) -> int:
        ans = 0
        cnt = 0 # 每次遇到 0 時，左邊的 1 的數量
        for ch in s:
            if ch == '1':
                cnt += 1
            else:
                ans += cnt
        return ans

class Solution {
public:
    long long minimumSteps(string s) {
        int n = s.size(), cnt = 0;
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '1') cnt++;
            else ans += cnt;
        }
        return ans;
    }
};