李成笔记网

专注域名、站长SEO知识分享与实战技巧

LeetCode|2938|区分黑球与白球 黑球白球问题

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值在后

提交结果:

发表评论:

控制面板
您好,欢迎到访网站!
  查看权限
网站分类
最新留言