2938.區(qū)分黑球與白球[中等]

題目：

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

給你一個長度為?n?、下標(biāo)從?0?開始的二進制字符串?s，其中?1?和?0?分別代表黑色和白色的球。

在每一步中，你可以選擇兩個相鄰的球并交換它們。

返回「將所有黑色球都移到右側(cè)，所有白色球都移到左側(cè)所需的?最小步數(shù)」。

示例 1：

輸入：s = "101"
輸出：1
解釋：我們可以按以下方式將所有黑色球移到右側(cè)：
- 交換 s[0] 和 s[1]，s = "011"。
最開始，1 沒有都在右側(cè)，需要至少 1 步將其移到右側(cè)。

示例 2：

輸入：s = "100"
輸出：2
解釋：我們可以按以下方式將所有黑色球移到右側(cè)：
- 交換 s[0] 和 s[1]，s = "010"。
- 交換 s[1] 和 s[2]，s = "001"。
可以證明所需的最小步數(shù)為 2 。

示例 3：

輸入：s = "0111"
輸出：0
解釋：所有黑色球都已經(jīng)在右側(cè)。

提示：

• 1 <= n == s.length <= 105
• s[i]?不是?'0'，就是?'1'。

題目分析：

?????????題目意思就是把字符串內(nèi)的所有1都放到右邊，所有0都放到左邊，那這里的話我們就可以利用一個雙指針去遍歷整個字符串s，相當(dāng)于是快速排序的算法思路，左邊去找1，找到之后停下；同時右邊去找0，找到之后停下；然后兩個指針指的元素交換位置，此時需要的步數(shù)就是??????尾指針re減去頭指針pr，即 re-pr；直到遍歷到re==pr為止。

代碼實現(xiàn)：

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

?總結(jié)：

????????這段代碼的核心思想是通過雙指針將字符串按照交替模式中 ‘0’ 和 ‘1’ 的位置進行交換，以達到最小步數(shù)的目的。詳細解釋如下：

1. 將輸入字符串 s 轉(zhuǎn)換為列表 s，并獲取字符串的長度 n。
2. 如果輸入字符串長度為 1，則直接返回 0。
3. 初始化兩個指針 pr 和 re，分別指向字符串的開頭和末尾。
4. 初始化變量 ans 記錄最小步數(shù)。
5. 在 pr < re 的情況下，開始一個 while 循環(huán)：
   • 內(nèi)層 while 循環(huán)將 pr 指向的元素為 ‘0’ 且 pr 小于 re 時，pr 向后移動，直到找到第一個不為 ‘0’ 的位置。
   • 內(nèi)層 while 循環(huán)將 re 指向的元素為 ‘1’ 且 re 大于 pr 時，re 向前移動，直到找到第一個不為 ‘1’ 的位置。
   • 將 ans 增加 re - pr，即當(dāng)前位置需要交換的步數(shù)。
   • 交換 pr 和 re 指向的元素，然后將 pr 前進一步，re 后退一步。
6. 最終返回 ans，即將字符串轉(zhuǎn)換為 0101… 這種交替模式所需的最小步數(shù)。

?