不是字符串问题字节跳动笔试真题 3月21号 第一题题目内容对于长度为mmm的字符串t1t2...tmt_1t_2...t_mt1​t2​...tm​和整数i(1≤i≤m)i(1≤i≤m)i(1≤i≤m)我们将字符串fi(t)f_i(t)fi​(t)定义为以下内容的连接ttt的前⌊i2⌋\lfloor \frac{i}{2} \rfloor⌊2i​⌋个字符按字典序从小到大排序ttt整串按字典序从大到小排序;ttt除去前⌊i2⌋\lfloor \frac{i}{2} \rfloor⌊2i​⌋个字符外的剩余字符按字典序从小到大排序。现在对于长度为nnn的字符串s1s2...sns_1s_2...s_ns1​s2​...sn​你需要取出它的的全部长度为xxx的子串且令ixixix按照上方所述的步骤进行构造能构造出多少个不相同的新字符串定义子串为从原字符串中连续的选择一段字符(可以全选、可以不选)组成的新字符串。输入描述每个测试文件均包含多组测试数据。第一行输入一个整数T(1≤T≤100)T(1≤T≤100)T(1≤T≤100)代表数据组数每组测试数据描述如下第一行上输入两个整数n,x(1≤n≤100;1≤x≤n)n,x(1≤n≤100;1≤x≤n)n,x(1≤n≤100;1≤x≤n)代表字符串长度、和询问长度。第二行输入一个长度为nnn且由大小写字母混合构成的字符串sss代表初始串。输出描述在一行上输出一个整数代表构造出的新字符串数量。样例1输入2 5 4 bAbbb 7 3 nuhhhhh输出1 3说明对于第一组测试数据长度为444的不同子串有bAbbbAbbbAbb和AbbbAbbbAbbb:对于bAbbbAbbbAbb构造得到f4(bAbb)AbbbbAbbf4 (bAbb) Ab bbbA bbf4(bAbb)AbbbbAbb前i2\frac{i}{2}2i​个字符按字典序从小到大排序为AbAbAb整串按字典序从大到小排序为bbbAbbbAbbbA;除去前i2\frac{i}{2}2i​个字符外的剩余字符按字典序从小到大排序为bbbbbb。对于AbbbAbbbAbbb构造得到f4(Abbb)AbbbbAbbf4 (Abbb) Ab bbbA bbf4(Abbb)AbbbbAbb。题解和思路思路实现思路暴力枚举从前往后枚举长度为x的子串substr按照题意求对应f(t)字符串并使用集合进行结果去重。对每个字符子串进行下面处理A 取subStr的前x / 2字符并进行升序排序B 对完整subStr进行降序排序C: 取substr的[x / 2: x -1]片段进行升序排序拼接A B C并加入集合中。每组测试数据结果最终为集合大小。算法时间复杂度为O(nxlogx)C#includebits/stdc.husingnamespacestd;// 构造对应字符串stringconstruct(strings,intx){intns.size();intmn/2;// [x/2]片段string As.substr(0,m);sort(A.begin(),A.end());string Bs;// 降序sort(B.begin(),B.end(),greaterchar());// 去除前[x /2]string Cs.substr(m);sort(C.begin(),C.end());returnABC;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){intn,x;cinnx;string s;cins;unordered_setstringans;for(inti0;in-x;i){string subStrs.substr(i,x);ans.insert(construct(subStr,x));}coutans.size()endl;}}Javaimportjava.io.*;importjava.util.*;publicclassMain{// 构造对应字符串staticStringconstruct(Strings,intx){intns.length();intmn/2;// [x/2]片段char[]As.substring(0,m).toCharArray();Arrays.sort(A);char[]Bs.toCharArray();Arrays.sort(B);StringBuilderbDescnewStringBuilder(newString(B)).reverse();// 去除前[x/2]char[]Cs.substring(m).toCharArray();Arrays.sort(C);returnnewString(A)bDescnewString(C);}publicstaticvoidmain(String[]args)throwsException{BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));intTInteger.parseInt(br.readLine());while(T--0){String[]firstbr.readLine().split( );intnInteger.parseInt(first[0]);intxInteger.parseInt(first[1]);Stringsbr.readLine();HashSetStringansnewHashSet();for(inti0;in-x;i){StringsubStrs.substring(i,ix);ans.add(construct(subStr,x));}System.out.println(ans.size());}}}pythonimportsys# 构造对应字符串defconstruct(s,x):nlen(s)mn//2# [x/2]片段A.join(sorted(s[:m]))B.join(sorted(s,reverseTrue))# 去除前[x/2]C.join(sorted(s[m:]))returnABC datasys.stdin.read().strip().split()idx0Tint(data[idx])idx1ans_list[]for_inrange(T):nint(data[idx])idx1xint(data[idx])idx1sdata[idx]idx1ansset()foriinrange(n-x1):sub_strs[i:ix]ans.add(construct(sub_str,x))ans_list.append(str(len(ans)))print(\n.join(ans_list))Javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constlines[];rl.on(line,line{lines.push(line);});rl.on(close,(){constdatalines.join( ).trim().split(/\s/);letidx0;// 构造对应字符串functionconstruct(s,x){constns.length;constmMath.floor(n/2);// [x/2]片段constAs.substring(0,m).split().sort().join();constBs.split().sort().reverse().join();// 去除前[x/2]constCs.substring(m).split().sort().join();returnABC;}constTNumber(data[idx]);constoutput[];for(lett0;tT;t){constnNumber(data[idx]);constxNumber(data[idx]);constsdata[idx];constansnewSet();for(leti0;in-x;i){constsubStrs.substring(i,ix);ans.add(construct(subStr,x));}output.push(String(ans.size));}console.log(output.join(\n));});Gopackagemainimport(bufiofmtossort)// 构造对应字符串funcconstruct(sstring,xint)string{n:len(s)m:n/2// [x/2]片段A:[]byte(s[:m])sort.Slice(A,func(i,jint)bool{returnA[i]A[j]})B:[]byte(s)sort.Slice(B,func(i,jint)bool{returnB[i]B[j]})// 去除前[x/2]C:[]byte(s[m:])sort.Slice(C,func(i,jint)bool{returnC[i]C[j]})returnstring(A)string(B)string(C)}funcmain(){in:bufio.NewReader(os.Stdin)varTintfmt.Fscan(in,T)for;T0;T--{varn,xintfmt.Fscan(in,n,x)varsstringfmt.Fscan(in,s)ans:make(map[string]struct{})fori:0;in-x;i{subStr:s[i:ix]ans[construct(subStr,x)]struct{}{}}fmt.Println(len(ans))}}