首页 > 代码库 > POJ-1002 487-3279
POJ-1002 487-3279
【题目描述】
大写字母（除了Q、Z）映射到2~9，具有相同标准格式（###-####）的为相同号码。以标准格式，按字典升序输出重复的号码。
【思路分析】
1. 存储结构
为了加快查找速度，采用无冲突的哈希表存这些7位数，故需要 long hashTable[10000000] 来存储每个号码的出现次数。
由于号码的个数不超过100000个，用 long keys[200000] 来存储重复号码，keyn代表该数组中存放了多少条号码，最后需要在keys上进行快速排序。
以上两个数组，要写成全局变量，否则在主函数中会堆栈溢出。
2. 号码转换为数字（哈希键）
由于号码的首位对应数字的最高位，而数字确定是为7位数，故可以从数字的最高位开始存入，跳过连字符‘-’，最终得到7位数字作为哈希键。转换函数 Change2Number() 代码如下所示：
long Change2Number(string &strline){ long result = 0; int bit = 6; for (int i(0); i < strline.length(); i++) { char c = strline[i]; if (c >= ‘0‘ && c <= ‘9‘) { result += pow(10.0, bit--) * (c - ‘0‘); } else if (c >= ‘A‘ && c <= ‘P‘) { result += pow(10.0, bit--) * ((c-‘A‘)/3 + 2); } else if (c >= ‘R‘ && c <= ‘Y‘) { result += pow(10.0, bit--) * ((c-‘A‘-1)/3 + 2); } else if (c == ‘Q‘ || c == ‘Z‘) { continue; } } return result; }
3. 对号码记数
获得转换的7位数index后，对相应的hashTable[index]值加1（hashTable[…]初始为0）。若hashTable[index]的值已经为1，说明这是第二次遇到该号码，则将其加入keys数组中。
重复此过程直到号码读完，对keys数组进行快速排序（为了练习一下快排我的代码是自己写的），可以调用现有的程序qsort(数组, 大小, 单元大小, 比较函数)，如下代码所示：
qsort(keys, keyn, sizeof(long), cmp);int cmp(const void*a,const void*b)//快排自定义cmp { return *(int*)a-*(int*)b;}
4. 输出格式控制
如果keys中没有元素，则输出“No duplicates.”（后面的’.’不要漏了，这里我也WA了 = =!!）。
否则，一个个输出，由于键是长整型，如果直接输出，数字最前面若是0则无法输出，所以在输出时候要控制下格式，写成”%07d”。
char temp[10];sprintf(temp, "%07d", keys[i]); //写成"%07d"前面才会补零string resultline = temp;resultline.insert(3, "-");cout<<resultline<<" "<<hashTable[ keys[i] ]<<endl;
【小结】
这道题的知识点主要在于：无冲突的哈希表构建（写成全局变量），快速排序与格式输出控制。
唉，认真读题目很重要的！“No duplicates.”后面的.和输出格式都卡了我好久，差点就要放弃了，不过还是坚持下来，这周在这两题上花了好多时间。
【附：完整代码】
#include <iostream>#include <string>#include <cmath>using namespace std;long Change2Number(string &strline){ bool flag = true; long result = 0; int bit = 6; for (int i(0); i < strline.length(); i++) { char c = strline[i]; if (c >= ‘0‘ && c <= ‘9‘) { result += pow(10.0, bit--) * (c - ‘0‘); } else if (c >= ‘A‘ && c <= ‘P‘) { result += pow(10.0, bit--) * ((c-‘A‘)/3 + 2); } else if (c >= ‘R‘ && c <= ‘Y‘) { result += pow(10.0, bit--) * ((c-‘A‘-1)/3 + 2); } else if (c == ‘Q‘ || c == ‘Z‘) { continue; } } return result; }long Partition(long arraylist[], long low, long high){ long toBePosition = arraylist[low]; while (low < high) { while (low < high && arraylist[high] >= toBePosition) high--; arraylist[low] = arraylist[high]; while (low < high && arraylist[low] <= toBePosition) low++; arraylist[high] = arraylist[low]; } arraylist[low] = toBePosition; return low;}void QSort(long arraylist[], long low, long high){ if (low < high) { long pos = Partition(arraylist, low, high); QSort(arraylist, low, pos-1); QSort(arraylist, pos+1, high); }}long keys[200000];long hashTable[10000000];long keyn = 0;int main(){ int n; while (cin>>n) { keyn = 0; memset(hashTable, 0, sizeof(hashTable)); for (int i(0); i < n; i++) { string strline; cin>>strline; long index = Change2Number(strline); if (index >= 0) // there is no ‘Q‘ or ‘Z‘ in strline, add in hashTable { if (hashTable[index] == 1) { keys[keyn] = index; keyn++; } hashTable[index]++; } } if (keyn == 0) { cout<<"No duplicates."<<endl; //!! } else { QSort(keys, 0, keyn-1); for (int i(0); i < keyn; i++) { char temp[10]; sprintf(temp, "%07d", keys[i]); //!! string resultline = temp; resultline.insert(3, "-"); cout<<resultline<<" "<<hashTable[ keys[i] ]<<endl; } } } return 0;}
POJ-1002 487-3279