)
字符串等频递增变换
阿里研发岗 0530笔试 第三题
题目内容
在蝴蝶悲园里，有一串写着小写字母的标牌。
你拿到一个长度为nnn的字符串sss（下标从111到nnn）。
你需要对字符串做kkk次 “操作”。
一次操作的过程如下：你从左到右依次处理i=1,2,…,ni=1,2,\dots,ni=1,2,…,n。
在一次操作中，按i=1,2,…,ni=1,2,\dots,ni=1,2,…,n的顺序依次处理每个位置，每个位置的修改将立即生效并影响后续位置的统计：
- 令ccc为当前位置iii的字符；
- 令xxx为位置111至i−1i-1i−1中当前字符等于ccc的数量；
- 令yyy为位置i+1i+1i+1至nnn中当前字符等于ccc的数量；
- 若x=yx = yx=y，则将位置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^5105，kkk之和不超过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++
#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cin>>T;while(T--){intn,k;cin>>n>>k;string s;cin>>s;vector<int>tot(26,0);for(charc:s){tot[c-'a']++;}while(k--){vector<int>cnt(26,0);for(inti=0;i<n;i++){intc=s[i]-'a';intx=cnt[c];inty=tot[c]-cnt[c]-1;if(x==y){tot[c]--;c=(c+1)%26;tot[c]++;}// 更新当前字符s[i]=char('a'+c);cnt[s[i]-'a']++;}}cout<<s<<"\n";}return0;}java
importjava.io.*;importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args)throwsException{BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));StringBuilderout=newStringBuilder();intT=Integer.parseInt(br.readLine());while(T-->0){String[]nk=br.readLine().split(" ");intn=Integer.parseInt(nk[0]);intk=Integer.parseInt(nk[1]);Strings=br.readLine();char[]arr=s.toCharArray();int[]tot=newint[26];for(charc:arr){tot[c-'a']++;}while(k-->0){int[]cnt=newint[26];for(inti=0;i<n;i++){intc=arr[i]-'a';intx=cnt[c];inty=tot[c]-cnt[c]-1;if(x==y){tot[c]--;c=(c+1)%26;tot[c]++;}arr[i]=(char)('a'+c);cnt[arr[i]-'a']++;}}out.append(newString(arr)).append('\n');}System.out.print(out);}}python
importsysinput=sys.stdin.readline T=int(input())for_inrange(T):n,k=map(int,input().split())s=list(input().strip())tot=[0]*26forcins:tot[ord(c)-97]+=1whilek>0:k-=1cnt=[0]*26foriinrange(n):c=ord(s[i])-97x=cnt[c]y=tot[c]-cnt[c]-1ifx==y:tot[c]-=1c=(c+1)%26tot[c]+=1s[i]=chr(c+97)cnt[c]+=1print("".join(s))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',()=>{letidx=0;letT=Number(input[idx++]);letout=[];while(T--){let[n,k]=input[idx++].split(' ').map(Number);lets=input[idx++].split('');lettot=newArray(26).fill(0);for(letcofs){tot[c.charCodeAt(0)-97]++;}while(k--){letcnt=newArray(26).fill(0);for(leti=0;i<n;i++){letc=s[i].charCodeAt(0)-97;letx=cnt[c];lety=tot[c]-cnt[c]-1;if(x===y){tot[c]--;c=(c+1)%26;tot[c]++;}s[i]=String.fromCharCode(c+97);cnt[c]++;}}out.push(s.join(''));}console.log(out.join('\n'));});Go
packagemainimport("bufio""fmt""os")funcmain(){in:=bufio.NewReader(os.Stdin)out:=bufio.NewWriter(os.Stdout)deferout.Flush()varTintfmt.Fscan(in,&T)forT>0{T--varn,kintfmt.Fscan(in,&n,&k)varsstringfmt.Fscan(in,&s)arr:=[]byte(s)tot:=make([]int,26)fori:=0;i<n;i++{tot[arr[i]-'a']++}fork>0{k--cnt:=make([]int,26)fori:=0;i<n;i++{c:=int(arr[i]-'a')x:=cnt[c]y:=tot[c]-cnt[c]-1ifx==y{tot[c]--c=(c+1)%26tot[c]++}arr[i]=byte(c+'a')cnt[int(arr[i]-'a')]++}}fmt.Fprintln(out,string(arr))}}
