LeetCode每日一题(2380. Time Needed to Rearrange a Binary String)

You are given a binary string s. In one second, all occurrences of “01” are simultaneously replaced with “10”. This process repeats until no occurrences of “01” exist.

Return the number of seconds needed to complete this process.

Example 1:

Input: s = “0110101”
Output: 4

Explanation:
After one second, s becomes “1011010”.
After another second, s becomes “1101100”.
After the third second, s becomes “1110100”.
After the fourth second, s becomes “1111000”.
No occurrence of “01” exists any longer, and the process needed 4 seconds to complete,
so we return 4.

Example 2:

Input: s = “11100”
Output: 0

Explanation:
No occurrence of “01” exists in s, and the processes needed 0 seconds to complete,
so we return 0.

Constraints:

• 1 <= s.length <= 1000
• s[i] is either ‘0’ or ‘1’.

---

dp[i]为整理 s[0…=i]所需要的秒数, zeros 为到 i 为止的 0 的数量，如果 s[i+1] == ‘1’, 则 dp[i+1] = max(zeros, dp[i] + 1), 如果 s[i+1] == ‘0’, 则 dp[i+1] = dp[i-1]。

---

impl Solution {
    pub fn seconds_to_remove_occurrences(s: String) -> i32 {
        let chars: Vec<char> = s.chars().collect();
        let mut dp = vec![0; s.len()];
        let mut zeros = if chars[0] == '1' { 0 } else { 1 };
        for i in 1..s.len() {
            if chars[i] == '0' {
                zeros += 1;
                dp[i] = dp[i - 1];
                continue;
            }
            if zeros > 0 {
                dp[i] = (dp[i - 1] + 1).max(zeros);
                continue;
            }
            dp[i] = dp[i - 1];
        }
        *dp.last().unwrap()
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22