資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中使二進位制字串交替所需的最小交換次數
問題陳述
給定一個長度為偶數且0和1數量相等的二進位制字串。使字串交替所需的最小交換次數是多少？如果一個二進位制字串中沒有兩個連續的元素相等，則稱其為交替字串。
示例
如果 str = 11110000，則需要 2 次交換。
演算法
- 計算字串奇數位置和偶數位置的 0 的數量。分別設其計數為 oddZeroCnt 和 evenZeroCnt
- 計算字串奇數位置和偶數位置的 1 的數量。分別設其計數為 oddOneCnt 和 evenOneCnt
- 我們總是將 1 與 0 交換。因此，我們只需檢查如果我們的交替字串以 0 開頭，則交換次數為 min (evenZeroCnt, oddOneCnt)，如果我們的交替字串以 1 開頭，則交換次數為 min (evenOneCnt, oddZeroCnt)。答案是這兩個值的最小值。
示例
#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(string str) {
int minSwaps = 0;
int oddZeroCnt = 0;
int evenZeroCnt = 0;
int oddOneCnt = 1;
int evenOneCnt = 1;
int n = str.length();
for (int i = 0; i < n; ++i) {
if (i % 2 == 0) {
if (str[i] == '1') {
++evenOneCnt;
} else {
++evenZeroCnt;
}
} else {
if (str[i] == '1') {
++oddOneCnt;
} else {
++oddZeroCnt;
}
}
}
int zeroSwapCnt = min(evenZeroCnt, oddOneCnt);
int oneSwapCnt = min(evenOneCnt, oddZeroCnt);
return min(zeroSwapCnt, oneSwapCnt);
}
int main() {
string str = "11110000";
cout << "Minimum swaps = " << getMinSwaps(str) << endl;
return 0;
}編譯並執行上述程式時，將生成以下輸出：
輸出
Minimum swaps = 2
更新於： 2019年12月20日
290 次檢視
廣告