使字串成為由一串0後面跟著一串1組成的最小移除次數-C++-PHP中文網

使字串成為由一串0後面跟著一串1組成的最小移除次數

王林

發布： 2023-09-07 22:57:02

轉載

589 人瀏覽過

使字串成為由一串0後面跟著一串1組成的最小移除次數

問題「進行 0 子字串的字串連接的最小刪除量」涉及操作字串的工作。提供 0 和 1 的字串作為輸入，結果是一個整數，反映為了產生連續 0 的子字串而必須消除的 0 的最小數量。

換句話說，問題可以重新表述為：給定一個由0和1組成的字串，為了讓剩下的字串中包含一段連續的0，需要消除多少個0。

演算法

第一步：變數初始化

定義一個計數變數來記錄目前零序列的長度。
定義一個 max_count 變數來追蹤迄今為止遇到的最長的零序列。
將兩個變數都設為0。

第二步：字串遍歷

使用循環遍歷字串中的每個字元。

第三步：零偵測

如果目前字元為零，則增加計數變數。

第 4 步：一次偵測

如果目前字元是 1，則將 count 變數與 max_count 變數進行比較。
如果計數變數高於 max_count 變量，則將 max_count 變數設定為等於計數變數。
將計數變數重設為0。

第 5 步：循環完成

重複這個過程，直到字串中的所有字元都被處理完。

步驟6：最小刪除計算

刪除所有零以使剩餘的不被任何零分隔所需的最小刪除次數可以透過從字串長度中減去 max_count 來計算。

第7步：結果輸出

將結果印到控制台。

遵循的方法

動態方法
迭代方法

方法一：動態方法

動態規劃可以用來有效率地解決這個問題。為了創建連續0的子字串，我們可以創建一個數組dp[]，其中dp[i]表示從子字串s[0...i]中需要消除的最小數量的0。從空子字串中消除的最小數量的0是0，因此我們可以將dp[0]初始化為0。

然後，我們可以迭代字串s並將dp[i]更新為−

如果 s[i] 為“0”，則 dp[i] = dp[i-1]，因為我們可以將 s[i] 包含在連續 0 的子字串中或將其刪除。
當 s[i] 為「1」時，我們必須得到距離 i 最接近的索引 j，其中包含連續 0 的子字串。這可以透過從 i-1 迭代到 0 並查看子字串 s[j...i] 是否包含連續的 0 來完成。如果找到索引j，則dp[i] = dp[j-1] (i-j 1)，其中dp[j-1] 表示必須從子字串s[ 中消除的0 的最小數量0...j-1 ]和(i-j 1)是為了得到連續0的子字串s[j...i]而必須消除的1的總數。如果沒有發現這樣的索引 j，則 dp[i] = dp[i-1]，因為我們不能將 s[i] 包含在連續 0 的子字串中。

最後，為了獲得連續 0 的子字串，需要從整個字串 s 中刪除的 0 的最小數量由 dp[n-1] 給出，其中 n 是字串 s 的長度。

範例 1

下面的程式使用我們上面討論的方法，首先從標準輸入讀取輸入字串，然後識別所有 0 的子字串。然後計算最長的 0 子字串的長度以及透過連接每個 0 子字串產生的字串的長度。為了確定所需消除的最少次數，它最終從所有 0 子字串的總和中減去最長 0 子字串的長度，並將結果顯示到標準輸出。

#include <bits/stdc++.h>
using namespace std;

int main() {
   string s = "100100011000110"; // constant input string

   vector<pair<int, int>> substrings; // vector to store start and end indices of each substring of 0s

   int start = -1;
   for (int i = 0; i < s.length(); i++) {
      if (s[i] == '0') {
         if (start == -1) {
         start = i;
         }
      } else {
         if (start != -1) {
         substrings.push_back(make_pair(start, i - 1));
         start = -1;
         }
      }
   }
   if (start != -1) {
      substrings.push_back(make_pair(start, s.length() - 1));
   }

   int totalLength = 0;
   for (auto& p : substrings) {
      totalLength += p.second - p.first + 1;
   }

   int maxLength = 0;
   for (auto& p : substrings) {
      int len = p.second - p.first + 1;
      if (len > maxLength) {
         maxLength = len;
      }
   }

   int removals = totalLength - maxLength;
   cout << "Input string: " << s << endl;
   cout << "Minimum removals: " << removals << endl;

   return 0;
}

登入後複製

輸出

Input string: 100100011000110
Minimum removals: 6

登入後複製

方法2：迭代方法

這種方法使用一種直接的迭代方法，逐個字元地遍歷給定的字串，同時更新兩個變數count和max_count的值。此方法根據目前字元是0還是1來更新count和max_count變數的值。然後，它提供了max_count和最長的0子字串的長度之間的差異。

Example 2

的中文翻譯為：

範例2

程式碼是一個 C 軟體，它計算從二進位字串中刪除所有零所需的最小消除次數，以便其餘的不被任何零分隔。 min_deletions 函數將二進位字串作為輸入，並使用循環來遍歷字串中的每個字元。此循環每次遇到零時都會增加計數變量，並在遇到一時將其重置為零。 count變數的最大值保存在max_count中，最後從max_count中減去字串的長度以獲得所需的最小刪除次數。然後將結果顯示給使用者。

#include <iostream> 
#include <string> 
using namespace std; 
 
int min_deletions(string str) { 
   int count = 0, max_count = 0; 
   for (char c : str) { 
      if (c == '0') { 
         count++; 
      } else { 
         max_count = max(max_count, count); 
         count = 0; 
      } 
   } 
    return str.length() - max_count; 
} 
 
int main() { 
   string str = "100010011000110"; 
   int deletions = min_deletions(str); 
   cout << "Minimum deletions needed: " << deletions << endl; 
   return 0; 
}

登入後複製