首页 > 其他分享 >数据结构

数据结构

时间:2023-03-18 21:44:07浏览次数:47  
标签:map int 18 mp res 数据结构

数据结构

你有一个长度为 n 的字符串,其中仅含0,1,2三个字符。
你希望知道,这个字符串有多少个子串,满足该子串的0,1,2个数相等?
n 之和不超过3e5

输入

4
3
012
6
001122
18
102100120120120012
18
012012012012012012

输出

1
1
25
51

分析:

map记录0,1与1,2的差值出现次数,在下一次出现时可以直接更新答案
注意map[{0 ,0}]的初始化

int n;
int res;
map<PII, int> mp;
string s;
int a[N], b[N], c[N];
void solve()
{
    mp.clear();
    res = 0;
    for(int i = 1; i <= n; i ++)
    {
        a[i] = b[i] = c[i] = 0;
    }
    cin >> n >> s;
    s = " " + s;
    for (int i = 1; i <= n; i++)
    {
        a[i] = a[i - 1];
        b[i] = b[i - 1];
        c[i] = c[i - 1];
        if (s[i] == '0')
            a[i]++;
        if (s[i] == '1')
            b[i]++;
        if (s[i] == '2')
            c[i]++;
    }

    mp[{0, 0}] = 1;
    for (int i = 1; i <= n; i++)
    {
        int t = a[i] - b[i], tt = b[i] - c[i];
        res += mp[{t, tt}];
        mp[{t, tt}]++;
    }
    cout << res << endl;
}

标签:map,int,18,mp,res,数据结构
From: https://www.cnblogs.com/Aidan347/p/17231896.html

相关文章

  • 数据结构-布隆过滤器
    1.布隆过滤器的概念定义布隆过滤器:是⼀种概率型数据结构,特点是⾼效的插⼊和查询,能明确告知某个字符串⼀定不存在或者可能存在;优点和缺点优点:布隆过滤器相⽐传......
  • golang常用库包:缓存redis操作库go-redis使用(03)-高级数据结构和其它特性
    Redis高级数据结构操作和其它特性第一篇:go-redis使用,介绍Redis基本数据结构和其他特性,以及go-redis连接到Redishttps://www.cnblogs.com/jiujuan/p/17207166.html第......
  • 数据结构-->链表_02
    本期的链表继续进行,上期我们完成了链表的增加和删除。现在接下来,我们进行链表的查改与优化头文件“SList.h”#include<stdio.h>#include<assert.h>#include<stdlib.h>typ......
  • 数据结构(第一章)
    数据结构(第一章)一、概论数据:数据是信息的载体,是描述事物客观属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据元素:数据元素是数据......
  • 数据结构大乱炖
    线段树基本思想将[1,n]分解成若干特定的子区间(数量不超过4×n),然后,将每个区间[l,r]都分解为少量特定的子区间,通过对这些少量子区间的修改或者统计,来实现快速对[l,......
  • 数据结构-->链表_01
    首次书写链表有关的知识,先来明确什么是链表?链表是一种物理存储结构上非连续,非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的举一个形象化的现实生活中......
  • Qz学算法-数据结构篇(非线性结构、树)
    非线性结构非线性结构包括:二维数组,多维数组,广义表,树结构,图结构树树结构为什么需要树结构数组存储方式的分析优点:通过下标方式访问元素,速度快。对于有序数组,还可使用二分查找......
  • 回顾集合及其数据结构
    集合1.集合的体系Collection集合分为单列集合Collection和双列集合MapCollection只有增删功能没有改查功能,特点是单列集合所有共性功能,有三种遍历方式(1.迭代器2.增......
  • 【数据结构】B树与B+树
    简介:本文主要介绍了B树和B+树的插入、删除操作。一、B树在1970年,Bayer&McCreight发表的论文《ORGANIZATIONANDMAINTENANCEOFLARGEORDEREDINDICES》(大型有序索引......
  • 数组模拟环形队列java(数据结构与算法)
    思路:背景队列有两种实现方式:1、数组,2、链表在数组实现队列时,有的教科书中只说了队列满的条件是(rear+1)%manSize=front这个公式真让人摸不着头脑原来:这是数组模拟环......