最少的后缀翻转次数

标签: 贪心 字符串

难度: 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 次翻转。

示例 2：

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

示例 3：

输入：target = "00000"
输出：0
解释：由于 s 已经等于目标，所以不需要任何操作

提示：

  • n == target.length
  • 1 <= n <= 105
  • target[i] 为 '0' 或 '1'

Submission

运行时间: 40 ms

内存: 16.5 MB

class Solution:
    def minFlips(self, target: str) -> int:
        out = 0
        pre = '0'
        out = 0

        for char in target:
            if char != pre:
                out += 1
            pre = char

        return out

Explain

这个题解的思路是基于观察字符串s（初始全为'0'）与目标字符串target之间的不同。算法遍历target中的每个字符，比较当前字符和前一个字符是否相同。当字符从'0'变为'1'或从'1'变为'0'时，表明需要进行一次翻转操作，以确保从当前位置到字符串末尾的所有位都进行了翻转。这样，算法能够确保每当遇到与前一位不同的字符时，都进行翻转，从而最小化翻转的次数。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minFlips(self, target: str) -> int:
        out = 0  # 初始化翻转次数为0
        pre = '0'  # 前一个字符初始化为'0'（因为字符串s初始全为'0'）
        for char in target:  # 遍历目标字符串中的每个字符
            if char != pre:  # 当前字符如果与前一个字符不同
                out += 1  # 需要进行一次翻转
            pre = char  # 更新前一个字符
        return out  # 返回总的翻转次数

Explore

在算法中使用字符'0'作为初始前一个字符是因为问题设定中字符串s初始全为'0'。这样做的目的是为了在第一个字符就能检测到是否需要进行翻转。如果使用target的第一个字符作为初始值，那么我们会错过在第一个字符处可能需要的翻转操作，因为初始的比较总是会显示相等（因为它们是相同的字符）。使用'0'可以确保第一个字符如果是'1'，算法会正确计算出需要进行一次翻转，以将开始的'0'变为'1'。

是的，算法中的翻转操作意味着每次翻转都是从当前位置i到字符串末尾n-1。这种策略可以确保最小化操作次数，因为它直接翻转了所有后续的字符，以匹配目标字符串中当前字符的需要。通过这种方式，每次字符从'0'变为'1'或从'1'变为'0'时，只需进行一次翻转，就可以改变所有后续字符的状态。这避免了对同一段字符的多次翻转，从而最小化了翻转次数。

在解决方案中，如果target全部为'1'，则算法会在初始时检测到从'0'到'1'的变化，因此会进行一次翻转，输出为1。如果target全部为'0'，由于初始字符串s也全为'0'，算法中不会检测到任何需要翻转的情况，因此输出为0。这样的输出完全符合题目要求，即最小化翻转次数以匹配目标字符串。

在我的算法中，没有特别为特定长度的字符串设计特殊的处理方式，因为算法本身就是基于逐字符比较和更新的方式运行。无论target字符串的长度是1、2还是更长，算法都按照同样的逻辑执行：检查每个字符与前一个字符是否不同，并在必要时增加翻转计数。因此，算法能够有效地处理包括非常短的字符串在内的所有边界条件。