LeetCode-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 <= 10^5
s[i] 不是 ‘0’,就是 ‘1’。

解题思路一:贪心

在这里插入图片描述

class Solution:
    def minimumSteps(self, s: str) -> int:
        ans = cnt1 = 0
        for c in s:
            if c == '1':
                cnt1 += 1
            else:
                ans += cnt1
        return ans

时间复杂度:O(n)
空间复杂度:O(1)

解题思路二:一次遍历统计’1’的个数,找’0’后累加左边的’1’的个数

想不到贪心怎么办?背吧。

class Solution:
    def minimumSteps(self, s):
        ans, sum = 0, 0
        for i in range(len(s)):
            if s[i] == '1':
                sum += 1
            else:
                ans += sum
        return ans

时间复杂度:O(n)
空间复杂度:O(1)

解题思路三:


时间复杂度:O(n)
空间复杂度:O(1)


创作不易,观众老爷们请留步… 动起可爱的小手,点个赞再走呗 (๑◕ܫ←๑)
欢迎大家关注笔者,你的关注是我持续更博的最大动力


原创文章,转载告知,盗版必究



在这里插入图片描述


在这里插入图片描述
♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠

相关推荐

  1. leetcode 2938.区分

    2024-06-09 17:14:02       31 阅读
  2. LeetCode-day04-2938. 区分

    2024-06-09 17:14:02       28 阅读
  3. 案例【C#】

    2024-06-09 17:14:02       33 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-06-09 17:14:02       106 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-06-09 17:14:02       116 阅读
  3. 在Django里面运行非项目文件

    2024-06-09 17:14:02       95 阅读
  4. Python语言-面向对象

    2024-06-09 17:14:02       103 阅读

热门阅读

  1. TypeScript常见面试题第十一节

    2024-06-09 17:14:02       29 阅读
  2. TalkingData数据统计:洞察数字世界的关键工具

    2024-06-09 17:14:02       43 阅读
  3. Django中drf动态过滤查询

    2024-06-09 17:14:02       42 阅读
  4. 006 RabbitMQ

    2024-06-09 17:14:02       38 阅读
  5. 记录一次jlink连不上cpu的情况

    2024-06-09 17:14:02       39 阅读
  6. wordpress网站建设详细过程

    2024-06-09 17:14:02       41 阅读
  7. 移动端前端开发遇到过的Andorid和IOS的差异记录

    2024-06-09 17:14:02       33 阅读
  8. Audio音频资源播放

    2024-06-09 17:14:02       48 阅读