2938. 区分黑球与白球

🟠   🔖  贪心 双指针 字符串  🔗 力扣 LeetCode

题目

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 theminimum 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 <= 10^5
• s[i] is either '0' or '1'.

题目大意

桌子上有 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'。

解题思路

问题要求将所有黑色球（1）移到右侧，所有白色球（0）移到左侧，并计算最小的步数，在每次操作中，可以选择相邻的两个球进行交换。

解题的关键是计算白色球和黑色球之间的“错位”程度，因此，可以从左到右遍历字符串，并计算每个白色球被黑色球阻挡的步数。

1. 用 curWhite 记录遍历时白色球的数量，初始化为 -1，每遇到一个白色球，就增加 curWhite 计数。
2. 用 minStep 记录所有白色球需要的总移动步数，初始化为 0。
3. 从左到右遍历字符串 s，每当遇到一个白色球时：

• 将 curWhite 加 1，表示当前白色球数加一。
• 计算当前白色球应该在的位置与它当前所在的位置的差值，并加到 minStep 中。

4. 最终 minStep 的值就是将所有白色球移到左侧、所有黑色球移到右侧所需的最小步数。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度。我们仅需遍历字符串一次，每次操作的复杂度为常数级。
• 空间复杂度：O(1)，除了几个辅助变量外，没有额外使用其他空间。

代码

/**
 * @param {string} s
 * @return {number}
 */
var minimumSteps = function (s) {
	let curWhite = -1,
		minStep = 0;
	for (let i = 0; i < s.length; i++) {
		const char = s[i];
		if (char == '0') {
			curWhite++;
			minStep += i - curWhite;
		}
	}
	return minStep;
};