leetcode
leetcode 1651 ~ 1700
使二进制字符串字符交替的最少反转次数

使二进制字符串字符交替的最少反转次数

难度:

标签:

题目描述

代码结果

运行时间: 148 ms, 内存: 16.4 MB


/*
 * 思路:
 * 和Java的思路一致,但使用Java Stream API来实现
 * 使用IntStream来处理字符串索引,然后使用filter过滤不符合交替要求的字符
 */
import java.util.stream.IntStream;
public class Solution {
    public int minFlips(String s) {
        int n = s.length();
        long count0 = IntStream.range(0, n).filter(i -> s.charAt(i) != (i % 2 == 0 ? '0' : '1')).count();
        long count1 = IntStream.range(0, n).filter(i -> s.charAt(i) != (i % 2 == 0 ? '1' : '0')).count();
        return (int) Math.min(count0, count1);
    }
}

解释

方法:

首先,题解构造了一个理想的交替二进制字符串 `_s`,长度与 `s` 相同,开始以 '10' 交替。接着,题解通过遍历字符串 `s` 与 `_s` 对比,计算与 `_s` 匹配的字符数 `count`。如果 `s` 的长度 `n` 是偶数,直接返回 `min(count, n-count)`,因为可以通过 `count` 次反转得到 `_s` 或者通过 `n-count` 次反转得到 `_s` 的反向交替字符串。如果 `n` 是奇数,通过滑动窗口方式不断旋转字符串并计算最小反转次数,对于每个字符,根据它的值修改 `count`,并不断更新结果 `res` 为最小反转次数。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在构造理想的交替字符串 `_s` 时使用了 '10' 作为重复的基本单元,而不是 '01'?
选择 '10' 或 '01' 作为交替字符串的起始模式实际上是任意的,因为它们都可以表示完整的交替模式。选择 '10' 只是一个设计选择,而且无论选择哪一个,最终的算法逻辑和结果都应该是等价的。选择 '10' 可能是因为在实现时首先考虑了以 '1' 开始的序列,然后紧跟 '0',这不会影响最小反转次数的计算。
🦆
在偶数长度的字符串中,为什么直接使用 `min(count, n - count)` 可以得到最小的反转次数?
在偶数长度的字符串中,由于字符串长度正好可以完全匹配一次完整的交替模式(如 '10' 重复),这意味着理想的交替字符串和它的反向交替(如 '01' 开始)都是有效的目标字符串。`count` 表示与原始交替字符串匹配的字符数,而 `n - count` 表示与反向交替字符串匹配的字符数。因此,`min(count, n - count)` 表示将输入字符串转换为任一有效交替模式所需的最小反转次数。
🦆
对于奇数长度的字符串,旋转操作是如何在算法中体现的,它具体影响了哪些变量的状态?
对于奇数长度的字符串,算法通过模拟旋转来寻找最小反转次数。在代码中,旋转通过在循环中逐一考虑将字符串的首字符移动到尾部的情况来模拟。每次旋转,我们需要更新与理想交替字符串 `_s` 的匹配字符数 `count`。因为每次旋转实际上是将当前字符串的第一个字符移到最后,我们根据这个被移动字符是 '1' 还是 '0' 来相应地调整 `count`。通过这种方式,我们能够在每次模拟旋转后得到新的匹配数,并不断更新最小反转次数。
🦆
算法中对于更新 `count` 的逻辑 `count = n - (count - 1)` 和 `count = n - (count + 1)` 是如何得出的?这里的逻辑是否适用于所有情况?
这些更新公式用于正确地计算在将字符串首字符旋转到末尾后,与理想交替字符串匹配的字符数。当旋转字符是 '1' 时,我们使用 `count = n - (count - 1)`,这是因为原来的 `count` 包括了这个 '1',旋转后它不再在首位因此要减去1,然后求与非匹配字符的总数(`n - count`)。相反,如果是 '0',我们使用 `count = n - (count + 1)`。这些操作都是为了保持 `count` 变量准确反映当前字符串与理想交替字符串 `_s` 的匹配程度。这种方法适用于所有字符旋转的情况,确保我们可以正确地更新匹配数。

相关问题