最近在准备PAT，由于刚大二结束，还没学数据结构，就利用这个暑假自学了一下数据结构，然后啃那三本经典的紫书系列，今天看到紫书上的一个叫ancient cipher的东西，题目是这样的:
“给定两个长度一样且不超过100的字符串，判断是否能把其中一个字符串的各个字母重排，之后对26个字母做一个一一映射，使得两个字符串相同
例如，JWPUDJSTVP重排后可以得到WJDUPSJPVT，之后把每个字母映射到它的前面一个字母，得到VICTORIOUS，输入两个字符串，输出YES或者NO”
拿到题目，前前后后看了四遍，压根没看懂，心中OS:这什么玩意儿啊，说的是人话吗，
然后找遍了网上所有，说的都差不多，题都看不懂怎么继续啊，忽然想到这东西不是UVa OJ上的东西吗，我这刚好有账号，就上去搜了一下原题:
UVa 1339
看了原题大概懂了，重点来了啊:意思就是给你 俩字符串，只要长度相等，并且在第一个字符串映射完后得到的字符串与第二个字符串中不同的字符个数相等，就判断为可以互相转化，顺序无所谓。
这样一来，代码实现就很简单了，无非就是定义定义俩字符串数组，然后统计长度，遍历每一个字符并比较，最后输出yes，no就可以了
下面贴代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define maxn 100 + 10
int cmp(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
int main()
{
char a[maxn];
char b[maxn];
while(scanf("%s%s", a,b) != EOF)
{
int i;
int len = strlen(a);
int cnt1[26],cnt2[26];
memset(cnt1,0,sizeof(cnt1));
memset(cnt2,0,sizeof(cnt2));
for(i=0; i < len; i++)
{
cnt1[a[i] - 'A']++;
cnt2[b[i] - 'A']++;
}
//排序
qsort(cnt1,26,sizeof(cnt1[0]),cmp);
qsort(cnt2,26,sizeof(cnt2[0]),cmp);
for(i=0; i < 26; i++)
{
if(cnt1[i] != cnt2[i])
{
printf("NO\n");
return 0;
}
}
printf("YES\n");
}
return 0;
}
分析:
紫书上提供了一个叫qsort的函数，这个之前真的不知道，他需要用本程序一开头的那个cmp函数实现，所以在一开始需要调用stdlib.h这个头文件。
qsort可以帮你把字符串瞬间排列好还是很厉害的
UVa 1339
代码运行没有问题，然后进行测试:
UVa 1339
UVa 1339
都没问题，但是一旦字符串不相同字符个数不一样，
UVa 1339
他就报错并会退出。
至此，UVa1339就结束了，欢迎各路大神进行指点 ，这是我的第一篇文章，谢谢大家支持！
网友评论