最长01子串

电玩女神 2022-07-29 11:56 177阅读 0赞

【题目】

给定一个数组，数组中只包含0和1。请找到一个最长的子序列，其中0和1的数量是相同的。

例1：10101010     结果就是其本身。

例2：1101000       结果是110100

【解析】

这个题目，看起来比较简单，一些同学可能认为题目的描述符合动态规划的特征，然后就开始用动态规划解，努力找状态转移方程。这些同学的感觉，是很正确的。

但找状态转移方程，我们要对原来的数组进行变换一下。原来是0和1的串，我们将0都换为-1。

这样题目目标就变成，找到一个最长的子串，子串数字和是0。设原数组为A, DP\[i\]表示从0开始到i的子数组和。DP遍历一遍数组即可。

例1中的数组产生的DP为：

![n2IVzu.jpg_web][]

这个例子，最后一个值是0，并且长度是偶数位。直接满足了结果。

再看例子2：

![yyEBzan.jpg_web][]

5的位置为0，最长子串从0开始到5，长度为6。

上面这两个例子，所求的子串都是从头开始，如果不是从头开始，会是什么样的呢？看这个例子：1101100

![Z3IRNja.jpg_web][]

通过观察上面的表格，我们可以得到，DP\[0\]==DP\[6\]==DP\[2\]，DP\[1\]==DP\[3\]. 根据DP的定义，如果DP\[i\]==DP\[j\]，i 一种方法，

我们用map保存DP的值到位置的映射，如下表：

![J3InmaB.jpg_web][]

我们最终的算法，要综合考虑最常穿是否从头开始的。 上面的这个思路，时间复杂度是O(n),空间复杂度也是O(n).

还有其他的思路，例如DP保存的是\[0,i\]的1的个数，那么DP\[j\] - DP\[i\] \* 2 == j - i则表明A\[i+1\]...A\[j\]是一个满足条件的串，

找到j-i最大的，就是最终的结果，这个思路的时间复杂度为O(n^2),空间复杂度为O(n).

#include<iostream>
    #include<string.h>
    #include<map>
    using namespace std;
    //最长的01字串
    string MaxSubStr(string str){
    	int len=str.length();
      	int* dp=new int[len+1];
      	//dp下标从1开始
      	dp[1]=(str[0]-'0')==1?1:-1;
      	for(int i=2;i<=len;i++){
        	dp[i]=(str[i-1]-'0')==1?1:-1;
        	dp[i]+=dp[i-1];
      	}
      	//统计最大01字串
      	int start = 0,end = 0,max = 0,begin;
      	map<int,int> m;
      	for(int i = 1;i <= len;i++){
        	//不同dp值原始起点
        	begin = m[dp[i]];
        	if(begin==0&&dp[i]!=0){
          		m[dp[i]]=i;
        	}
        	else{
          	//更新最大子串
          		if(i-begin>max){
            		max=i-begin;
            		start=begin;
           			end=i;
          		}
        	}
      	}
      	return str.substr(start,max);
    }
    int main(){
    	string str("01101100001");
      	cout<<"Max:"<<MaxSubStr(str)<<endl;
      	return 0;
    }

[n2IVzu.jpg_web]: http://img2.tuicool.com/n2IVzu.jpg!web
[yyEBzan.jpg_web]: http://img2.tuicool.com/yyEBzan.jpg!web
[Z3IRNja.jpg_web]: http://img1.tuicool.com/Z3IRNja.jpg!web
[J3InmaB.jpg_web]: http://img2.tuicool.com/J3InmaB.jpg!web