标签: 字符串
难度: Easy
给你一个仅由字符 '0' 和 '1' 组成的字符串 s 。一步操作中，你可以将任一 '0' 变成 '1' ，或者将 '1' 变成 '0' 。
交替字符串 定义为：如果字符串中不存在相邻两个字符相等的情况，那么该字符串就是交替字符串。例如，字符串 "010" 是交替字符串，而字符串 "0100" 不是。
返回使 s 变成 交替字符串 所需的 最少 操作数。
示例 1：
输入：s = "0100" 输出：1 解释：如果将最后一个字符变为 '1' ，s 就变成 "0101" ，即符合交替字符串定义。
示例 2：
输入：s = "10" 输出：0 解释：s 已经是交替字符串。
示例 3：
输入：s = "1111" 输出：2 解释：需要 2 步操作得到 "0101" 或 "1010" 。
提示：
1 <= s.length <= 104s[i] 是 '0' 或 '1'运行时间: 34 ms
内存: 0.0 MB
class Solution:
def minOperations(self, s: str) -> int:
op = sum(a != b for a, b in zip(s, cycle('01')))
return min(op, len(s) - op)
为了将字符串转换为交替字符串，我们可以考虑两种可能的交替模式：'0101...'和'1010...'。对于每个字符，我们检查它与这两种模式中的对应位置是否匹配。通过zip函数和cycle函数，我们可以将字符串s与无限循环的'01'模式对齐，然后计算不匹配的字符数量，即需要变更的次数。我们同时计算与'01'和'10'模式的不匹配数量，然后取两者中的较小值，因为我们总是可以选择变更次数较少的模式。
时间复杂度: O(n)
空间复杂度: O(1)
# 增加了注释的题解代码
class Solution:
def minOperations(self, s: str) -> int:
# 使用zip和cycle('01')来比较字符串s与'01'循环模式的每个字符
op = sum(a != b for a, b in zip(s, cycle('01')))
# 计算转换成'0101...'或'1010...'的最小变更次数
# op是与'01'模式的不匹配次数，len(s) - op是与'10'模式的不匹配次数
return min(op, len(s) - op)
在处理字符串s时，考虑两种模式'0101...'和'1010...'是因为它们是唯二的交替二进制字符串模式。一个正确的交替二进制字符串必须满足任何两个相邻字符都不相同，这正好对应了这两种模式。从任何位置开始，字符要么是'0'要么是'1'，因此必须考虑这两种可能的起始字符的模式，以便找到将给定字符串转换成真正交替字符串的最小操作数。
函数中`zip(s, cycle('01'))`通过组合Python中的`zip`函数和`itertools.cycle`函数来工作。`zip`函数用于将两个序列的相应元素配对生成一个元组的序列。而`cycle('01')`会无限循环地重复序列'01'。这样，无论字符串s的长度多长，`cycle('01')`都能提供足够的'0'和'1'来与之对应。因此，`zip(s, cycle('01'))`确保了不论s的长度如何，都可以将其每个字符与'01'模式的相应字符进行比较。
题解中的计算方法`len(s) - op`基于两种模式'0101...'和'1010...'之间的关系。对于任何给定的位置，如果一个字符与'0101...'模式不匹配，那么它必然与'1010...'模式匹配，反之亦然。因此，与'0101...'模式不匹配的字符数`op`加上与'1010...'模式不匹配的字符数应等于字符串s的总长度`len(s)`。这里的逻辑是，字符串中每个字符都必须参与这两种计数之一，因此两种不匹配的总和等于字符串的长度。从而，与'1010...'模式不匹配的次数可以简单地通过`len(s) - op`计算得出。
使用生成器表达式`sum(a != b for a, b in zip(s, cycle('01')))`来计算不匹配次数是因为这种方法在内存使用上更为高效。生成器表达式在迭代过程中逐个生成结果，并不需要存储整个结果列表，这对于处理大型数据集时尤为重要。此外，这种方法可以直接与`sum`函数结合，实现一步到位的计算，避免了额外的循环或列表操作，从而提升了代码的执行效率。总体而言，这种方法在处理大型字符串时，既节省内存又提高了计算速度。