UVA 1339 Ancient Cipher——快速排序

UVA 1339 Ancient Cipher——快速排序

算法：

字母可以重排，因此字母的位置并不重要，重要的是字母出现的次数；

因此我们可以用两个数组a[26],b[26]分别记录两个字符串中各字母出现的次数，然后进行排序，若排序之后的结果相同，则证明两个字符串之间存在一一映射关系；

注意，题目需要调用stdlib.h里的快速排序函数qsort，

int comInc(const void *a, const void *b) { return *(int *)a - *(int *)b; } int compDec(const void *a, const void *b) { return *(int *)b - *(int *)a; } 递增： qsort(a, len, sizeof(a[0]), compInc); 递减： qsort(b, len, sizeof(b[0]), compDec);

这是快速排序的原理：

#include #include #include int comInc(const void *a, const void *b){ return *(int *)a - *(int *)b;}int main(){ int i,j; int len; char str1[105],str2[105]; int a[26], b[26]; while( gets(str1)!=NULL ){ gets(str2); len=strlen(str1); memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for(i = 0; i < len; ++i){ a[(int)(*(str1+i) - 'A')]++; b[(int)(*(str2+i) - 'A')]++; } qsort(a,26,sizeof(a[0]),comInc); qsort(b,26,sizeof(b[0]),comInc); for(i = 0; i < 26; ++i){ if(a[i]!=b[i]) break; } if(i==26) printf("YES\n"); else printf("NO\n"); }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。