class Solution {
public:
int maxOperations(string s) {
}
};
100360. 将 1 移动到末尾的最大操作次数
给你一个 二进制字符串 s。
你可以对这个字符串执行 任意次 下述操作：
i（ i + 1 < s.length ），该下标满足 s[i] == '1' 且 s[i + 1] == '0'。s[i] 向 右移 直到它到达字符串的末端或另一个 '1'。例如，对于 s = "010010"，如果我们选择 i = 1，结果字符串将会是 s = "000110"。返回你能执行的 最大 操作次数。
示例 1：
输入： s = "1001101"
输出： 4
解释：
可以执行以下操作：
i = 0。结果字符串为 s = "0011101"。i = 4。结果字符串为 s = "0011011"。i = 3。结果字符串为 s = "0010111"。i = 2。结果字符串为 s = "0001111"。示例 2：
输入： s = "00111"
输出： 0
提示：
1 <= s.length <= 105s[i] 为 '0' 或 '1'。原站题解
golang 解法, 执行用时: 14 ms, 内存消耗: 5.9 MB, 提交时间: 2024-07-22 23:03:04
func maxOperations(s string) (ans int) {
cnt1 := 0
for i, c := range s {
if c == '1' {
cnt1++
} else if i > 0 && s[i-1] == '1' {
ans += cnt1
}
}
return
}
java 解法, 执行用时: 10 ms, 内存消耗: 44.5 MB, 提交时间: 2024-07-22 23:02:52
class Solution {
public int maxOperations(String S) {
char[] s = S.toCharArray();
int ans = 0;
int cnt1 = 0;
for (int i = 0; i < s.length; i++) {
if (s[i] == '1') {
cnt1++;
} else if (i > 0 && s[i - 1] == '1') {
ans += cnt1;
}
}
return ans;
}
}
cpp 解法, 执行用时: 30 ms, 内存消耗: 14 MB, 提交时间: 2024-07-22 23:02:41
class Solution {
public:
int maxOperations(string s) {
int ans = 0, cnt1 = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '1') {
cnt1++;
} else if (i && s[i - 1] == '1') {
ans += cnt1;
}
}
return ans;
}
};
python3 解法, 执行用时: 106 ms, 内存消耗: 16.8 MB, 提交时间: 2024-07-22 23:02:26
'''
把 1 当作车，想象有一条长为 n 的道路上有一些车。
我们要把所有的车都排到最右边，例如 011010 最终要变成 000111。
下文用 s→t 表示车的位置变化。
如果我们优先操作右边的车，那么每辆车都只需操作一次：
011010
➡️011001
➡️010011
➡️000111
一共需要操作 3 次。
如果我们优先操作左边的（能移动的）车，这会制造大量的「堵车」，那么每辆车的操作次数就会更多。
011010
➡010110
➡001110
➡001101
➡001011
➡000111
一共需要操作 5 次。
'''
class Solution:
def maxOperations(self, s: str) -> int:
ans = cnt1 = 0
for i, c in enumerate(s):
if c == '1':
cnt1 += 1
elif i and s[i - 1] == '1':
ans += cnt1
return ans