leetcode
leetcode 1651 ~ 1700
构成交替字符串需要的最小交换次数

构成交替字符串需要的最小交换次数

难度:

标签:

题目描述

代码结果

运行时间: 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'都在偶数位置或奇数位置是否考虑了?
交替字符串的定义是相邻的字符必须不同。因此,只有两种模式满足这个条件:'1'在奇数位置,'0'在偶数位置;或者'1'在偶数位置,'0'在奇数位置。如果'1'和'0'都在偶数位置或者都在奇数位置,那么相邻的字符会相同,这与交替字符串的定义不符,因此这些情况不需要考虑。
🦆
如何确定当even_1不等于odd_0时,第一种情况就不可能实现?是否有具体的逻辑或数学推导支持这一点?
对于第一种情况,'1'在奇数位置,'0'在偶数位置,奇数位置的'1'数量应该等于偶数位置的'0'数量,否则无法通过交换得到交替字符串。例如,如果奇数位置的'1'数量多于偶数位置的'0'数量,那么即使通过最优交换,也会有多余的'1'无法找到对应的'0'进行交换,因此这种情况不可能实现。
🦆
在计算两种情况的交换次数时,为什么可以直接使用even_1或odd_1作为交换次数,而不需要进一步的计算或验证?
在考虑交换次数时,我们关注的是将错误位置的字符移动到正确的位置。在第一种情况('1'在奇数位置,'0'在偶数位置),需要交换的次数等于错误位置上'1'的数量(even_1),因为每个这样的'1'都需要与一个错误位置上的'0'交换。同理,在第二种情况('1'在偶数位置,'0'在奇数位置),需要交换的次数等于错误位置上'1'的数量(odd_1)。因此,直接使用even_1或odd_1作为交换次数是有效的。
🦆
当两种情况都可能时,选择交换次数较少的一种作为答案,这种方法是否总是有效?存在哪些潜在的风险或例外情况?
选择交换次数较少的策略通常是有效的,因为这直接减少了操作的复杂度和可能的错误。然而,潜在的风险包括未考虑到特殊情况,比如输入字符串几乎已经是交替字符串,这时更复杂的逻辑可能会导致不必要的交换。此外,如果输入字符串长度非常大,那么即使是最小的交换次数也可能导致实际操作上的不可行。总的来说,在大多数情况下,选择交换次数较少的情况是合理和有效的。

相关问题