C ++中二进制字符串中零和一的最大差
给定任务是从给定的二进制字符串中找到一个子字符串,然后找到零和一之间的最大差。
现在让我们使用示例了解我们必须做的事情-
输入值
str = “100100110”
输出结果
2
说明
在位置1到5(“00100”)的子数组中,零和一之间的差=4–1=3,这是可以找到的最大值。
输入值
str = “00000”
输出结果
5
在以下程序中使用的方法如下
在main()函数中,创建一个字符串str来存储二进制字符串。还初始化一个变量intsize以存储字符串的大小,并将它们都传递给Max()函数。
在Max()函数中,首先通过调用One()函数检查所有元素是否均为1。
创建类型为bool的One()函数,并在其中创建变量intO=0。
从i=0循环直到i<str.size(),如果str[i]==1,则将1加到变量O。
在循环外部,检查是否(O==size)。如果是这样,则返回true。
如果One()函数返回true,则返回Max()函数,然后返回-1作为答案。
否则继续寻找长度。初始化一个数组inta[100]={0}。
从i=0循环直到i<size,然后放入a[i]=(str[i]=='0'?1:-1)并以此方式检查str的每个元素。
在循环外部,初始化另一个数组intarr[100][3],并使用memset(arr,-1,sizeofarr)将其所有元素替换为-1,最后调用Length(a,str,size,0,0,arr)
在Length()函数中,首先检查(i>=size),如果是,则表示字符串结束并返回0。
然后检查是否(arr[i][s]!=-1)。如果是这样,则意味着状态已经被计算并返回arr[i][s]。
然后检查(s==0)。如果是这样,则返回arr[i][s]=max(a[i]+Length(a,str,size,i+1,1,arr),Length(a,str,size,i+1,0,arr));
否则返回arr[i][s]=max(a[i]+Length(a,str,size,i+1,1,arr),0);
示例
#include <bits/stdc++.h> using namespace std; bool One(string str, int size){ int O = 0; for (int i = 0; i < str.size(); i++) O += (str[i] == '1'); return (O == size); } int Length(int a[], string str, int size, int i, int s, int arr[][3]){ // If string is over. if (i >= size) return 0; // If the already calculated. if (arr[i][s] != -1) return arr[i][s]; if (s == 0) return arr[i][s] = max(a[i] + Length(a, str, size, i + 1, 1, arr), Length(a, str, size, i + 1, 0, arr)); else return arr[i][s] = max(a[i] + Length(a, str, size, i + 1, 1, arr), 0); } int Max(string str, int size){ // Checking if all elements are 1 if (One(str, size)) return -1; // Finding length int a[100] = { 0 }; for (int i = 0; i < size; i++) a[i] = (str[i] == '0' ? 1 : -1); int arr[100][3]; memset(arr, -1, sizeof arr); return Length(a, str, size, 0, 0, arr); } // main function int main(){ string str = "100100110"; int size = 9; cout << Max(str, size); return 0; }
输出结果
3