https://leetcode.cn/problems/separate-black-and-white-balls/description/?envType=daily-question&envId=2024-06-06
题目分析:
难度=中等
桌子上有 n 个球,每个球的颜色不是黑色,就是白色。给你一个长度为 n 、下标从 0 开始的二进制字符串 s,其中 1 和 0 分别代表黑色和白色的球。在每一步中,你可以选择两个相邻的球并交换它们。返回「将所有黑色球都移到右侧,所有白色球都移到左侧所需的 最小步数」。
理论/fake.code:
这题用一个实例说明最能说明问题
观察实例可以看到,要移动0的步数关键是前面有多少个1。
1.循环字符串
2.如果是1就记数cnt_one,表示当前1的个数=后面是0的移动步数
3.如果是0,前面的cnt_one记录了需要移动步数,累加移动步数记录cnt_move
4.返回总移动步数cnt_move
实例说明:
这里用字符a-z代表目标0
1 a 1 0 0 1 1 0 0 0 1 1 0 原字符串 当前移动 总移动
a 1 1 b 0 1 1 0 0 0 1 1 0 0前面有1个1,移动1步 +1 1
a b 1 1 c 1 1 0 0 0 1 1 0 0前面有2个1,移动2步 +2 3
a b c 1 1 1 1 d 0 0 1 1 0 0前面有2个1,移动2步 +2 5
a b c d 1 1 1 1 e 0 1 1 0 0前面有4个1,移动4步 +4 9
a b c d e 1 1 1 1 f 1 1 0 0前面有4个1,移动4步 +4 13
a b c d e f 1 1 1 1 1 1 g 0前面有4个1,移动2步 +4 17
a b c d e f g 1 1 1 1 1 1 0前面有6个1,移动6步 +6 23
注意/难点:
na
代码如下:
class Solution:
def minimumSteps(self, s: str) -> int:
cnt_one=0 #记录1的个数
cnt_move=0 #记录移动总数
for ch in s: #循环字符串
if ch=='1': #如果是1就记数cnt_one
cnt_one+=1
elif ch=='0': #如果是0记录累加移动步数
cnt_move+=cnt_one
return cnt_move #总移动步数cnt_move
#用list展示变量过程
def minimumSteps_exportList(self, s: str) -> int:
cnt_one=0 #记录1的个数
cnt_move=0 #记录移动总数
sList=[int(x) for x in s] #列表转字符串
i,j=0,0 #字符下标
for i,ch in enumerate(s): #循环字符串
if ch=='1': #如果是1就记数cnt_one
cnt_one+=1
elif ch=='0': #如果是0记录累加移动步数
cnt_move+=cnt_one
j=i-cnt_one #需要交换前字符下标
sList[i],sList[j]=sList[j],sList[i] #交换
print(sList)
return cnt_move #总移动步数cnt_move
# s = "101"
s="1010011000110"
ans1=Solution().minimumSteps(s)
print(f'answer-1 | {ans1}')
ans2=Solution().minimumSteps_exportList(s)
print(f'answer-2 | {ans2}')
变量过程:
整个交换过程如题目要求的,0值在前;1值在后