---

1529. 最少的后缀翻转次数

• 标签：贪心、字符串
• 难度：中等

题目链接

• 1529. 最少的后缀翻转次数 - 力扣

题目大意

描述：给定一个目标二进制字符串 $target$。初始全 $0$ 字符串。每次操作可以选择一个下标 $i$，将从 $i$ 到末尾的所有字符翻转（$0 \to 1$，$1 \to 0$）。

要求：返回将初始字符串变为 $target$ 所需的最少操作次数。

说明：

• $1 \le target.length \le 10^5$。
• $target$ 只包含 '0' 和 '1'。

示例：

• 示例 1：

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

• 示例 2：

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

解题思路

思路 1：贪心

1. 核心思想

从左到右遍历 $target$，每次遇到与前一个字符不同的位置，就需要一次翻转操作。

因为翻转后缀的操作会改变当前位置及之后所有位置的状态，所以翻转的次数可以通过当前位置的当前状态与目标状态的差异来判断。

等价地：维护一个翻转次数 $flips$。对于位置 $i$，如果 $(flips \% 2 == 1)$，说明该位置已被翻转了一次（即当前字符已被翻转 $flips$ 次）。如果经过 $flips$ 次翻转后，当前字符与 $target[i]$ 仍不同，则再从 $i$ 开始做一次后缀翻转。

2. 具体步骤

第 1 步：初始化 $flips = 0$。

第 2 步：遍历 $target$：

• 当前字符经过 $flips$ 次翻转后的状态为 chr((ord(target[i]) - ord('0') + flips) % 2 + ord('0'))。
• 但这种计算麻烦。简便方法：维护一个变量 $flipped$，表示当前字符是否被翻转。
• 如果 ($target[i] == '0'$ 且 $flipped$) 或 ($target[i] == '1'$ 且 $!flipped$)，说明当前状态不对，需要翻转，$flips += 1$，$flipped = !flipped$。

更简洁的代码：

flips = 0
for ch in target:
    if (int(ch) + flips) % 2 == 0:
        pass  # 当前状态已匹配
    else:
        flips += 1

等等，初始字符串全 $0$，状态为 $0$。每次翻转后缀会切换从 $i$ 开始所有位置的状态。
实际上简化：当前字符为 $target[i]$，初始为 $0$。$flips$ 为已经做的翻转操作次数。经过 $flips$ 次翻转后，当前字符为 $flips \% 2$。如果 $flips \% 2 \neq target[i]$，需要再做一次翻转 -> $flips++$。

3. 举例说明

以 $target = "10111"$ 为例：

• $i=0$：$target[0]='1'$，当前 $cur=0$。$0 \neq 1$，翻转，$flips=1$。
• $i=1$：$target[1]='0'$，$flips\%2=1$，当前 $cur=1$。$1 \neq 0$，翻转，$flips=2$。
• $i=2$：$target[2]='1'$，$flips\%2=0$，当前 $cur=0$。$0 \neq 1$，翻转，$flips=3$。
• $i=3$：$target[3]='1'$，$flips\%2=1$，当前 $cur=1$。$1 == 1$，不翻转。
• $i=4$：$target[4]='1'$，$flips\%2=1$，当前 $cur=1$。$1 == 1$，不翻转。

$flips = 3$。

思路 1：代码

class Solution:
    def minFlips(self, target: str) -> int:
        flips = 0
        for ch in target:
            cur = flips % 2  # 当前字符经过 flips 次翻转后的状态
            if cur != int(ch):
                flips += 1
        return flips

思路 1：复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。