2025-03-10：将 1 移动到末尾的最大操作次数

福大大架构师每日一题

发布于 2025-03-11 21:25:30

3800

代码可运行

运行总次数：0

代码可运行

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[1]

题目来自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++
        } elseif i+1 < size && s[i+1] == '1' && s[i] == '0' {
            ans += cnt
        } elseif i == size-1 && s[i] == '0' {
            ans += cnt
        }
    }
    return ans
}

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

Python完整代码如下：

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

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

    for i inrange(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 - 1and s[i] == '0':
            ans += cnt

    return ans

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