数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中二进制字符串中0和1的最大差值
给定的任务是从给定的二进制字符串中找到一个子字符串，然后找到0和1数量之间的最大差值。
让我们用一个例子来理解我们必须做什么：
输入
str = “100100110”
输出
2
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
解释
在从位置1到5的子数组（“00100”）中，0和1之间的差值 = 4 – 1 = 3，这是可以找到的最大值。
输入
str = “00000”
输出
5
下面程序中使用的算法如下：
在main()函数中，创建一个字符串**str**来存储二进制字符串。还初始化一个变量int size来存储字符串的**大小**，并将两者都传递给Max()函数。
在Max()函数中，首先通过调用One()函数检查所有元素是否都是1。
创建一个bool类型的One()函数，并在其中创建一个变量int O = 0。
循环从i = 0到i< str.size()，如果str[i] == 1，则将1添加到变量O中。
在循环外部，检查if(O == size)。如果是，则返回true。
回到Max()函数，如果One()函数返回true，则返回-1作为答案。
否则继续查找长度。初始化一个数组int a[100] = {0}。
循环从i = 0到i< size，并设置a[i] = (str[i] == '0' ? 1 : -1)，以此方式检查str的每个元素。
在循环外部，初始化另一个数组int arr[100][3]，并使用memset(arr, -1, sizeof arr)将其所有元素替换为-1，最后调用Length(a, str, size, 0, 0, arr)
在Length()函数中，首先检查if (i >= size)，如果是，则表示字符串结束，返回0。
然后检查if (arr[i][s] != -1)。如果是，则表示状态已计算，返回arr[i][s]。
然后检查if(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
257 次浏览
