一个01字符串，求出现0、1出现次数相等的最长子串长度
题目描述：
已知一个长度为N的字符串，只由0和1组成， 求一个最长的子串，要求该子串出0和1出现的次数相等。
要求算法时间复杂度尽可能的低。
比如： 10000010111000001，所求为8，加粗的部分有4个0、4个1
最简单的想法就是遍历所有的子串，之后判断该子串是否满足条件N^2子串，每个子串扫一遍判断0、1是否出现的次数相等，复杂度为O(N^3)
方法一：
稍加思考就会发现， 如果一个长度为n的子串满足条件，加么这n个元素的和加起来一定=(n/2),且
子串长度为偶数，这样在循环的过程中，增量加就可以了，不需要每个子串从头计算，复杂度降为O(N^2).
该思想的程序为fun():
int fun(char num[],int n)
{
int i,j;
int maxlen=0;//所求
int sum,currentlen;//当前子串和与当前子串长度
//挨个判断每个子串是否符合要求，若符合，则更新maxlen
for(i=0;i<n;i++)
{
sum=0;
for(j=i;j<n;j++)
{
currentlen = j-i+1;
sum+=num[j]-'0';
if(currentlen%2==0 && sum==currentlen/2 && currentlen>maxlen)
maxlen = currentlen;
}
}
return maxlen;
}方法二：
和fun()的主体差不多，设了一个sum来判断每个子串中0,1个数是否相等，遇到0，sum--；遇到1，sum++。fun()和fun2()求子串的思路和方法要领会，它是以求以每个字符开头的所有子串这样的方式求的，外面再包个大循环就能求出所有子串。
int fun2(char num[],int n)
{
int i,j;
int maxlen=0;//所求
int sum,currentlen;//当前子串和与当前子串长度
//挨个判断每个子串是否符合要求，若符合，则更新maxlen
for(i=0;i<n;i++)
{
sum=0;
for(j=i;j<n;j++)
{
currentlen = j-i+1;
if(num[j]=='0')
sum--;
else
sum++;
if(sum==0 && currentlen>maxlen)
maxlen = currentlen;
}
}
return maxlen;
} 方法三：
一种巧妙的解法：定义一个数据temp[N]， temp[i]表示从num[0...i]中 num_of_0 - num_of_1，0的个数与1的个数的差那么如果num[i+1] ~ num[j]是符合条件的子串，一定有 temp[i] == temp[j]，因为中间的部分0、1个数相等，相减等于0。只需要扫一遍num[N]就能把temp[N]构造出来了。这样问题就转换成了求距离最远的一对数，使得temp[i] == temp[j]，因为temp[i]的范围一定是[-N,N]，-N到N的范围所对应的从num[0]开始的子串的结尾下标i都存起来，这样每扫到temp[i]，查数就行了。
设两个辅助数组temp[]与assist[]，代表的意义如下:
temp[i]表示num[0...i]中0的个数与1的个数差(即0的个数减去1的个数),则必有 -n<=temp[i]<=n
assist[]为辅助数组，里面存了0,1个数差所对应的num的最小下标，初值为-1表示该处还未存入内容。
assist[0]表示0,1个数差为-n的从num[0]开始的子串的结尾位置，即num[0...i]中的i，此时num[0...i]串中0,1个数差为-n,assist[2*n]表示0,1个数差为n的从num[0]开始的子串的结尾位置，即num[0...i]中的i，此时num[0...i]串中0,1个数差为n,assist[k]表示0,1个数差为 k-n 的从num[0]开始的子串的结尾位置。即assist[k+n] = i 表示0,1个数差为k的子串为num[0...i]
int fun1(char num[],int n)
{
int maxlen=0;//所求
int currentlen;//当前子串长度
int temp[n];
int assist[2*n+1]; //temp[]和assist[]的意义见上
int i;
int count[2]={0,0};//分别代表当前0和1的个数,count[0]为0的个数，count[1]为1的个数
for(i=0;i<2*n+1;i++)
assist[i] = -1;
for(i=0;i<n;i++)
{
count[num[i]-'0']+=1;
temp[i] = count[0]-count[1];
if(assist[temp[i]+n]==-1) //还不存在0,1个数差为temp[i]的从num[0]开始的子串
assist[temp[i]+n] = i;
//已存在0,1个数差为temp[i]的从num[0]开始的子串，设assist[temp[i]+n]为k,则该子串为num[0..k]
else
{
//设assist[temp[i]+n]为k，从num[0...i]中去掉num[0...k]为当前找到的符合条件的子串
currentlen = i- assist[temp[i]+n];
if(currentlen > maxlen)
maxlen = currentlen;
}
}
return maxlen;
}
int main()
{
char num[]="10000010111000001";
int maxlen = fun(num,strlen(num));
printf("maxlen=%d\n",maxlen);
return 0;
}
最后一种解法
/**
*
* 数字串，全为0,1组合而成。求一个最长的连续子串，其中0和1的个数相等。
* 比如: 01100111 --> 011001
* 110000011 --> 1100 / 0011
*
* 方法：
* 定义一个数组a，a[0] = 0
* 然后遍历输入输入数字串，遇到0，减1，遇到1，加1。含义就是，到目前位置，净值出现了多少个0或者1.
* 在数组a中选择两个相等的值，比如都是-3，第一个-3表示到该元素为止，多出现了3个0，第二个-3还是表示
* 到该元素为止，多出3个0，那么这两个元素之间的0和1的个数必定相互抵消。
* 于是，所求子串等同于，数组a中距离最远的两个相同值。可以两次循环，复杂度o(n*n)
*
* 为了O(n)的复杂度，利用hash表代替数组。原理一样。
*
**/
public class ZeroOnePairs {
public static void find(int[] input){
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
map.put(0, 0);
int begin = 0;
int max = 0;
int current = 0;
for(int i=0; i<input.length; i++){
if(input[i] == 0){
current--;
}else{
current++;
}
Integer p = map.get(current);
if(p == null){
map.put(current, i+1);
}else{
int l = p.intValue();
if((i+1-l) > max){
max = i + 1 - l;
begin = l;
}
}
}
for(int j=begin; j<begin+max; j++){
System.out.print(input[j]);
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
// int[] input = {0,1,1,0,0,1,1,1};
int[] input = {1,0,0,0,0,0,1,1};
ZeroOnePairs.find(input);
}
}
京公网安备 11010502036488号