LeetCode 5760. 构成交替字符串需要的最小交换次数
原题链接
中等
作者:
YimingLi
,
2021-05-16 12:02:27
,
所有人可见
,
阅读 668
5760. Minimum Number of Swaps to Make the Binary String Alternating
算法 —— 分类讨论
0
和 1
的个数之差必须为 <=1
,不然无法排成题目要求的格式
- 最终的格式只能有两种
0101...
或者 1010...
- 分别计算这两种格式和原始字符串的最小交换次数即可,由于可以任意交换两个下标,交换次数就是相同下标不同数的个数除以二
时间复杂度
C++ 代码
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int cntNum(string &s, int x) {
int ans = 0;
for (auto ch : s) {
if (ch - '0' == x) ans++;
}
return ans;
}
int cntSwap(string &s, string &t) {
int n = s.length();
int ans = 0;
for (int i = 0; i < n; i++) {
if (s[i] != t[i]) {
ans++;
}
}
return ans / 2;
}
int minSwaps(string s) {
int n = s.length();
int c0 = cntNum(s, 0), c1 = cntNum(s, 1);
if (abs(c0 - c1) >= 2) return -1;
string s0, s1;
for (int i = 0; i < c0 && i < c1; i++) {
s0 += "01";
s1 += "10";
}
for (int i = min(c0, c1); i < c0; i++) {
s0 += "0";
}
for (int i = min(c0, c1); i < c1; i++) {
s1 += "1";
}
int ans = INT_MAX;
if (s0.length() == n) ans = min(ans, cntSwap(s, s0));
if (s1.length() == n) ans = min(ans, cntSwap(s, s1));
return ans;
}
};
原来零一数量差<= 1就行…之前没想通’‘100’’这种hhh 唉感觉要是下午考就好了
我看y总的 s与
'010101'
错位的0 和1的数量相等就有方案. (然后同理'101010...'
取个最小值就是该变的那个),也就是说不用判断s原串的01个数,只用判断和目标串相差的0, 1个数是否相同就行。(因为是交换)
嗯嗯,确实可以更简单一些
你这个也不错(等我稍后看看hh)