拼多多笔试真题-平衡队伍(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是最大的平衡队伍。题解和思路思路实现思路前缀和可以将A看作-1B看作1,从前往后进行累加。利用前缀和特性可以得出当prefix[i] prefix[j]时说明[i1, j]中1的数量和-1数量相同就是题目所描述的均衡情况。为了求出尽可能长度当前位置 i 前缀和sum情况下肯定是选取尽量靠前的前缀和也为sum的位置所以只需要使用哈希表记录各个前缀和首次出现位置。按照1、2分析从前往后累加前缀和sum 将首次出现前缀和位置记录在哈希表中遍历到i时前缀和sum在哈希表中已经存在记录时尝试更新最长均衡长度maxLen max(maxLen, i - mp[sum])算法平均时间复杂度为OnC#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;string s;cinn;cins;intmaxLen0;intsum0;// 记录前缀和首次出现位置unordered_mapint,intmp;mp[0]-1;for(inti0;in;i){sum(s[i]A?-1:1);// 两个相同前缀和之间一定平衡if(mp.count(sum)){maxLenmax(maxLen,i-mp[sum]);// 记录sum首次出现位置}else{mp[sum]i;}}coutmaxLen;}Javaimportjava.io.*;importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args)throwsException{BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));intnInteger.parseInt(br.readLine());Stringsbr.readLine();intmaxLen0;intsum0;// 记录前缀和首次出现位置HashMapInteger,IntegermpnewHashMap();mp.put(0,-1);for(inti0;in;i){sum(s.charAt(i)A?-1:1);// 两个相同前缀和之间一定平衡if(mp.containsKey(sum)){maxLenMath.max(maxLen,i-mp.get(sum));// 记录sum首次出现位置}else{mp.put(sum,i);}}System.out.print(maxLen);}}pythonimportsys nint(sys.stdin.readline())ssys.stdin.readline().strip()maxLen0sum0# 记录前缀和首次出现位置mp{}mp[0]-1foriinrange(n):sum-1ifs[i]Aelse1# 两个相同前缀和之间一定平衡ifsuminmp:maxLenmax(maxLen,i-mp[sum])# 记录sum首次出现位置else:mp[sum]iprint(maxLen)Javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});letinput[];rl.on(line,line{input.push(line.trim());});rl.on(close,(){letnNumber(input[0]);letsinput[1];letmaxLen0;letsum0;// 记录前缀和首次出现位置letmpnewMap();mp.set(0,-1);for(leti0;in;i){sum(s[i]A?-1:1);// 两个相同前缀和之间一定平衡if(mp.has(sum)){maxLenMath.max(maxLen,i-mp.get(sum));// 记录sum首次出现位置}else{mp.set(sum,i);}}console.log(maxLen);});Gopackagemainimport(bufiofmtos)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;in;i{ifs[i]A{sum--}else{sum}// 两个相同前缀和之间一定平衡ifpos,ok:mp[sum];ok{ifi-posmaxLen{maxLeni-pos}// 记录sum首次出现位置}else{mp[sum]i}}out:bufio.NewWriter(os.Stdout)deferout.Flush()fmt.Fprint(out,maxLen)}