LeetCode 5760. 和Y总不同的思路:构成交替字符串需要的最小交换次数
原题链接
中等
作者:
0weili
,
2021-05-16 15:18:21
,
所有人可见
,
阅读 325
算法1
(统计) $O(n)$
- 如果s长度是偶数,统计偶数位的0,返回min(cnt,n/2-cnt),代表需要修复的错位的最小数量
- 如果长度是奇数,就不能直接这样做了,因为此时偶数位比奇数位多一个,偶数位只能够填入0和1中数量更多的一方
比如1比0多,那偶数位只能填1,那么统计偶数位上0的数量就是错位的数量
时间复杂度
参考文献
C++ 代码
class Solution {
public:
int minSwaps(string s) {
int cnt0 = 0, cnt1 = 0, n = s.size();
for(auto c : s) c - '0' ? cnt1++ : cnt0++;
if(n&1) {
if(abs(cnt0 - cnt1) != 1) return -1;
} else if(cnt0 != cnt1) return -1;
int cnt = 0;
auto c = cnt0 > cnt1 ? '1' : '0';
for(int i = 0; i < n; i+=2) if(s[i]==c) cnt++;
return (n&1)?cnt:min(cnt,n/2-cnt);
}
};