leetcode
leetcode 1551 ~ 1600
生成交替二进制字符串的最少操作数

生成交替二进制字符串的最少操作数

难度:

标签:

题目描述

代码结果

运行时间: 34 ms, 内存: 0.0 MB


/*
 * 思路:
 * 1. 使用Java Stream进行字符的逐一检查和计数。
 * 2. 对于每种模式(pattern1和pattern2),统计需要改变的字符数。
 * 3. 最终返回两个计数的最小值。
 */

import java.util.stream.IntStream;

public class AlternatingStringStream {
    public int minOperations(String s) {
        int n = s.length();
        
        // 计算转换为pattern1所需的操作数
        long count1 = IntStream.range(0, n)
                .filter(i -> (i % 2 == 0 && s.charAt(i) != '0') || (i % 2 == 1 && s.charAt(i) != '1'))
                .count();

        // 计算转换为pattern2所需的操作数
        long count2 = IntStream.range(0, n)
                .filter(i -> (i % 2 == 0 && s.charAt(i) != '1') || (i % 2 == 1 && s.charAt(i) != '0'))
                .count();
        
        // 返回较小的操作数
        return (int) Math.min(count1, count2);
    }
}

解释

方法:

为了将字符串转换为交替字符串,我们可以考虑两种可能的交替模式:'0101...'和'1010...'。对于每个字符,我们检查它与这两种模式中的对应位置是否匹配。通过zip函数和cycle函数,我们可以将字符串s与无限循环的'01'模式对齐,然后计算不匹配的字符数量,即需要变更的次数。我们同时计算与'01'和'10'模式的不匹配数量,然后取两者中的较小值,因为我们总是可以选择变更次数较少的模式。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在处理字符串s时,为什么要考虑两种模式'0101...'和'1010...'?
在处理字符串s时,考虑两种模式'0101...'和'1010...'是因为它们是唯二的交替二进制字符串模式。一个正确的交替二进制字符串必须满足任何两个相邻字符都不相同,这正好对应了这两种模式。从任何位置开始,字符要么是'0'要么是'1',因此必须考虑这两种可能的起始字符的模式,以便找到将给定字符串转换成真正交替字符串的最小操作数。
🦆
函数中`zip(s, cycle('01'))`的工作机制是怎样的,它是如何确保与字符串s的每个字符正确对应的?
函数中`zip(s, cycle('01'))`通过组合Python中的`zip`函数和`itertools.cycle`函数来工作。`zip`函数用于将两个序列的相应元素配对生成一个元组的序列。而`cycle('01')`会无限循环地重复序列'01'。这样,无论字符串s的长度多长,`cycle('01')`都能提供足够的'0'和'1'来与之对应。因此,`zip(s, cycle('01'))`确保了不论s的长度如何,都可以将其每个字符与'01'模式的相应字符进行比较。
🦆
题解中提到,计算与'10'模式不匹配的次数使用了`len(s) - op`,这个计算方法的正确性和逻辑基础是什么?
题解中的计算方法`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(a != b for a, b in zip(s, cycle('01')))`来计算不匹配次数是因为这种方法在内存使用上更为高效。生成器表达式在迭代过程中逐个生成结果,并不需要存储整个结果列表,这对于处理大型数据集时尤为重要。此外,这种方法可以直接与`sum`函数结合,实现一步到位的计算,避免了额外的循环或列表操作,从而提升了代码的执行效率。总体而言,这种方法在处理大型字符串时,既节省内存又提高了计算速度。

相关问题