2025-03-10:将 1 移动到末尾的最大操作次数。用go语言,给定一个二进制字符串 s,你可以进行以下操作:选择字符串中任

举报
福大大架构师每日一题 发表于 2025/03/10 09:20:02 2025/03/10
【摘要】 2025-03-10:将 1 移动到末尾的最大操作次数。用go语言,给定一个二进制字符串 s,你可以进行以下操作:选择字符串中任意一个下标 i(满足 i + 1 < s.length 的条件),并且 s[i] 为 ‘1’ 且 s[i + 1] 为 ‘0’。然后把 s[i] 向右移动,直到它到达字符串末尾或遇到另一个 ‘1’。例如,对于 s = “010010”,如果选择 i = 1,操作后得...

2025-03-10:将 1 移动到末尾的最大操作次数。用go语言,给定一个二进制字符串 s,你可以进行以下操作:选择字符串中任意一个下标 i(满足 i + 1 < s.length 的条件),并且 s[i] 为 ‘1’ 且 s[i + 1] 为 ‘0’。然后把 s[i] 向右移动,直到它到达字符串末尾或遇到另一个 ‘1’。例如,对于 s = “010010”,如果选择 i = 1,操作后得到的字符串将变为 “000110”。你的任务是计算可以进行的最大操作次数。

1 <= s.length <= 100000。

s[i] 为 ‘0’ 或 ‘1’。

输入: s = “1001101”。

输出: 4。

解释:

可以执行以下操作:

选择下标 i = 0。结果字符串为 s = “0011101”,下标0到2。

选择下标 i = 4。结果字符串为 s = “0011011”,下标4到5。

选择下标 i = 3。结果字符串为 s = “0010111”,下标3到4。

选择下标 i = 2。结果字符串为 s = “0001111”,下标2到3。

答案2025-03-10:

chatgpt

题目来自leetcode3228。

大体步骤如下:

1.初始化变量 size 为字符串 s 的长度,ans 和 cnt 均为初始值 0。

2.遍历字符串 s 中的每个字符,从位置 i = 0 开始。

3.如果当前字符为 ‘1’,则递增 cnt 的计数。

4.如果当前字符为 ‘0’ 且下一个字符也为 ‘1’,则将 cnt 的计数累加到 ans 上。

5.如果当前字符为 ‘0’ 且为字符串最后一个字符,则将 cnt 的计数累加到 ans 上。

6.返回 ans 作为结果。

对于输入字符串 s = “1001101”,根据算法的执行过程,可以得到以下操作:

  • 选择位置 i = 0 时,结果字符串为 “0011101”,共操作3次。

  • 选择位置 i = 4 时,结果字符串为 “0011011”,共操作2次。

  • 选择位置 i = 3 时,结果字符串为 “0010111”,共操作1次。

  • 选择位置 i = 2 时,结果字符串为 “0001111”,共操作1次。

因此,可以进行的最大操作次数为 4,与题目给出的输出一致。

总的时间复杂度为 O(n),其中 n 为字符串 s 的长度,因为算法需要遍历整个字符串。

总的额外空间复杂度为 O(1),因为除了常量级别的额外空间用于存储几个计数器之外,没有使用额外的动态空间。

Go完整代码如下:

package main

import "fmt"

func maxOperations(s string) int {
	size := len(s)
	ans := 0
	cnt := 0

	for i := 0; i < size; i++ {
		if s[i] == '1' {
			cnt++
		} else if i+1 < size && s[i+1] == '1' && s[i] == '0' {
			ans += cnt
		} else if i == size-1 && s[i] == '0' {
			ans += cnt
		}
	}
	return ans
}

func main() {
	// 测试代码
	s := "1001101"
	result := maxOperations(s)
	fmt.Println(result) // 输出结果
}

在这里插入图片描述

Python完整代码如下:

# -*-coding:utf-8-*-

def max_operations(s: str) -> int:
    size = len(s)
    ans = 0
    cnt = 0

    for i in range(size):
        if s[i] == '1':
            cnt += 1
        elif i + 1 < size and s[i + 1] == '1' and s[i] == '0':
            ans += cnt
        elif i == size - 1 and s[i] == '0':
            ans += cnt

    return ans

# 测试代码
if __name__ == "__main__":
    s = "1001101"
    result = max_operations(s)
    print(result)  # 输出结果

在这里插入图片描述

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。