Medium

题目描述

给你一个长度为 n 的 0 索引 二进制字符串 target。你有一个长度为 n 的二进制字符串 s，最初所有位都设为 0。你想要让 s 等于 target。

在一次操作中，你可以选择一个下标 i（0 <= i < n）并翻转在 闭区间 [i, n - 1] 内的所有位。翻转意味着 ‘0’ 变成 ‘1’，‘1’ 变成 ‘0’。

返回使 s 等于 target 所需的 最少 操作次数。

示例 1：

输入：target = "10111"
输出：3
解释：最初，s = "00000"。
选择下标 i = 2："00000" -> "00111"
选择下标 i = 0："00111" -> "11000"  
选择下标 i = 1："11000" -> "10111"
我们至少需要 3 次翻转操作来形成 target。

示例 2：

输入：target = "101"
输出：3
解释：最初，s = "000"。
选择下标 i = 0："000" -> "111"
选择下标 i = 1："111" -> "100"
选择下标 i = 2："100" -> "101"
我们至少需要 3 次翻转操作来形成 target。

示例 3：

输入：target = "00000"
输出：0
解释：我们不需要任何操作，因为初始的 s 已经等于 target。

提示：

  • n == target.length
  • 1 <= n <= 10^5
  • target[i] 是 ‘0’ 或 ‘1’

解题思路

这道题的关键观察是：我们从左到右遍历目标字符串，每当当前位与预期不符时，就需要进行一次翻转操作。

核心思路：

  1. 初始字符串 s 全为 ‘0’
  2. 从左到右遍历 target，维护一个当前状态（表示是否经过了奇数次翻转）
  3. 当当前位的目标值与当前状态不匹配时，需要从这个位置开始翻转到末尾
  4. 每次翻转会改变当前状态，同时操作数加1

算法详解：

  • 用变量 flipped 记录当前位置是否被翻转过（奇数次翻转为true）
  • 遍历 target 的每个字符：
    • 计算当前位置的实际值：如果 flipped 为true，则 ‘0’ 变 ‘1’，‘1’ 变 ‘0’
    • 如果实际值不等于目标值，则需要翻转，操作数加1，同时切换 flipped 状态

这是一个贪心算法，因为我们总是在最早可能的位置进行翻转操作，这样能保证最少的操作次数。

代码实现

class Solution {
public:
    int minFlips(string target) {
        int flips = 0;
        bool flipped = false;
        
        for (char c : target) {
            char current = flipped ? (c == '0' ? '1' : '0') : c;
            if (current != c) {
                flips++;
                flipped = !flipped;
            }
        }
        
        return flips;
    }
};

class Solution:
    def minFlips(self, target: str) -> int:
        flips = 0
        flipped = False
        
        for c in target:
            current = '1' if (c == '0' and flipped) or (c == '1' and not flipped) else '0'
            if current != c:
                flips += 1
                flipped = not flipped
                
        return flips

public class Solution {
    public int MinFlips(string target) {
        int flips = 0;
        bool flipped = false;
        
        foreach (char c in target) {
            char current = flipped ? (c == '0' ? '1' : '0') : c;
            if (current != c) {
                flips++;
                flipped = !flipped;
            }
        }
        
        return flips;
    }
}

var minFlips = function(target) {
    let flips = 0;
    let current = '0';
    
    for (let i = 0; i < target.length; i++) {
        if (target[i] !== current) {
            flips++;
            current = target[i];
        }
    }
    
    return flips;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历整个target字符串一次
空间复杂度O(1)只使用常数个额外变量

相关题目