阿里研发岗 0530笔试真题-字符串等频递增变换(详细思路+多语言题解)

字符串等频递增变换阿里研发岗 0530笔试 第三题题目内容在蝴蝶悲园里有一串写着小写字母的标牌。你拿到一个长度为nnn的字符串sss下标从111到nnn。你需要对字符串做kkk次 “操作”。一次操作的过程如下你从左到右依次处理i1,2,…,ni1,2,\dots,ni1,2,…,n。在一次操作中按i1,2,…,ni1,2,\dots,ni1,2,…,n的顺序依次处理每个位置每个位置的修改将立即生效并影响后续位置的统计令ccc为当前位置iii的字符令xxx为位置111至i−1i-1i−1中当前字符等于ccc的数量令yyy为位置i1i1i1至nnn中当前字符等于ccc的数量若xyx yxy则将位置iii的字符修改为字母表中的下一个字母z变为a否则保持不变。现在我们将按顺序执行kkk次操作请你输出做完kkk次操作后的最终字符串。输入描述每个测试文件均包含多组测试数据。第一行输入一个整数t (1≤t≤2×105)t\ (1 \le t \le 2 \times 10^5)t(1≤t≤2×105)代表数据组数每组测试数据描述如下第一行输入两个整数nnn和kkk(1≤n≤105; 1≤k≤105)(1 \le n \le 10^5;\ 1 \le k \le 10^5)(1≤n≤105;1≤k≤105)分别表示字符串长度与操作次数。第二行输入一个长度为nnn的字符串sss保证仅由小写英文字母组成。除此之外保证单个测试文件的nnn之和不超过10510^5105kkk之和不超过10510^5105。输出描述对于每一组测试数据新起一行输出做完kkk次操作后的最终字符串。样例1输入2 2 1 ab 3 2 abc输出bb bbe题解思路逻辑分析一个位置可以发生改变的条件左侧c字符 右侧c字符的数量其实可以转换为左侧c的数量 c的总数量 - 左侧c的数量 -1按照1的规律可以预统计初始input中各个字符的数量使用tot的数量在每一轮中从前往后过程中cnt统计{0, i-1}中各种字符的数量当cnt[c] tot[c] - cnt[c] -1时更新对应位置字符以及更新tot中的字符数量即可C#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){intn,k;cinnk;string s;cins;vectorinttot(26,0);for(charc:s){tot[c-a];}while(k--){vectorintcnt(26,0);for(inti0;in;i){intcs[i]-a;intxcnt[c];intytot[c]-cnt[c]-1;if(xy){tot[c]--;c(c1)%26;tot[c];}// 更新当前字符s[i]char(ac);cnt[s[i]-a];}}couts\n;}return0;}javaimportjava.io.*;importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args)throwsException{BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));StringBuilderoutnewStringBuilder();intTInteger.parseInt(br.readLine());while(T--0){String[]nkbr.readLine().split( );intnInteger.parseInt(nk[0]);intkInteger.parseInt(nk[1]);Stringsbr.readLine();char[]arrs.toCharArray();int[]totnewint[26];for(charc:arr){tot[c-a];}while(k--0){int[]cntnewint[26];for(inti0;in;i){intcarr[i]-a;intxcnt[c];intytot[c]-cnt[c]-1;if(xy){tot[c]--;c(c1)%26;tot[c];}arr[i](char)(ac);cnt[arr[i]-a];}}out.append(newString(arr)).append(\n);}System.out.print(out);}}pythonimportsysinputsys.stdin.readline Tint(input())for_inrange(T):n,kmap(int,input().split())slist(input().strip())tot[0]*26forcins:tot[ord(c)-97]1whilek0:k-1cnt[0]*26foriinrange(n):cord(s[i])-97xcnt[c]ytot[c]-cnt[c]-1ifxy:tot[c]-1c(c1)%26tot[c]1s[i]chr(c97)cnt[c]1print(.join(s))javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});letinput[];rl.on(line,(line){input.push(line.trim());});rl.on(close,(){letidx0;letTNumber(input[idx]);letout[];while(T--){let[n,k]input[idx].split( ).map(Number);letsinput[idx].split();lettotnewArray(26).fill(0);for(letcofs){tot[c.charCodeAt(0)-97];}while(k--){letcntnewArray(26).fill(0);for(leti0;in;i){letcs[i].charCodeAt(0)-97;letxcnt[c];letytot[c]-cnt[c]-1;if(xy){tot[c]--;c(c1)%26;tot[c];}s[i]String.fromCharCode(c97);cnt[c];}}out.push(s.join());}console.log(out.join(\n));});Gopackagemainimport(bufiofmtos)funcmain(){in:bufio.NewReader(os.Stdin)out:bufio.NewWriter(os.Stdout)deferout.Flush()varTintfmt.Fscan(in,T)forT0{T--varn,kintfmt.Fscan(in,n,k)varsstringfmt.Fscan(in,s)arr:[]byte(s)tot:make([]int,26)fori:0;in;i{tot[arr[i]-a]}fork0{k--cnt:make([]int,26)fori:0;in;i{c:int(arr[i]-a)x:cnt[c]y:tot[c]-cnt[c]-1ifxy{tot[c]--c(c1)%26tot[c]}arr[i]byte(ca)cnt[int(arr[i]-a)]}}fmt.Fprintln(out,string(arr))}}