构成交替字符串需要的最小交换次数
难度:
标签:
题目描述
代码结果
运行时间: 20 ms, 内存: 16.0 MB
/*
思路:
1. 使用Java Stream来简化字符统计和交换次数计算。
2. 对字符串中的每个字符按其在奇偶位置上的出现情况进行计数。
3. 分别计算出将字符串变为'010101...'和'101010...'所需的交换次数,取最小值。
*/
import java.util.stream.IntStream;
public class Solution {
public int minSwaps(String s) {
int n = s.length();
long count0 = s.chars().filter(c -> c == '0').count();
long count1 = n - count0;
if (Math.abs(count0 - count1) > 1) return -1;
long swap1 = IntStream.range(0, n)
.filter(i -> s.charAt(i) != (i % 2 == 0 ? '0' : '1'))
.count();
long swap2 = IntStream.range(0, n)
.filter(i -> s.charAt(i) != (i % 2 == 0 ? '1' : '0'))
.count();
if (count0 > count1) return (int) swap1 / 2;
if (count1 > count0) return (int) swap2 / 2;
return (int) Math.min(swap1, swap2) / 2;
}
}
解释
方法:
为了将二进制字符串转化为交替字符串,我们可以考虑两种情况:一种是'1'在奇数位置,'0'在偶数位置;另一种是'1'在偶数位置,'0'在奇数位置。首先统计字符串中在奇数位置和偶数位置的'0'和'1'的数量。然后,根据这些统计值来判断每种情况下需要进行的交换次数。如果某种情况下的'1'的数量与对应位置的'0'的数量不匹配,则该情形不可能。如果两种情况都不可能,则返回-1。如果两种情况都可能,则选择交换次数较少的一种。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
题解中提到了两种情况,但未明确解释为什么只有这两种情况是可能的,其他的情况比如'1'和'0'都在偶数位置或奇数位置是否考虑了?
▷🦆
如何确定当even_1不等于odd_0时,第一种情况就不可能实现?是否有具体的逻辑或数学推导支持这一点?
▷🦆
在计算两种情况的交换次数时,为什么可以直接使用even_1或odd_1作为交换次数,而不需要进一步的计算或验证?
▷🦆
当两种情况都可能时,选择交换次数较少的一种作为答案,这种方法是否总是有效?存在哪些潜在的风险或例外情况?
▷