仅由01构成的串中，最长01数目相等的子串_最长01相等子串_Authur_gyc的博客-程序员秘密

有一个仅由0和1组成的01串，找到其中最长的一段子串，使得该子串中0和1的数目相等。

面试时将0改成-1，然后用前缀和，二分枚举长度然后检验，这里二分枚举错了，不满足二分的性质。

正确思路是，在前缀和的基础上，找前缀和相等的 i 和 j 并且 |i - j| 尽可能大。

这里用哈希存一下每个前缀和的最小 id ，然后O（n）跑一下取最大距离即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int arr[maxn], pre_sum[maxn];
unordered_map <int, int> mp;
int main() {
    
    int n; cin >> n;
    mp[0] = 0;//特别的
    for(int i = 1; i <= n; i++){
    
        scanf("%1d", &arr[i]);
        arr[i] = arr[i] == 0 ? -1 : 1;
        int x = pre_sum[i] = pre_sum[i - 1] + arr[i];
        //int x = pre_sum[i];
        if(x == 0){
    
            continue;//0的最小下标不用更新
        }
        mp[x] = mp[x] ? mp[x] : i;//存储最小下标
    }    
    int ans = 0;
    for(int i = 1; i <= n; i++){
    
        ans = max(ans, i - mp[pre_sum[i]]);
    }
    cout << ans << endl;
    return 0;
}

本文链接：https://blog.csdn.net/WHY995987477/article/details/115628705

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Stacked Autoencoders_zjxiaolu的博客-程序员秘密

博文内容参照网页Stacked Autoencoders，Stacked Autocoders是栈式的自编码器（参考网页Autoencoder and Sparsity和博文自编码与稀疏性），就是多层的自编码器，把前一层自编码器的输出（中间隐藏层）作为后一层自编码器的输入，其实就是把很多自编码器的编码部分叠加起来，然后再叠加对应自编码器的解码部分，这样就是一个含有多个隐含层的自编码器了。本博文

SpringBoot+Mysql 无法保存emoj表情？_一灰灰blog的博客-程序员秘密

尤记得很久以前，想存 emoj 表情到 mysql 中，需要额外的将 emoj 表情转码之后保存，每次读取时，再解码还原成一下；每次这种 sb 的操作，真心感觉心塞，那么有没有办法直接存...

html学习之htm文件结构和标签_悦仲的博客-程序员秘密

今天是开通博客的第一天，也是正式学习html的第一天。web前端工程师学习计划正在进行中，希望我能坚持。一、html文件的结构一个HTML文件是有自己固定的结构的。 ... ...二、认识标签11.称为根标签，所有的网页标签都在中。2. 标签用于定义文档的头部，它是所有头部元素的容器。头部元素有、、、、等标签。文档的头部描述了文

内网ip与外网ip_192.168.100.1/23是什么ip_三分恶的博客-程序员秘密

查看内网ip与外网ipcmd，进入Dos窗口，输入命令tracert www.baidu.com

JavaWeb文件上传图片到非工程目录，然后前端访问_Mooner_guo的博客-程序员秘密

首先，假如使用的是eclipse开发项目，那么eclipse运行tomcat并不是tomcat安装目录，而是eclipse的一个插件目录。如果想在tomcat的安装目录部署项目，那么就要修改eclipse配置tomcat的虚拟目录。具体修改方法如可以看这个博客http://kingxss.iteye.com/blog/1741438 ，或者百度搜索很多讲解的。然后我们将上传图片到后台，

灰色关联度分析（Grey Relation Analysis，GRA）原理详解_江户川柯壮的博客-程序员秘密

释名灰色关联度分析（Grey Relation Analysis，GRA），是一种多因素统计分析的方法。简单来讲，就是在一个灰色系统中，我们想要了解其中某个我们所关注的某个项目受其他的因素影响的相对强弱，再直白一点，就是说：我们假设以及知道某一个指标可能是与其他的某几个因素相关的，那么我们想知道这个指标与其他哪个因素相对来说更有关系，而哪个因素相对关系弱一点，依次类推，把这些因素排个序，得到一个...