資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究將字串連線成由 0 組成的子字串後跟由 1 組成的子字串所需的最小移除次數
問題“將字串連線成由 0 組成的子字串所需的最小移除次數”涉及字串操作的任務。輸入提供一個由 0 和 1 組成的字串，結果是一個整數，表示為了生成連續的 0 的子字串而必須刪除的 0 的最少數量。
換句話說，問題可以重新表述如下：給定一個由 0 和 1 組成的字串，必須刪除多少個 0 才能使剩餘的字串包含連續的 0 的子字串。
演算法
步驟 1：變數初始化
定義一個計數變數來記錄當前 0 序列的長度。
定義一個 max_count 變數來跟蹤迄今為止遇到的最長 0 序列。
將這兩個變數都設定為 0。
步驟 2：字串遍歷
使用迴圈遍歷字串中的每個字元。
步驟 3：零檢測
如果當前字元為零，則增加計數變數。
步驟 4：一檢測
如果當前字元為一，則將計數變數與 max_count 變數進行比較。
如果計數變數大於 max_count 變數，則將 max_count 變數設定為等於計數變數。
將計數變數重置為 0。
步驟 5：迴圈完成
重複此過程，直到處理完字串中的所有字元。
步驟 6：最小刪除計算
可以透過從字串的長度中減去 max_count 來計算將所有零移除以使剩餘的零不與任何零分隔所需的最小刪除次數。
步驟 7：結果輸出
將結果列印到控制檯。
遵循的方法
動態方法
迭代方法
方法 1：動態方法
動態規劃可用於有效地解決此問題。為了建立連續的 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' 時，我們必須獲得包含連續 0 的子字串的最接近 i 的索引 j。這可以透過從 i-1 迭代到 0 並檢視子字串 s[j...i] 是否包含連續的 0 來完成。如果找到索引 j，則 dp[i] = dp[j-1] + (i-j+1)，其中 dp[j-1] 表示必須從子字串 s[0...j-1] 中刪除的 0 的最小數量，而 (i-j+1) 是為了獲得連續的 0 的子字串 s[j...i] 而必須刪除的 1 的總數。如果找不到這樣的索引 j，則 dp[i] = dp[i-1]，因為我們無法將 s[i] 包含在連續的 0 的子字串中。
最後，為了從整個字串 s 中獲得連續的 0 的子字串，需要刪除的 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 子字串的長度之間的差值。
示例 2
程式碼是一個 C++ 程式，它計算將所有零從二進位制字串中刪除所需的最小消除次數，以使剩餘的零不與任何零分隔。min_deletions 函式將二進位制字串作為輸入，並使用迴圈遍歷字串中的每個字元。每次遇到零時，迴圈都會增加一個計數變數，並在遇到一時將其重置為零。計數變數的最大值儲存在 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;
}
輸出
Minimum deletion needed: 12
結論
確定所有 0 的子字串、計算連線每個 0 子字串的結果字串的長度以及確定最長 0 子字串的長度是解決給定問題的三個步驟。然後可以從所有 0 子字串的總和中減去最長 0 子字串的長度，以獲得所需的最小刪除次數。
我們用來獲得答案的方法簡單有效，並且線上性時間內執行，使其適用於大型輸入。但可以透過應用更復雜的方法（例如動態規劃）來進一步改進它。
68 次檢視
