生成交替二进制字符串的最少操作数
难度:
标签:
题目描述
代码结果
运行时间: 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...'?
▷🦆
函数中`zip(s, cycle('01'))`的工作机制是怎样的,它是如何确保与字符串s的每个字符正确对应的?
▷🦆
题解中提到,计算与'10'模式不匹配的次数使用了`len(s) - op`,这个计算方法的正确性和逻辑基础是什么?
▷🦆
为什么在计算不匹配次数时使用了生成器表达式`sum(a != b for a, b in zip(s, cycle('01')))`?这种方法的效率如何?
▷