資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中將所有1移到左邊，所有0移到右邊的最小翻轉次數
問題陳述
給定一個二進位制字串，我們可以翻轉左邊部分的所有1和右邊部分的所有0。任務是計算使所有1都在左邊，所有0都在右邊的最小翻轉次數。
示例
給定的二進位制字串是0010101。在這個字串中，有3個1和4個0。我們必須翻轉高亮的4位，以便所有1都在左邊，所有0都在右邊，如下所示：
0010101
翻轉後字串將變成：
1110000
演算法
- 從左到右遍歷字串，計算將所有0轉換為1所需的翻轉次數。
- 從右到左遍歷字串，計算將所有1轉換為0所需的翻轉次數。
- 遍歷所有位之間的位置，找到(0翻轉次數 + 1翻轉次數)的最小值。
示例
#include <iostream>
#include <string>
#include <climits>
using namespace std;
int minFlips(string binaryString) {
int n = binaryString.length();
int flipCnt, zeroFlips[n], oneFlips[n];
flipCnt = 0;
for (int i = 0; i < n; ++i) {
if (binaryString[i] == '0') {
++flipCnt;
}
zeroFlips[i] = flipCnt;
}
flipCnt = 0;
for (int i = n - 1; i >= 0; --i) {
if (binaryString[i] == '1') {
++flipCnt;
}
oneFlips[i] = flipCnt;
}
int minFlips = INT_MAX;
for (int i = 1; i < n; ++i) {
int sum = zeroFlips[i - 1] + oneFlips[i]; if (sum < minFlips) {
minFlips = sum;
}
}
return minFlips;
}
int main() {
string binaryString = "0010101";
cout << "Minimum flips: " << minFlips(binaryString) <<
endl;
return 0;
}輸出
編譯並執行上述程式後，將生成以下輸出：
Minimum flips: 4
更新於：2019年11月22日
311 次瀏覽
廣告