1.一个字符串，你可以在这个字符串后面拼接若干个任意字符，使得这个字符串成为回文串。
回文串，即字符串从左到右，从右到左读是一样的。
比如字符串abcbc,你可以在最后拼接2个字符ba，使得字符串变为回文串abcbcba，
现在给你一个只含英文小写字母的字符串，请问在后面拼接多少个字符会使得其变成回文串。
后面拼接的字符都是与最前面的字符匹配,所以从前往后枚举看从第几个字符开始的子串是回文串. for(int i=0;;++i) 当匹配成功时退出循环,前面共有i个字符要在后面补上与之对应的字符
for(int j=i,k=len-1;j<k;++j,--k)
{
if(s[j]!=s[k]) {flag=0;break;}
}
2.给你一个只含有英文小写字母的字符串，你可以无限次交换任意相邻的两个字符，请问是否能将字符串变为回文串。 所谓“回文串”，就是字符串从左到右读，和从右到左读是一样的字符串。
如果字符串长度为偶数,那么判断每个字符出现次数是否为偶数;如果字符串长度为奇数,判断是否仅有一个字符出现了奇数次
3.一个只含小写英文字母的字符串 求一个字符串 ，长度与它 相同，其第 i位的字符为到它 的第i 位出现数量最多的字符，如果多个字符的数量相同，则取最早达到这个数量的的字符。
前缀和求每个字符出现的次数,用一个变量cur记录到当前位置出现数量最多的字符和出现次数cnt,然后遍历26个字符,如果>cnt,就更新.然后每次把这个字符写入一个字符数组中
4.一个只含小写英文字母的字符串，你每个回合可以把其中的一种字符换成另外一种，请问最少多少个回合你能得到由同一种字符组成的字符串？
每次换,相当于合并两种类型的字符为一堆.假设一共有n种字符,最后全为一种字符,说明合并了n-1次
5.给一个字符串，请判断字符串是否出现了所有的英文字母（不区分大小写）。
统计即可,大写和小写判断好,它们都属于同一个cnt数组下标
6.当你看到这个题目的时候，你是否觉得虽然有点怪，但是也不会读错了？ 如果一个单词的首尾字母是一样的，中间的字母只是交换了顺序的话，人很容易“自动”纠错成正确的单词。 现在给你一个单词和其正确的字母排列顺序，请问是否符合上面的规则，让人能很容易自动“纠错”。
如果两个字符串一致，输出“Equal”；如果可以自动“纠错”，输出“Yes”，否则输出“No”。
strcmp判断是否相同,然后判断首尾是否相同,相同的话在判断中间字符出现的次数是否完全相同
7.如果一个字符串只含限定的字符集，我们称这个字符串是好的。现在给一个字符串和字符集，请找出好的字符子串的最长长度。
滑动窗口:
bool judge(char x); //判断某个字符是否在限定的字符集里面
int max=0;
int l=0,r=0;
while(r<len)
{
if(judge(s[r]) {++r;if(r-l+1>max) {max=r-l+1;}}
else {++r;l=r;}//l=原来的r+1;不用++r会死循环
}
int pos=0;
int cur=0,max=0;
while(pos<len)
{
if(judge(s[pos]) {++cur;if(cur>max) {max=cur;}}
else {cur=0;}
++pos;
}
8.一个 n个字母的序列，按大写字母顺序，从'A'开始，一共 n个字母。
然后你可以对字符进行左循环位移或者右循环位移。
比如一行字符一开始是ABCD，循环左移1位，变成BCDA; 如果再循环右移2位，那么变成DABC
请输出操作结束以后的字母序列。
输入ci表示操作 ==0不操作,<0左移,>0右移
i)直接操作即可,左移先记录下第一个字母,然后让s[i]=s[i+1],最后s[n-1]=记录下的这个,右移则s[i]=s[i-1],也要先记录先最后一个字母
ii)可记录下移动操作后第一个字符的位置,然后循环输出,记录下偏移量,左移相当于偏移量加ci然后%n,右移相当于偏移量+(n-ci),然后%n
9.如果一个长度为2n的字符串a1~a2n，满足ai=a(i+n)，我们称这样的字符串为"co-string"。 现在给你一个只含英文小写字母的长度为len字符串，请找出其最长的"co-string"子串的长度。
虽然是找最长字串,但滑动窗口没有任何优势,因为ai=a(i+n)与子串长度有关
int res;
for(res=len/2;res;--res)
{
for(int begin=0;begin+res*2<=len;++begin)
{
bool flag=1;
for(int j=begin;j<begin+res;++j)
{
if(s[j]!=s[j+res]) {flag=0;break;}
}
if(flag) {break;}
}
}
res<<=1;
~ ~ ~
10.我们可以简单地替换字符成另外一个字符来进行加密。
比如字符串”eric”，我们将e替换成a,r替换成b,i替换成c,c替换成d，那么字符串就变成了”abcd”。
但是我们不能将其替换成”aabc”，因为这样，e和r都被替换成了a，我们无法解密这个字符串。
同样我们也不能将字符串”aa”，替换成”bc”，因为a被替换成了两个不同的字符。
现在给你一个明文（加密前的字符串），一个密文（加密后的字符串），请问它们是由某种替换加密得到的吗？。
不能直接比较每个字符出现的次数是否完全相同,因为只能替换不能改变排列顺序(重排),如aab与abb
直接按题意不能原字符串中的两种字符映射成同一种,或者原字符串一种字符被映射成两种.判断一种字符映射成两种比判断两种字符被映射成同一种容易,所以考虑判断加密字符串是否存在一种字符映射成两种字符
即建立起双射关系
if(lena!=lenb) ->NO
char reflect1[128]={0},reflect2[128]={0};
bool flag=1;
for(int i=0;i<len;++i)
{
if(reflect1[a[i]]==0) {reflect1[a[i]]=b[i];}
else if(reflect1[a[i]]&&reflect1[a[i]]!=b[i]) {flag=0;break;}
if(reflect2[b[i]]==0) {reflect2[b[i]]=a[i];}
else if(reflect2[b[i]]&&reflect2[b[i]]!=a[i]) {flag=0;break;}
}
11.一个只含小写英文字母的字符串，你可以删除任意一段字符串，这样你可以得到一个新的字符串。
比如aabbcc，你可以得到abbcc,aabcc,aabbc,bbcc,abcc,aacc,aabc,aabb,bcc,acc,aac,aab,cc,ac,aa,c,a，一共17种。
现在给你一个字符串，请问你可以得到多少种不同的字符串。
先按照删除的长度来枚举,不同长度的字符串一定不同.接着按照删除起点枚举,并去重.
#include<stdio.h>
#include<string.h>
#include<stdbool.h>
int len;
char s[155];
char tmp[155];
char res[155][155];
int solve(int dellen)
{
int cnt=0;
for(int begin=0;begin+dellen<=len;++begin)//删除起点
{
memcpy(tmp,s,begin);//从0到begin-1共begin个
strcpy(&tmp[begin],&s[begin+dellen]);//前面写入从0到begin-1
bool flag=0;
for(int i=0;i<cnt;++i) {if(strcmp(tmp,res[i])==0) {flag=1;break;}}//写入时就去重
if(flag) {continue;}
strcpy(res[cnt++],tmp);
}
return cnt;
}
12.一个字符串 ，我们定义 Sk为将S 重复k 次拼接的字符串。
现在有一个字符串 ，请问最少修改多少个字符，可以使得它成为某个字符串的幂次（幂次大于1）。
因为拼接是从前往后进行的,所以枚举这个字符串的长度就可以,起点默认是s[0]
然而可以任意修改,那么这个字符串也可以被修改,统计所有幂次每个位置上出现的最多的字符串,然后把其他的字符串都改成这一种
while(scanf("%s",s)!=EOF)
{
int len=strlen(s);
int min=10010;
for(int perlen=1;perlen<=len/2;++perlen)
{
if(len%perlen) {continue;}
int ttot=0,slice=len/perlen;
for(int pos=0;pos<perlen;++pos)
{
int cnt[26]={0};
for(int per=0;per<slice;++per)
{
++cnt[s[per*perlen+pos]-'a'];
}
int max=cnt[0];
for(int i=1;i<26;++i) {if(cnt[i]>max) {max=cnt[i];}}
ttot+=slice-max;
}
if(ttot<min) {min=ttot;}
}
printf("%d\n",min);
}
13.两个等长的只含英文小写字母的字符串T和C，你可以进行下面四种操作：
让其中一个字符串整体循环左移1位，比如abc变成bca 让其中一个字符串整体循环右移1位，比如abc变成cab 让其中一个字符串的某个字符按字典序顺序变成下一个字符，比如a变成b,z变成a。 让其中一个字符串的某个字符按字典序顺序变成上一个字符，比如a变成z,z变成y。 请问最少多少次操作可以将T变成C?
右移i位相当于左移len-i位,左移同理;连续变成下一个字符i次相当于连续变成上一个字符26-i次
枚举左移i次(0到len-1),判断每个对应位置的字符差的绝对值k,然后min(k,26-k),求和后,再看是左移还是右移好min(i,26-i),最后相加即可
14.现在给你两个字符串，请求他们的共同的子串有多少种
strstr(char a[],char b[])在a中找有没有b(b是a的子串),没有则返回NULL
int substr(int len)//len枚举到min(lena,lenb)
{
int cnt=0;
for(int i=0;i+len<=lenb;++i)
{
strncpy(tmp,&b[i],len);
bool flag=1;
for(int j=0;j<cnt;++j)
{
if(strcmp(tmp,res[i])==0) {flag=0;break;}
}
if(flag) {strcpy(res[cnt++],tmp);}
}
return cnt;
}
不同长度的子串一定不同,每次枚举b中一种长度的子串,然后看他是不是a的子串
15.一个只含小写英文字母的字符串，各个字符出现的次数为 。求 中出现次数最多的数及其字符。比如字符串“abcdd”，‘a’,‘b’,‘c’都出现 次，‘d’出现 次，所以 出现次数最多。 如果存在多个相同的最多出现次数，输出字母小的那个次数。比如字符串“aaabbccddd”,3个‘a’，2个‘b’，2个‘c’,3个‘d’,3和2都出现2次，这时因为‘a’最小，输出”3 a d”。
统计每个字符出现次数,然后统计每个字符出现次数的出现次数(两层for循环遍历哪些字符出现次数与这个字符相等),找到最大的,然后从字母小到字母大枚举,如果有出现次数是最大的出现次数的出现次数,那么就记录下这个出现次数并输出,然后按从字母小到字母大枚举出现次数等于记录下的那个出现次数的字符
16.Alice的记忆力不太好，如果一个句子中含的单词（每个单词之间用一个空格隔开）数量超过10，或者句子中字母种类（不区分大小写）超过10个，她就会记不住。现在给你若干个句子，请写个程序判断一下Alice是否能记住这些句子。
注意是单词数量而不是种类数
while(gets(s)!=NULL)来获取一行,>=10个空格或者有10种字母(注意大小写)输出No
17.如果一个字符串 ,通过交换其中字符的位置,可得到另外一个字符串 ,我们称这两个字符串是“可变换”的。
比如字符串"abc"，交换其中字符的位置，可以得到"acb","bac","bca","cab","cba"其他五个字符串。 这 个字符串是属于同一组可变换字符串。
现在给你n 个字符串,请找出含可变换字符串最多的一组，如果存在多个组存在相同数目的可变换字符串，找出含在输入中最早出现的字符串的一组。
判断两个字符串是否所有字符出现次数都完全相同,相同输入同一组可变换字符串,每再输入一个字符串,找到前面第一个和他同一组的字符串,并把其前面那组对应的cnt++,然后标记这一组字符串属于前面那一组,然后break;最后找到最大的cnt并输出后面所有标记属于他的字符串
或者全部输入完后和上题一样两层循环枚举
18.有些字符写在纸上，如果你把纸转 ，它会变成另外一个字符。
比如字母 ，会变成 。
现在给你一个存在翻转关系的字符表(如下表)和若干字符串，请问其翻转以后的字符串是什么？
要注意翻转是相互的,A->B,则B->A
19.有一个通话的记录，请找出联系最多的联系人名字。
输入
第一行是一个整数N，表示样例的个数。
每个样例从”START”开始，”END”结束，其间每行一个联系人的名字，名字都是小写英文，长度不超过16个字符，联系人数不超过20人。
输出
每行输出一个样例的结果，如果有多个名字符合条件，请输出字典序最小的那个人的名字。
输入START(strcmp(s,"START")==0) continue;清空一些数组,开始输入联系人;输入END开始找答案
每再输入一个联系人,判断前面(tmp数组)有没有,有的话前面对应的cnt++,没有的话添加到tmp数组中,最后找最大cnt,然后把所有==max的存下来,然后找最小字典序的
20.如果字符串B的尾部字符串和另外一个字符串C的头部字符串是相同的，那我们可以把它们拼接在一起，组成一个新的字符串A，我们叫A是由B和C连接而成的。 比如字符串”abc”和字符串”bca”,可以连接成字符串”abca”。现在给你两个字符串，求其能连接产生的最短的字符串。输出字典序最小的那个
从大到小枚举拼接的长度,用双指针判断某个字符串末尾和另一个字符串开头是否相同如果A可以和B拼,B也可以和A拼,就比较字典序
#include<stdio.h>
#include<string.h>
#include<stdbool.h>
int main()
{
char a[205],b[205];
for(;;)
{
if(scanf("%s",a)==EOF) {break;}
scanf("%s",b);
int lena=strlen(a),lenb=strlen(b);
int can=(lena<=lenb ? lena : lenb);
for(;can;--can)
{
bool flaga=1;
for(int p=lena-can,q=0;q<can;++p,++q)
{
if(a[p]!=b[q]) {flaga=0;break;}
}
bool flagb=1;
for(int p=lenb-can,q=0;q<can;++p,++q)
{
if(b[p]!=a[q]) {flagb=0;break;}
}
if(!flaga && !flagb) {continue;}
char tmpa[405],tmpb[405];
if(flaga&&flagb)
{
memcpy(tmpa,a,lena);
strcpy(&tmpa[lena],&b[can]);
memcpy(tmpb,b,lenb);//可改成循环,复制时变量名不要改混了
strcpy(&tmpb[lenb],&a[can]);
if(strcmp(tmpa,tmpb)<0) {puts(tmpa);}
else {puts(tmpb);}
}
else if(flaga)
{
memcpy(tmpa,a,lena);
strcpy(&tmpa[lena],&b[can]);
puts(tmpa);
}
else
{
memcpy(tmpb,b,lenb);
strcpy(&tmpb[lenb],&a[can]);
puts(tmpb);
}
break;
}
if(can==0)
{
if(strcmp(a,b)<0) {printf("%s%s\n",a,b);}
else {printf("%s%s\n",b,a);}
}
}
return 0;
}
京公网安备 11010502036488号