在本文中,我們將深入探討一個涉及C 字串操作的有趣問題。我們今天要研究的問題是如何「最小化需要刪除的0的數量,以最大化最長的連續1子字串的長度」。這個問題是磨練你在字串操作和動態規劃方面技能的絕佳方式。
給定一個二進位字串,任務是最小化需要刪除的 0 的數量,以便最大化最長 1 子字串的長度。
為了解決這個問題,我們可以使用滑動視窗的方法。我們將維護兩個指針,即左指針和右指針。最初,兩個指標都指向第一個元素。然後,我們將不斷將右指針向右移動。如果遇到了一個'0',我們會增加一個計數器。如果計數器變得大於允許的零移除數量,我們會將左指標向右移動,直到遇到一個'0'並減少計數器。
我們還將維護一個變數 maxLen 來儲存迄今為止我們看到的 1 子字串的最大長度。
這是解決問題的 C 程式碼 -
#include <iostream> #include <algorithm> #include <string> using namespace std; int maxSubstring(string str, int k) { int zeroCount = 0; int left = 0; int maxLen = 0; for (int right = 0; right < str.size(); right++) { if (str[right] == '0') { zeroCount++; } while (zeroCount > k) { if (str[left] == '0') { zeroCount--; } left++; } maxLen = max(maxLen, right - left + 1); } return maxLen; } int main() { string str = "110100110"; int k = 2; // number of zeros that can be removed int result = maxSubstring(str, k); cout << "The maximum length of the substring of 1s is: " << result << endl; return 0; }
The maximum length of the substring of 1s is: 5
讓我們拿二進位字串 "110100110",我們可以移除2個零。
當我們將這個字串和k的值傳遞給maxSubstring函數時,它會從左邊開始掃描。每當遇到一個'0'時,它就會增加zeroCount。當zeroCount超過k時,它開始將左指標向右移動,直到遇到一個'0'並減少zeroCount。
在這個過程中,它不斷更新maxLen,也就是1s的最大子字串長度。對於給定的字串,在最多移除2個零的情況下,1s的最大子字串長度為5,即在移除第二個和第三個'0'後的子字串"11111"。
因此,函數將傳回 5。
這個問題示範如何有效地使用滑動視窗技術來解決 C 中複雜的字串操作問題。對於理解和練習動態程式設計和字串處理技術來說,這是一個極好的問題。不斷練習此類問題以提高您的 C 編碼技能。
以上是最小化需要刪除的0的數量,以最大化最長連續1子字串的長度的詳細內容。更多資訊請關注PHP中文網其他相關文章!