力扣每日一题 6/6

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 <= 105
• s[i] 不是 '0'，就是 '1'。

题目分析：

         题目意思就是把字符串内的所有1都放到右边，所有0都放到左边，那这里的话我们就可以利用一个双指针去遍历整个字符串s，相当于是快速排序的算法思路，左边去找1，找到之后停下；同时右边去找0，找到之后停下；然后两个指针指的元素交换位置，此时需要的步数就是      尾指针re减去头指针pr，即 re-pr；直到遍历到re==pr为止。

代码实现：

class Solution:
    def minimumSteps(self, s: str) -> int:
        n=len(s)
        s=list(s)
        if n==1: return 0
        pr,re=0,n-1
        ans=0
        while pr<re:
            while s[pr]=='0' and pr<re:
                pr+=1
            while s[re]=='1' and re>pr:
                re-=1
            ans+=(re-pr)
            s[pr],s[re]=s[re],s[pr]
            pr+=1
            re-=1
        return ans

 总结：

        这段代码的核心思想是通过双指针将字符串按照交替模式中 ‘0’ 和 ‘1’ 的位置进行交换，以达到最小步数的目的。详细解释如下：

1. 将输入字符串 s 转换为列表 s，并获取字符串的长度 n。
2. 如果输入字符串长度为 1，则直接返回 0。
3. 初始化两个指针 pr 和 re，分别指向字符串的开头和末尾。
4. 初始化变量 ans 记录最小步数。
5. 在 pr < re 的情况下，开始一个 while 循环：
   • 内层 while 循环将 pr 指向的元素为 ‘0’ 且 pr 小于 re 时，pr 向后移动，直到找到第一个不为 ‘0’ 的位置。
   • 内层 while 循环将 re 指向的元素为 ‘1’ 且 re 大于 pr 时，re 向前移动，直到找到第一个不为 ‘1’ 的位置。
   • 将 ans 增加 re - pr，即当前位置需要交换的步数。
   • 交换 pr 和 re 指向的元素，然后将 pr 前进一步，re 后退一步。
6. 最终返回 ans，即将字符串转换为 0101… 这种交替模式所需的最小步数。