查看: 271|回复: 4

[JavaSE] POJ-2159-Ancient Cipher-解题报告

[复制链接]

该用户从未签到

发表于 2017-12-22 22:42:51 | 显示全部楼层 |阅读模式
题意是说第一行字符串能否由第二行字符串经过“替代”和“位置转换”后得到。
做题时,实际上只统计两个字符串的各字符出现的“次数”是否相同即可(不必计较这相同次数是否字符也相同)。

算法思想如下:
1)读入两行字符串;
2)分别统计这两行字符串中每个字符出现的次数,并将其结果存在num1[26], num2[26]数组;
3)对上述两个数组进行降序排序;
4)比较两个数组是否相同:若相同,输出“YES”;若不同,输出“NO”。


C-sharp代码

  • #include <iostream>  
  • #include <string>  
  • #include <stdlib.h>  
  • #define MAX_LINE_SIZE 100  
  •   
  • using namespace std;  
  •   
  • int cmp(const void* a, const void* b) {  
  •     return -(*(int*)a - *(int*)b);  
  • }  
  •   
  • int main()  
  • {  
  •     string line1, line2;  
  •     cin >> line1 >> line2;  
  •       
  •     const char *line1Char = line1.c_str();  
  •     const char *line2Char = line2.c_str();  
  •       
  •     int len = line1.length();  
  •       
  •     int a[MAX_LINE_SIZE], b[MAX_LINE_SIZE]; //checked tag  
  •     int num1[26], num2[26];  
  •       
  •     for(int i = 0; i < 26; i++) {  
  •         num1 = 0;  
  •         num2 = 0;  
  •     }  
  •       
  •     for(int i = 0; i < MAX_LINE_SIZE; i++) {  
  •         a = 0;  
  •         b = 0;  
  •     }  
  •       
  •     for(int i = 0; i < len; ++i) {  
  •         if(a == 1) continue;  
  •         num1[line1Char - 'A']++;  
  •         a = 1;  
  •          
  •         for(int j = i + 1; j < len; ++j) {  
  •                 if(a[j] == 1) continue;  
  •                 if(line1Char == line1Char[j]) {  
  •                         num1[line1Char - 'A']++;  
  •                         a[j] = 1;  
  •                 }  
  •         }  
  •     }  
  •       
  •     for(int i = 0; i < len; ++i) {  
  •         if(b == 1) continue;  
  •         num2[line2Char - 'A']++;  
  •         b = 1;  
  •          
  •         for(int j = i + 1; j < len; ++j) {  
  •                 if(b[j] == 1) continue;  
  •                 if(line2Char == line2Char[j]) {  
  •                         num2[line2Char - 'A']++;  
  •                         b[j] = 1;  
  •                 }  
  •         }  
  •     }  
  •       
  •     qsort(num1, 26, sizeof(num1[0]), cmp);  
  •     qsort(num2, 26, sizeof(num2[0]), cmp);  
  •       
  •     int eqTag = 1;  
  •     for(int i = 0; i < 26; ++i) {  
  •         if(num1 == num2) continue;  
  •         else {  
  •                 eqTag = 0;  
  •                 break;  
  •         }  
  •     }  
  •       
  •     if(eqTag == 1)  
  •         cout << "YES" << endl;  
  •     else  
  •         cout << "NO" << endl;  
  •   
  •     return 0;  
  • }  



您需要登录后才可以回帖 登录 | 注册青鸟豆号

本版积分规则

Copyright 1999-2018 Beijing Aptech Beida Jade Bird Information Technology Co.,Ltd

北大青鸟IT教育 北京阿博泰克北大青鸟信息技术有限公司 版权所有

京ICP备11045574号-3 京公网安备11010802013845号

快速回复 返回顶部 返回列表