学会 01 串

学会 01 串

51node 上的一道题目 01 串[1]

给定一个 01 串 S,求出它的一个尽可能长的子串 S[i..j],满足存在一个位置 i<=x <j, S[i..x]中 0 比 1 多,而 S[x + 1..j]中 1 比 0 多。求满足条件的最长子串长度。 输入

一行包含一个只由 0 和 1 构成的字符串 S。S 的长度不超过 1000000。

输出

一行包含一个整数,表示满足要求的最长子串的长度。

输入样例

10

输出样例

0

时间限制 1s 空间 131,072.0 KB

为了方便操作我们可以把字符串先转成 int 数组的类型,同时把 0 记录-1 后边方便我们判断 0 和 1 谁比较多

int a[i];  //a[i]用来存储0变成-1 1变成1的值
string s;
cin>>s;
int len=s.length();
for (int i = 1; i <= len; i++)
{
    if (s[i-1] == '0')
        a[i] = -1;
    else  
        a[i] = 1;
}

观察一下这道题,想一下 x 点的下标可能是 中的任何一个位置 (读题可知不能是不能是 len-1 这个下标)

所以我们可以做一下预处理,然后对每个点进行枚举,看 x 取哪个点的时候字串的位置最大

我们先假设一个最终下标是 y 点 假设 s[i...x]为 s1,s[x+1....j]为 s2 先看一下 s1 情况有两种

  1. 0-y 之间 0 的个数比 1 的个数要多 这时候 s1 长度是
  2. 0-y 之间 1 的个数比 0 的个数要多或者相等(这两种情况可以归结为 0 的个数没有 1 的多) 这时候 s1 的长度不能直接得出我们需要进行一下处理

第二种情况下我们需要用贪心的思想取考虑

既然这个区间上 0 没有 1 多 那么我们只能选取这个区间上的一个子区间 选取的这个子区间想要长度最大化的时候 必定是 0 的个数比 1 的个数多 1 个

先假设一个串是 111110000110

黑线部分表示的是 s1 可以看出来这时候 0 的个数比 1 的正好多 1 个 这时候 s1 中的值累加是 -1

现在我们知道如何选择了 那么我们怎么能知道 s1 的起始位置在哪?

再看一下上面我们得出 s1 是第二种情况的时候 s1 中的和是-1 那么我们扫一遍数组记录前缀和是不是就能得出 y 点的 s1 在哪了?

int index[maxn];
int now;  //记录前缀和
memset(index, -1, sizeof index);
for (int i = 1; i <= len; i++) {
    now += a[i];
    if (now < 0)
        lef[i] = i;   // 如果前缀和小于0的时候 s1的起始位置就是下表为0的地方 这时候s1的长度是i
    else  
    {
        if (index[now + 1] != -1)
        {
            lef[i] = i - index[now + 1];
            //此时长度是i-index[now+1]
            //为什么是 index[now+1] 而不是index[now+2]
            //读者可以用111110000110比着试一下
        }
        else  
        {
            index[now] = i;
            lef[i] = 0;
            //这种情况下s1不存在 拿上边那个例子来说 到下标为4的时候 now=4 此时怎么选取s1都选不出来
        }
    }
}

以上就是 s1 的寻找过程 反过来寻找 s2 的长度也是同理 下面给出完整的代码

    #include<iostream>
    #include<string>
    #include<string>
    #include<cstring>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn = 1000005;
    int a[maxn];  //存储string转化后的值
    int index[maxn]; //辅助数组
    int lef[maxn];//记录每个点左边选取的序列的最长长度
    int rt[maxn];//右边同理
    string s;
    int main()  
    {
        cin >> s;
        int len = s.length();
        for (int i = 1; i <= len; i++)
        {
            if (s[i-1] == '0')
                a[i] = -1;
            else  
                a[i] = 1;
        }
        int now = 0;
        memset(index, -1, sizeof index);
        // 注意下面转存到int数组的时候我是从下标1开始的
        // 对于每一个点 寻找它的s1长度
        for (int i = 1; i <= len; i++) {
            now += a[i];
            if (now < 0)
                lef[i] = i;
            else  
            {
                if (index[now + 1] != -1)
                {
                    lef[i] = i - index[now + 1];
                }
                else  
                {
                    index[now] = i;
                    lef[i] = 0;
                }
            }
        }
            //寻找s2长度
        memset(index, -1, sizeof index);
        now = 0;
        for (int i = len; i >= 1; i--)
        {
            now += a[i];
            if (now > 0)
            {
                rt[i] = len - i + 1;
            }
            else  
            {
                if (index[-now + 1] != -1)
                    rt[i] = index[-now + 1] - i;
                else  
                {
                    index[-now] = i;
                    rt[i] = 0;
                }
            }
        }
        //最后一步就是从左往右枚举x点了 看哪个点更合适
        int ans = 0;
        for (int i = 1; i < len; i++)
        {
            if(lef[i]>0&&rt[i+1]>0)  //不能忘记判断
                ans = max(ans, lef[i] + rt[i + 1]);
        }
        printf("%d", max(ans,0));
        return 0;
    }

最后再留一个练习了 也是 01 串的运用[2]  上面讲的这道题我们是用前缀和的形式来寻找我们想要的信息的练习是使用异或记录状态的

参考资料

[1]

01串: https://www.51nod.com/Challenge/Problem.html#problemId=1391

[2]

也是01串的运用: https://nanti.jisuanke.com/t/43513

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:故逝

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Bessie的好牌(队列)- POJ 3629

    Bessie is playing a card game with her N-1 (2 ≤ N ≤ 100) cow friends using a dec...

    ACM算法日常
  • 简单ac自动机学习

    简单的来讲解一下自动机,虽然都在说这是和的组合,但个人觉得不需要深入理解这两个仍然可以学会它。同时由于网上已经存在了很多教程,本文尽量避免采取和网上一样的说法,...

    ACM算法日常
  • 洛谷 | P1028 数的计算(递推)

    考虑数字6,第一次有16、26、36,第二次有126、136,然后还有6本身(不做任何处理)。

    ACM算法日常
  • 【HDU 2203】亲和串

    给你一个字符串s1,字符串s2,s1循环移位,使s2包含在s1中,则s2 是s1的亲和串

    饶文津
  • 推荐一个项目:数据结构和算法必知必会的 50 个代码实现

    看了这么久小吴的文章,不知道你们有没有发现,目前文章中涉及到的编程代码有 Java、C++、Python、JavaScript 这么多种,但就算法而言,实际上这...

    五分钟学算法
  • 08:石头剪刀布

    08:石头剪刀布 总时间限制: 1000ms 内存限制: 65536kB描述 石头剪刀布是常见的猜拳游戏。石头胜剪刀,剪刀胜布,布胜石头。如果两个人出拳一样,...

    attack
  • 微信小游戏入门与实战 刷爆朋友圈教程视频

    七月半夏
  • 1026 程序运行时间 (15 分)

    除以100的四舍五入有没有考虑到,因此在最开始虽然输入是整数,但是也要赋值double。

    可爱见见
  • RPA机器人流程自动化开启高效办公潮流

    数据输入和报告生成作业是公司常见的流程,几乎不限行业。这种工作简单且重复,往往占用了企业大量的人力成本和时间成本。

    蕉黄
  • 腾讯云公网负载均衡技术实现详解

    本文主要讲述了腾讯云CLB的基本概念,业务架构以及公网LB技术实现。

    朱彬峰

扫码关注云+社区

领取腾讯云代金券