2025-03-10:将 1 移动到末尾的最大操作次数。用go语言,给定一个二进制字符串 s,你可以进行以下操作:选择字符串中任
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:
题目来自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) # 输出结果
- 点赞
- 收藏
- 关注作者
评论(0)