数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究二进制字符串中零和一的最大差值 - (O(n) 时间复杂度) C++ 实现
给定任务是从给定的二进制字符串中找到一个子字符串，然后找到零和一的数量之间的最大差值。
现在让我们用一个例子来理解我们必须做什么 -
输入
str = “10010110”
输出
2
解释
在从位置 1 到 4 的子数组（“0010”）中，零和一的差值 = 3 – 1 = 2，这是可以找到的最大值。
输入
str = “00000”
输出
5
下面程序中使用的方案如下
在 main() 函数中创建一个字符串 str 来存储二进制字符串。 同时声明一个数组 int arr[str.length()+1];
使用 memset(arr,0,sizeof(arr)); 将 arr[] 的所有元素设置为 0。
循环从 j = 1 到 j<= str.length()
检查 if(memset(arr,0,sizeof(arr)), 如果是，则将 arr[j] 设置为 max(arr[j-1]-1,-1);
否则将 arr[j] 设置为 max(arr[j-1]+1,1);
在循环外部，使用 *max_element(arr+1, arr+str.length()+1); 打印最大值。
示例
#include<bits/stdc++.h>
using namespace std;
int main(){
string str = "10010110";
int arr[str.length()+1];
memset(arr,0,sizeof(arr));
for(int j=1;j<=str.length();j++){
if(str[j-1]=='1')
arr[j]=max(arr[j-1]-1,-1);
else
arr[j]=max(arr[j-1]+1,1);
}
cout<<*max_element(arr+1,arr+str.length()+1);
return 0;
}输出
2
更新于: 2020年8月4日
116 次浏览
广告