`
SunnyYoona
  • 浏览: 361761 次
社区版块
存档分类
最新评论

[经典面试题]最长01子串

 
阅读更多

【题目】

给定一个数组,数组中只包含0和1。请找到一个最长的子序列,其中0和1的数量是相同的。
例1:10101010 结果就是其本身。
例2:1101000 结果是110100

【解析】

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

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

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

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


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

再看例子2:


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

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


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

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


我们最终的算法,要综合考虑最常穿是否从头开始的。 上面的这个思路,时间复杂度是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;
            }//if
        }//if
    }//for
    return str.substr(start,max);
}

int main(){
    string str("01101100001");
    cout<<"Max:"<<MaxSubStr(str)<<endl;
    return 0;
}



分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics