Data Structure
Networking
RDBMS
Operating System
Java
MS Excel
iOS
HTML
CSS
Android
Python
C Programming
C++
C#
MongoDB
MySQL
Javascript
PHP
Physics
Chemistry
Biology
Mathematics
English
Economics
Psychology
Social Studies
Fashion Studies
Legal StudiesC++ 中串聯二進位制字串的最大連續0
假設我們有一個長度為 n 的二進位制字串，給定另一個值 k。我們必須將二進位制字串連線 k 次。然後，我們必須在連線的字串中找到連續 0 的最大數量。假設二進位制字串為“0010010”，k = 2，那麼將字串連線 k 次後，它將變為“00100100010010”。因此，連續 0 的最大數量為 3。
方法很簡單。如果數字全部為 0，那麼答案將為 n * k。如果字串包含 1，則結果將是字串子字串的最大長度，包含所有 0，或者僅包含 0 的字串的最大字首的長度與僅包含 0 的字串的最大字尾的長度之和。
演算法
max_zero_count (str, n, k) −
Begin total := 0 len := 0 for i in range 0 to n, do if str[i] = 0, then increase len else len := 0 total := maximum of total and len done if total = n, then return n * k prefix := length of maximal prefix with only 0 suffix:= length of maximal suffix with only 0 if k > 1, then total := max of total, and (prefix + suffix) return total End
示例
#include <iostream>
using namespace std;
int max_length_substring(string str, int n, int k) {
int total_len = 0;
int len = 0;
for (int i = 0; i < n; ++i) {
if (str[i] == '0') //if the current character is 0, increase len
len++;
else
len = 0;
total_len = max(total_len, len);
}
if (total_len == n) //if the whole string has 0 only
return n * k;
int prefix = 0, suffix = 0;
for (int i = 0; str[i] == '0'; ++i, ++prefix) //find length of maximal prefix with only 0;
for (int i = n - 1; str[i] == '0'; --i, ++suffix) //find length of maximal suffix with only 0;
if (k > 1)
total_len = max(total_len, prefix + suffix);
return total_len;
}
int main() {
int k = 3;
string str = "0010010";
int res = max_length_substring(str, str.length(), k);
cout << "Maximum length of 0s: " << res;
}輸出
Maximum length of 0s: 3
更新時間： 17-10-2019
366 次瀏覽
廣告