# POJ1002 Phone Number Duplication

By | 2012 年 7 月 14 日

1.gets()比cin()快
2.cin()不自动吃掉’\n’，需要的话，用getchar()吃掉
3.printf(“%.3d”,anInt)，不足3位在前面补0
4.时间问题，抓主要矛盾（线性搜索改为二叉树搜索），new操作都是次要的，链表比数组慢也是次要的

<

// main.cpp
// POJ1002-PhoneNumberDuplication
// Created by Qiu Xiangyu on 12-7-10.
// gets()比cin()快
// cin()不自动吃掉’\n’，需要的话，用getchar()吃掉
// printf(“%.3d”,anInt)，不足3位在前面补0
// 时间问题，抓主要矛盾（线性搜索改为二叉树搜索），new操作都是次要的，链表比数组慢也是次要的

# include

//#include
using namespace std;

struct node{
long phoneNumber;
int repeatCount;
node leftChild;
node *rightChild;
node *parant;
};
inline int translateCode(char c)
{
if (c >= ‘0’ && c <= ‘9’) {
return c – ‘0’;
}
if (c >= ‘A’ && c <= ‘O’) {
int num = c – ‘A’;
return num / 3 + 2;
}
if (c == ‘P’ || c == ‘R’ || c == ‘S’) {
return 7;
}
if (c >= ‘T’ && c <= ‘V’) {
return 8;
}
if (c >= ‘W’ && c <= ‘Y’) {
return 9;
}
return -1;
}
inline node *findNodeWithNumber(node
startNode, long number)
{
if (startNode == NULL) {
return NULL;
}
if (startNode->phoneNumber == number) {
return startNode;
} else if (startNode->phoneNumber < number) {
if (startNode->rightChild == NULL) {
return startNode;
}
return findNodeWithNumber(startNode->rightChild, number);
} else {
if (startNode->leftChild == NULL) {
return startNode;
}
return findNodeWithNumber(startNode->leftChild, number);
}
}
bool haveDuplication = false;
inline void output(node *root)
{
if (root == NULL) {
return;
}
output(root->leftChild);

```if (root->repeatCount > 1) {
haveDuplication = true;
long phoNum = root->phoneNumber;
int first = phoNum / 10000;
int last = phoNum % 10000;
printf("%.3d-%.4d %d\n",first,last,root->repeatCount);
}

output(root->rightChild);```

}
int main(int argc, const char * argv[])
{
int totalNumber;
cin>>totalNumber;
getchar();
// cout<<“total:”<<totalNumber<<endl;
for (int iNumber = 0; iNumber < totalNumber; iNumber ++) {
char inputbuffer[500];
char *str = inputbuffer;
gets(str);
// cout<<aNumber<<endl;
// cout<<str;
long phoneNumber = 0;
int strLen = strlen(str);// aNumber.length();
// if (strLen == 0) {
// iNumber–;
// continue;
// }
for (int ichar = 0; ichar < strLen; ichar ++) {
char c = str[ichar];
if (c == ‘-‘) {
continue;
}
int num = translateCode(c);
if (num == -1) {
continue;
}
phoneNumber = 10 * phoneNumber + num;
}
// cout<<phoneNumber<<endl;
if (phoneNode) {
if (phoneNode->phoneNumber == phoneNumber) {
phoneNode->repeatCount ++;
} else if (phoneNode->phoneNumber < phoneNumber) {
node *parant = phoneNode;
node *child = new node();
child->phoneNumber = phoneNumber;
child->repeatCount = 1;
child->parant = parant;
parant->rightChild = child;
} else {
node *parant = phoneNode;
node *child = new node();
child->phoneNumber = phoneNumber;
child->repeatCount = 1;
child->parant = parant;
parant->leftChild = child;
}
} else {
phoneNode = new node();
phoneNode->phoneNumber = phoneNumber;
phoneNode->repeatCount = 1;