LeetCode 2380 二进制字符串重新安排顺序需要的时间

二进制字符串替换问题：计算消除 "01" 所需秒数

题目描述

给定一个二进制字符串 s，每秒将所有子字符串 "01" 同时替换为 "10"，直到字符串中不再存在 "01"。求完成这个过程所需的秒数。

输入输出示例

输入：

s = "0101"

输出：

2

解释：

• 第 1 秒："0101" → "1010"
• 第 2 秒："1010" → "1100"

解题思路分析

1. 暴力模拟法

最直观的思路是模拟替换过程：

1. 遍历字符串，找到所有 "01" 并替换为 "10"。
2. 每次替换后秒数加 1。
3. 重复上述步骤，直到字符串不再变化。

优点：实现简单，逻辑清晰。
缺点：时间复杂度较高，最坏情况下为 O (n²)。

2. 数学规律优化

观察发现：

• 每个 '0' 需要向右移动的次数等于其右侧连续 '1' 的数量。
• 总秒数等于所有 '0' 右侧连续 '1' 数量的最大值。

示例分析：

s = "0101"

• 第一个 '0' 右侧有 1 个 '1' → 需 1 秒。
• 第二个 '0' 右侧有 2 个 '1' → 需 2 秒。
• 总秒数为 2。

优点：时间复杂度 O (n)。
缺点：需要理解并推导出数学规律。

代码实现（Java）

方法一：暴力模拟法

class Solution {
    public int secondsToRemoveOccurrences(String s) {
        int seconds = 0;
        boolean hasChanged;
        char[] chars = s.toCharArray();

        do {
            hasChanged = false;
            for (int i = 0; i < chars.length - 1; i++) {
                if (chars[i] == '0' && chars[i + 1] == '1') {
                    // 交换 '0' 和 '1'
                    chars[i] = '1';
                    chars[i + 1] = '0';
                    hasChanged = true;
                    // 跳过下一个位置，避免重复处理
                    i++;
                }
            }
            if (hasChanged) {
                seconds++;
            }
        } while (hasChanged);

        return seconds;
    }
}

方法二：数学规律法

class Solution {
    public int secondsToRemoveOccurrences(String s) {
        int seconds = 0;
        int ones = 0; // 当前累积的连续 '1' 数量

        for (char c : s.toCharArray()) {
            if (c == '0') {
                // 当前 '0' 需要等待 ones 秒才能移动
                seconds = Math.max(seconds, ones);
            } else {
                ones++;
            }
        }
        return seconds;
    }
}

代码逐行解析

方法一：暴力模拟法

1. 初始化变量：

   • seconds：记录总秒数。
   • hasChanged：标记本次是否发生替换。
   • chars：将字符串转换为字符数组以便修改。

2. 循环处理：

   • 使用 do-while 确保至少执行一次替换。
   • 遍历字符数组，找到 "01" 并交换为 "10"。
   • 每次交换后跳过下一个位置（i++），避免重复处理。

3. 更新秒数：

   • 若发生替换，seconds 加 1。

方法二：数学规律法

1. 遍历字符：
   • 遇到 '0' 时，记录当前累积的连续 '1' 数量 ones，并更新最大秒数。
   • 遇到 '1' 时，累积 ones。

复杂度分析

常见问题解答

Q1：为什么暴力模拟法的时间复杂度是 O (n²)？

最坏情况下（如 "010101..."），每次只能处理一个 "01"，需要进行 O (n) 次遍历，每次遍历 O (n) 时间。

Q2：数学规律法的正确性如何证明？

• 每个 '0' 必须等待其右侧的所有 '1' 全部移动到左边后，才能移动。
• 例如，"011" 中的 '0' 需要 2 秒才能移动到最后。

Q3：为什么字符数组比字符串更高效？

字符串是不可变对象，每次修改会生成新实例。字符数组支持原地修改，减少内存开销。

测试用例

总结

本题通过两种方法实现：

1. 暴力模拟法：直观易懂，适合小规模输入。
2. 数学规律法：高效优化，适合大规模输入。

实际开发中需根据场景选择合适方法。掌握字符串处理技巧和数学规律推导能力，对解决类似问题至关重要。如果您有任何疑问或建议，欢迎在评论区交流！ 🚀