class Solution {
public:
int secondsToRemoveOccurrences(string s) {
}
};
2380. 二进制字符串重新安排顺序需要的时间
给你一个二进制字符串 s 。在一秒之中，所有 子字符串 "01" 同时 被替换成 "10" 。这个过程持续进行到没有 "01" 存在。
请你返回完成这个过程所需要的秒数。
示例 1：
输入：s = "0110101" 输出：4 解释： 一秒后，s 变成 "1011010" 。 再过 1 秒后，s 变成 "1101100" 。 第三秒过后，s 变成 "1110100" 。 第四秒后，s 变成 "1111000" 。 此时没有 "01" 存在，整个过程花费 4 秒。 所以我们返回 4 。
示例 2：
输入：s = "11100" 输出：0 解释： s 中没有 "01" 存在，整个过程花费 0 秒。 所以我们返回 0 。
提示：
1 <= s.length <= 1000s[i] 要么是 '0' ，要么是 '1' 。原站题解
cpp 解法, 执行用时: 8 ms, 内存消耗: 6.3 MB, 提交时间: 2022-12-09 15:21:23
class Solution {
public:
int secondsToRemoveOccurrences(string &s) {
int f = 0, pre0 = 0;
for (char c : s)
if (c == '0') ++pre0;
else if (pre0) f = max(f + 1, pre0); // 前面有 0 的时候才会移动
return f;
}
};
golang 解法, 执行用时: 4 ms, 内存消耗: 2 MB, 提交时间: 2022-12-09 15:20:56
func secondsToRemoveOccurrences(s string) (f int) {
pre0 := 0
for _, c := range s {
if c == '0' {
pre0++
} else if pre0 > 0 { // 前面有 0 的时候才会移动
f = max(f+1, pre0)
}
}
return
}
func max(a, b int) int { if b > a { return b }; return a }
java 解法, 执行用时: 3 ms, 内存消耗: 39.9 MB, 提交时间: 2022-12-09 15:20:44
class Solution {
public int secondsToRemoveOccurrences(String s) {
int f = 0, pre0 = 0;
for (var i = 0; i < s.length(); i++)
if (s.charAt(i) == '0') ++pre0;
else if (pre0 > 0) f = Math.max(f + 1, pre0); // 前面有 0 的时候才会移动
return f;
}
}
python3 解法, 执行用时: 44 ms, 内存消耗: 14.9 MB, 提交时间: 2022-12-09 15:20:31
'''
定义 f[i] 表示 s 的前 i 个字符中的1完成左移所需的秒数
如果 s[i]=0，此处无1，则 f[i]=f[i−1]
如果 s[i]=1，记前 i 个字符中0的个数为 pre0[i]，则 f[i] 至少为 pre0[i]
'''
class Solution:
def secondsToRemoveOccurrences(self, s: str) -> int:
f = pre0 = 0
for c in s:
if c == '0': pre0 += 1
elif pre0: f = max(f + 1, pre0) # 前面有 0 的时候才会移动
return f
python3 解法, 执行用时: 108 ms, 内存消耗: 15.2 MB, 提交时间: 2022-12-09 13:14:56
class Solution:
def secondsToRemoveOccurrences(self, s: str) -> int:
n = 0
while '01' in s:
s = s.replace('01', '10')
n += 1
return n