排序二進位字串所需刪除的最小字元數，以使其按升序排列

在電腦科學中，字串操作是一個重要的主題，涉及拼接、子字串、反轉等操作。與字串操作相關的一個常見問題是從二進位字串中移除所有的0。在本文中，我們將討論一種使用最少數量的非相鄰對翻轉來解決這個問題的演算法。

問題陳述

給定一個二進位字串，我們必須使用最少次數的非相鄰對翻轉來刪除字串中的所有 0。翻轉被定義為選擇兩個相鄰的字元並交換它們。換句話說，我們需要找到使字串中全0到字串末尾所需的最少翻轉次數。

方法

我們可以使用貪心演算法來解決這個問題。我們可以從字串的左邊開始，並追蹤我們翻轉0到末尾的最後一個索引。對於每個遇到的0，我們將其與最後一個翻轉的0交換位置，將其移動到字串的末尾。如果遇到1，我們只需移動到下一個索引。

讓我們詳細看一下演算法 -

• 將兩個變數「lastFlipped」和「flipCount」分別初始化為 -1 和 0。

• 從左到右遍歷二進位字串。

• 如果目前字元為“0”，則將其與索引“lastFlipped 1”處的字元交換，並遞增“lastFlipped”變數。

• 為每個交換操作增加「flipCount」變數。

• 遍歷完成後，所有 0 將位於字串末尾，「flipCount」將包含刪除所有 0 所需的最小翻轉次數。

範例

這是用於實作上述演算法的C 程式碼 -

#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

測試案例的解釋

我們以二進位字串「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 的演算法。該演算法使用的方法是貪婪的，這使得它高效且易於實現。我們還提供了用於實現該演算法的 C 程式碼以及範例測試用例。

這個問題也可以使用動態規劃來解決，但貪心演算法提供了一個更簡單和更快的解決方案。此演算法的時間複雜度為O(n)，其中n是二進位字串的長度。

總之，最小非相鄰對翻轉演算法是字串操作中的一個有用工具，可以應用於各種情境。

以上是排序二進位字串所需刪除的最小字元數，以使其按升序排列的詳細內容。更多資訊請關注PHP中文網其他相關文章！