模板手机网站建设公司排名,做网站的资源哪里找,长尾关键词挖掘站长工具,wordpress授权系统2938.区分黑球与白球[中等]
题目#xff1a;
桌子上有 n 个球#xff0c;每个球的颜色不是黑色#xff0c;就是白色。
给你一个长度为 n 、下标从 0 开始的二进制字符串 s#xff0c;其中 1 和 0 分别代表黑色和白色的球。
在每一步中#xff0c;你可以选择两个相邻的…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 105s[i] 不是 0就是 1。
题目分析 题目意思就是把字符串内的所有1都放到右边所有0都放到左边那这里的话我们就可以利用一个双指针去遍历整个字符串s相当于是快速排序的算法思路左边去找1找到之后停下同时右边去找0找到之后停下然后两个指针指的元素交换位置此时需要的步数就是 尾指针re减去头指针pr即 re-pr直到遍历到repr为止。
代码实现
class Solution:def minimumSteps(self, s: str) - int:nlen(s)slist(s)if n1: return 0pr,re0,n-1ans0while prre:while s[pr]0 and prre:pr1while s[re]1 and repr:re-1ans(re-pr)s[pr],s[re]s[re],s[pr]pr1re-1return ans 总结 这段代码的核心思想是通过双指针将字符串按照交替模式中 ‘0’ 和 ‘1’ 的位置进行交换以达到最小步数的目的。详细解释如下
将输入字符串 s 转换为列表 s并获取字符串的长度 n。如果输入字符串长度为 1则直接返回 0。初始化两个指针 pr 和 re分别指向字符串的开头和末尾。初始化变量 ans 记录最小步数。在 pr re 的情况下开始一个 while 循环 内层 while 循环将 pr 指向的元素为 ‘0’ 且 pr 小于 re 时pr 向后移动直到找到第一个不为 ‘0’ 的位置。内层 while 循环将 re 指向的元素为 ‘1’ 且 re 大于 pr 时re 向前移动直到找到第一个不为 ‘1’ 的位置。将 ans 增加 re - pr即当前位置需要交换的步数。交换 pr 和 re 指向的元素然后将 pr 前进一步re 后退一步。最终返回 ans即将字符串转换为 0101… 这种交替模式所需的最小步数。
