假设我们有一个长度为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