資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究最小化需要移除的 0 的數量，以最大化最長 1 子串的長度
在本文中，我們將深入探討一個涉及字串操作的有趣問題。我們今天要研究的問題是如何“最小化需要移除的 0 的數量，以最大化最長 1 子串的長度”。這個問題是磨練你在各種程式語言中字串操作和動態規劃技能的好方法。
問題陳述
給定一個二進位制字串，任務是最小化需要移除的 0 的數量，以便最大化最長 1 子串的長度。
解決方案方法
為了解決這個問題，我們可以使用滑動視窗方法。我們將維護兩個指標，left 和 right。最初，兩個指標都指向第一個元素。然後，我們將繼續向右移動 right 指標。如果我們遇到一個 '0'，我們將增加一個計數器。如果計數器變得大於允許的零移除次數，我們將向右移動 left 指標，直到我們遇到一個 '0' 並遞減計數器。
我們還將維護一個變數 maxLen 來儲存到目前為止我們看到的 1 子串的最大長度。
示例
以下是解決該問題的程式：
#include <stdio.h>
#include <string.h>
int maxSubstring(char str[], int k) {
int zeroCount = 0;
int left = 0;
int maxLen = 0;
int strLen = strlen(str);
for (int right = 0; right < strLen; right++) {
if (str[right] == '0') {
zeroCount++;
}
while (zeroCount > k) {
if (str[left] == '0') {
zeroCount--;
}
left++;
}
maxLen = (maxLen > right - left + 1) ? maxLen : right - left + 1;
}
return maxLen;
}
int main() {
char str[] = "110100110";
int k = 2; // number of zeros that can be removed
int result = maxSubstring(str, k);
printf("The maximum length of the substring of 1s is: %d\n", result);
return 0;
}
輸出
The maximum length of the substring of 1s is: 5
#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
public class MaxSubstring {
public static int maxSubstring(String str, int k) {
int zeroCount = 0;
int left = 0;
int maxLen = 0; // Stores the maximum length of the substring of 1s
for (int right = 0; right < str.length(); right++) {
if (str.charAt(right) == '0') {
zeroCount++;
}
while (zeroCount > k) {
if (str.charAt(left) == '0') {
zeroCount--;
}
left++;
}
// Update maxLen to store the maximum length of the substring of 1s found so far
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen; // Return the maximum length of the substring of 1s
}
public static void main(String[] args) {
String str = "110100110";
int k = 2;
int result = maxSubstring(str, k); // Call the maxSubstring function
System.out.println("The maximum length of the substring of 1s is: " + result);
}
}
輸出
The maximum length of the substring of 1s is: 5
def maxSubstring(s, k):
zeroCount = 0
left = 0
maxLen = 0
for right in range(len(s)):
if s[right] == '0':
zeroCount += 1
while zeroCount > k:
if s[left] == '0':
zeroCount -= 1
left += 1
# Update maxLen to store the maximum length of the substring of 1s found so far
maxLen = max(maxLen, right - left + 1)
return maxLen
if __name__ == "__main__":
s = "110100110"
k = 2
result = maxSubstring(s, k) # Call the maxSubstring function
print("The maximum length of the substring of 1s is:", result)
輸出
The maximum length of the substring of 1s is: 5
帶測試用例的解釋
讓我們取二進位制字串 "110100110"，並且允許我們移除 2 個零。
當我們將此字串和 k 的值傳遞給 maxSubstring 函式時，它從左側開始掃描。每次遇到 '0' 時，它都會遞增 zeroCount。當 zeroCount 超過 k 時，它開始向右移動 left 指標，直到遇到 '0' 並遞減 zeroCount。
在此過程中，它會不斷更新 maxLen，它是 1 子串的最大長度。對於給定的字串，在移除最多 2 個零後，1 子串的最大長度為 5，即在移除第二個和第三個 '0' 後的子串 "11111"。
因此，函式將返回 5。
結論
這個問題演示瞭如何有效地使用滑動視窗技術來解決複雜的字串操作問題。對於理解和練習動態規劃和字串處理技術來說，這是一個極好的問題。繼續練習此類問題以提高你的編碼技能。
更新於： 2023年10月23日
98 次瀏覽
廣告