拼多多笔试真题-平衡队伍(C++/Py/Java /Js/Go)

平衡队伍

拼多多技术岗 8月2号笔试 第一题

题目内容

某体育俱乐部的nnn名队员排成一列，每名队员的类型用字符串中的字符表示：‘AAA’或’BBB’。教练想要选出一个连续的区间组成队伍。若区间内 ‘AAA’ 类队员数与 ‘BBB’ 类队员数相等，则称该队伍为“平衡队伍”。请找出平衡队伍的最大人数。

输入描述

第111行：一个整数nnn(1≤n≤2×105)(1 \le n \le 2\times10^5)(1≤n≤2×105)
第222行：一个长度为nnn的字符串sss，仅包含字符 ‘AAA’ 和 ‘BBB’

输出描述

一个整数，表示平衡队伍的最大人数。若不存在平衡队伍，输出000。

样例1

输入

4 ABAB

输出

4

说明
整个字符串有222个 ‘AAA’ 和222个 ‘BBB’，满足平衡条件，最大长度为444。

样例2

输入

3 AAA

输出

0

说明
无法选出平衡队伍，输出000。

样例3

输入

5 AAABB

输出

4

说明
“AABBAABBAABB” 子串（第222至555位）有222个 ‘AAA’ 和222个 ‘BBB’，长度为444，是最大的平衡队伍。

题解和思路

思路

实现思路：前缀和

1. 可以将A看作-1，B看作1,从前往后进行累加。利用前缀和特性可以得出当prefix[i] == prefix[j]时说明[i+1, j]中1的数量和-1数量相同，就是题目所描述的均衡情况。
2. 为了求出尽可能长度，当前位置 i 前缀和sum情况下肯定是选取尽量靠前的前缀和也为sum的位置，所以只需要使用哈希表记录各个前缀和首次出现位置。
3. 按照1、2分析，从前往后累加前缀和sum， 将首次出现前缀和位置记录在哈希表中，遍历到i时，前缀和sum在哈希表中已经存在记录时，尝试更新最长均衡长度maxLen = max(maxLen, i - mp[sum])
4. 算法平均时间复杂度为O（n）

C++

#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;string s;cin>>n;cin>>s;intmaxLen=0;intsum=0;// 记录前缀和首次出现位置unordered_map<int,int>mp;mp[0]=-1;for(inti=0;i<n;i++){sum+=(s[i]=='A'?-1:1);// 两个相同前缀和之间一定平衡if(mp.count(sum)){maxLen=max(maxLen,i-mp[sum]);// 记录sum首次出现位置}else{mp[sum]=i;}}cout<<maxLen;}

Java

importjava.io.*;importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args)throwsException{BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));intn=Integer.parseInt(br.readLine());Strings=br.readLine();intmaxLen=0;intsum=0;// 记录前缀和首次出现位置HashMap<Integer,Integer>mp=newHashMap<>();mp.put(0,-1);for(inti=0;i<n;i++){sum+=(s.charAt(i)=='A'?-1:1);// 两个相同前缀和之间一定平衡if(mp.containsKey(sum)){maxLen=Math.max(maxLen,i-mp.get(sum));// 记录sum首次出现位置}else{mp.put(sum,i);}}System.out.print(maxLen);}}

python

importsys n=int(sys.stdin.readline())s=sys.stdin.readline().strip()maxLen=0sum=0# 记录前缀和首次出现位置mp={}mp[0]=-1foriinrange(n):sum+=-1ifs[i]=='A'else1# 两个相同前缀和之间一定平衡ifsuminmp:maxLen=max(maxLen,i-mp[sum])# 记录sum首次出现位置else:mp[sum]=iprint(maxLen)

Javascript

constreadline=require("readline");constrl=readline.createInterface({input:process.stdin,output:process.stdout});letinput=[];rl.on("line",line=>{input.push(line.trim());});rl.on("close",()=>{letn=Number(input[0]);lets=input[1];letmaxLen=0;letsum=0;// 记录前缀和首次出现位置letmp=newMap();mp.set(0,-1);for(leti=0;i<n;i++){sum+=(s[i]==='A'?-1:1);// 两个相同前缀和之间一定平衡if(mp.has(sum)){maxLen=Math.max(maxLen,i-mp.get(sum));// 记录sum首次出现位置}else{mp.set(sum,i);}}console.log(maxLen);});

Go

packagemainimport("bufio""fmt""os")funcmain(){in:=bufio.NewReader(os.Stdin)varnintvarsstringfmt.Fscan(in,&n)fmt.Fscan(in,&s)maxLen:=0sum:=0// 记录前缀和首次出现位置mp:=make(map[int]int)mp[0]=-1fori:=0;i<n;i++{ifs[i]=='A'{sum--}else{sum++}// 两个相同前缀和之间一定平衡ifpos,ok:=mp[sum];ok{ifi-pos>maxLen{maxLen=i-pos}// 记录sum首次出现位置}else{mp[sum]=i}}out:=bufio.NewWriter(os.Stdout)deferout.Flush()fmt.Fprint(out,maxLen)}