当前位置：首页 > article >正文

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

article 2025/3/13 3:51:16

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

题目描述

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

输入输出示例

输入：

s = "0101"

输出：

解释：

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

解题思路分析

1. 暴力模拟法

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

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

优点：实现简单，逻辑清晰。
缺点：时间复杂度较高，最坏情况下为 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;
    }
}

代码逐行解析

方法一：暴力模拟法

初始化变量：
- seconds：记录总秒数。
- hasChanged：标记本次是否发生替换。
- chars：将字符串转换为字符数组以便修改。
循环处理：
- 使用 do-while 确保至少执行一次替换。
- 遍历字符数组，找到 "01" 并交换为 "10"。
- 每次交换后跳过下一个位置（i++），避免重复处理。
更新秒数：
- 若发生替换，seconds 加 1。