資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學將二進位制字串排序為升序所需移除的最小字元數
在計算機科學中，字串操作是一個重要的主題，它涉及諸如連線、子串、反轉等操作。與字串操作相關的常見問題之一是從二進位制字串中刪除所有0。在本文中，我們將討論一種使用最小數量的非相鄰對翻轉來解決此問題的演算法。
問題陳述
給定一個二進位制字串，我們必須使用最少的非相鄰對翻轉來刪除字串中的所有0。翻轉定義為選擇兩個相鄰字元並交換它們。換句話說，我們需要找到將字串中所有0移動到字串末尾所需的最小翻轉次數。
方法
我們可以使用貪婪演算法來解決這個問題。我們可以從字串的左側開始，並跟蹤我們已將0翻轉到末尾的最後一個索引。對於遇到的每個0，我們將其與最後一個翻轉的0交換以將其移動到字串的末尾。如果我們遇到1，我們只需移動到下一個索引。
讓我們詳細瞭解一下演算法：
初始化兩個變數，“lastFlipped”和“flipCount”，分別為-1和0。
從左到右遍歷二進位制字串。
如果當前字元是'0'，則將其與索引“lastFlipped + 1”（即下一個需要交換的位置）處的字元交換，並將“lastFlipped”變數加1。
對於每次交換操作，將“flipCount”變數加1。
遍歷完成後，所有0都將位於字串的末尾，“flipCount”將包含刪除所有0所需的最小翻轉次數。
示例
以下是實現上述演算法的程式碼：
#include <stdio.h>
#include <string.h>
int minNonAdjacentPairFlips(char* s) {
int lastFlipped = -1;
int flipCount = 0;
for (int i = 0; i < strlen(s); i++) {
if (s[i] == '0') {
char temp = s[i];
s[i] = s[lastFlipped + 1];
s[lastFlipped + 1] = temp;
lastFlipped++;
flipCount++;
}
}
return flipCount;
}
int main() {
char s[] = "100101000";
printf("Binary String: %s\n", s);
printf("Minimum Non-adjacent Pair Flips: %d\n", minNonAdjacentPairFlips(s));
return 0;
}
輸出
Binary String: 100101000 Minimum Non-adjacent Pair Flips: 6
#include <iostream>
#include <string>
using namespace std;
int minNonAdjacentPairFlips(string s) {
int lastFlipped = -1;
int flipCount = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '0') {
swap(s[i], s[lastFlipped + 1]);
lastFlipped++;
flipCount++;
}
}
return flipCount;
}
int main() {
string s = "100101000";
cout << "Binary String: " << s << endl;
cout << "Minimum Non-adjacent Pair Flips: " << minNonAdjacentPairFlips(s) << endl;
return 0;
}
輸出
Binary String: 100101000 Minimum Non-adjacent Pair Flips: 6
public class Main {
public static int minNonAdjacentPairFlips(String s) {
int lastFlipped = -1;
int flipCount = 0;
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '0') {
char temp = chars[i];
chars[i] = chars[lastFlipped + 1];
chars[lastFlipped + 1] = temp;
lastFlipped++;
flipCount++;
}
}
return flipCount;
}
public static void main(String[] args) {
String s = "100101000";
System.out.println("Binary String: " + s);
System.out.println("Minimum Non-adjacent Pair Flips: " + minNonAdjacentPairFlips(s));
}
}
輸出
Binary String: 100101000 Minimum Non-adjacent Pair Flips: 6
def min_non_adjacent_pair_flips(s):
last_flipped = -1
flip_count = 0
for i in range(len(s)):
if s[i] == '0':
s_list = list(s)
s_list[i], s_list[last_flipped + 1] = s_list[last_flipped + 1], s_list[i]
s = ''.join(s_list)
last_flipped += 1
flip_count += 1
return flip_count
s = "100101000"
print("Binary String:", s)
print("Minimum Non-adjacent Pair Flips:", min_non_adjacent_pair_flips(s))
輸出
Binary String: 100101000 Minimum Non-adjacent Pair Flips: 6
測試用例解釋
讓我們以二進位制字串“100101000”為例。我們必須使用最少的非相鄰對翻轉來刪除此字串中的所有0。
最初，“lastFlipped”和“flipCount”分別設定為-1和0。
我們從左到右開始遍歷字串。
在索引1處，我們遇到一個'0'。我們將它與索引“lastFlipped + 1”（即索引0）處的字元交換，並將“lastFlipped”遞增到0。字串變為“010101000”。“flipCount”遞增到1。
在索引4處，我們遇到另一個'0'。我們將它與索引“lastFlipped + 1”（即索引1）處的字元交換，並將“lastFlipped”遞增到1。字串變為“011010000”。“flipCount”遞增到2。
在索引5處，我們遇到一個'1'。我們只需移動到下一個索引。
結論
在本文中，我們討論了一種使用最少的非相鄰對翻轉來從二進位制字串中刪除所有0的演算法。該演算法中使用的方法是貪婪演算法，這使得它高效且易於實現。
這個問題也可以使用動態規劃來解決，但是貪婪演算法提供了一個更簡單、更快的解決方案。該演算法的時間複雜度為O(n)，其中n是二進位制字串的長度。
總之，最小非相鄰對翻轉演算法是字串操作中一個有用的工具，可以應用於各種上下文中。
瀏覽量：152
