2938. 区分黑球与白球

题目

桌子上有 n 个球，每个球的颜色不是黑色，就是白色。

给你一个长度为 n 、下标从 0 开始的二进制字符串 s，其中 1 和 0 分别代表黑色和白色的球。

在每一步中，你可以选择两个相邻的球并交换它们。

返回「将所有黑色球都移到右侧，所有白色球都移到左侧所需的 最小步数」。

示例 1：

输入：s = "101"

输出：1

解释：我们可以按以下方式将所有黑色球移到右侧：

• 交换 s[0] 和 s[1]，s = "011"。
  最开始，1 没有都在右侧，需要至少 1 步将其移到右侧。

示例 2：

输入：s = "100"

输出：2

解释：我们可以按以下方式将所有黑色球移到右侧：

• 交换 s[0] 和 s[1]，s = "010"。
• 交换 s[1] 和 s[2]，s = "001"。
  可以证明所需的最小步数为 2 。

示例 3：

输入：s = "0111"

输出：0

解释：所有黑色球都已经在右侧。

提示：

• 1 <= n == s.length <= 10^5
• s[i] 不是 '0'，就是 '1'。

代码

完整代码

#include <string.h>
#include <stdio.h>
long long minimumSteps(char* s) {
    int n = strlen(s);
    long long res = 0;
    long long cntof1 = 0;
    for (int i = 0; i < n; i++)
    {
        if(s[i] == '1')
        {
            cntof1 ++;
        }
        else
        {
            res += cntof1;
        }
    }
    return res;
}

思路分析

该代码的目的是计算将所有黑色球（‘1’）移到右侧，所有白色球（‘0’）移到左侧所需的最小步数。算法核心类型是贪心算法，通过遍历字符串 s，每当遇到一个白色球（‘0’），计算将其左侧的所有黑色球（‘1’）移到其右侧所需的步数，并累加这些步数，从而得到最小步数。

拆解分析

1. 变量初始化

   int n = strlen(s);
   long long res = 0;
   long long cntof1 = 0;
   

   • n：存储字符串 s 的长度。
   • res：存储最终结果，即最小步数。
   • cntof1：用于统计遍历过程中遇到的黑色球（‘1’）的数量。

2. 遍历字符串

   for (int i = 0; i < n; i++)
   {
       if (s[i] == '1')
       {
           cntof1++;
       }
       else
       {
           res += cntof1;
       }
   }
   

   • 遍历字符串 s 的每个字符：
     • 如果字符是 ‘1’（黑色球），cntof1 递增。
     • 如果字符是 ‘0’（白色球），res 增加当前 cntof1 的值。这意味着将当前白色球左侧的所有黑色球向右移动到该白色球的右侧所需的步数。

3. 返回结果

   return res;
   

   • 返回总步数 res。

复杂度分析

• 时间复杂度：

  • 遍历字符串 s 需要 O(n) 的时间，其中 n 是字符串的长度。
  • 在遍历过程中，只有简单的加法和判断操作，因此整体时间复杂度为 O(n)。

• 空间复杂度：

  • 使用了几个额外的变量（n、res、cntof1），空间复杂度为 O(1)。

综上所述，代码的时间复杂度为 O(n)，空间复杂度为 O(1)。

结果

一题多解

分析最优性

当前算法的核心思路是贪心策略：每遇到一个白色球，统计其左侧黑色球的数量，并将这些黑色球移动到右侧。这种方法直接反映了问题的本质：我们只需要计算每个白色球左侧所有黑色球的位置差异，并累加这些差异即可。

更详细的贪心思路分析

1. 遍历字符一次：
   • 每个字符只需要访问一次，所以时间复杂度是 O(n)。
2. 累加步数：
   • 计算步数时，只需一个累加操作，空间复杂度是 O(1)。

为什么是最优的

1. 时间复杂度：

   • 对于一个长度为 n 的字符串，只需要遍历一遍，所以时间复杂度是 O(n)。没有办法在更短的时间内解决这个问题，因为至少需要访问每个字符一次。

2. 空间复杂度：

   • 只使用了常量级别的额外空间，即用于计数的几个变量。因此，空间复杂度是 O(1)，没有多余的存储需求。

其他可能的思路

虽然当前方法已经最优，但为了完整性，这里列出其他一些常见的算法思路，并分析其复杂度：

1. 双指针：
   • 使用两个指针，一个从左到右找到第一个黑色球的位置，另一个从右到左找到第一个白色球的位置，然后交换它们。
   • 然而，这个方法在最坏情况下仍需要 O(n) 的时间来遍历整个字符串，而且每次交换操作的次数和复杂度会增加。

#include <stdio.h>
#include <string.h>

long long minimumStepsTwoPointers(char* s) {
    int n = strlen(s);
    int left = 0, right = n - 1;
    long long res = 0;

    while (left < right) {
        while (left < n && s[left] == '0') left++;
        while (right >= 0 && s[right] == '1') right--;
        if (left < right) {
            res += (right - left);
            left++;
            right--;
        }
    }
    return res;
}

2. 动态规划：
   • 可以尝试构建一个动态规划表来记录状态转移，但这会引入额外的空间开销，而且复杂度分析会变得更复杂，可能不如贪心策略直接有效。

// 动态规划不太会

3. 前缀和后缀数组：
   • 构建前缀和后缀数组来记录每个位置的黑色球数量，这样可以在常数时间内计算出每个位置的移动步数。但构建这些数组需要额外的 O(n) 空间，不如贪心策略简洁。

#include <stdio.h>
#include <string.h>

long long minimumStepsPrefixSuffix(char* s) {
    int n = strlen(s);
    int prefix[n + 1];
    int suffix[n + 1];
    memset(prefix, 0, sizeof(prefix));
    memset(suffix, 0, sizeof(suffix));

    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + (s[i - 1] == '1');
    }

    for (int i = n - 1; i >= 0; i--) {
        suffix[i] = suffix[i + 1] + (s[i] == '0');
    }

    long long res = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') {
            res += prefix[i];
        }
    }

    return res;
}

结论

综上所述，当前的贪心策略已经是最优解，无论是时间复杂度还是空间复杂度都是最优的，无法进一步优化。