POJ1002 Phone Number Duplication

By | 2012 年 7 月 14 日

上周三做了一道简单的poj题目,但是虽然简单却有比较大的收获,主要有四点:
1.gets()比cin()快
2.cin()不自动吃掉’\n’,需要的话,用getchar()吃掉
3.printf(“%.3d”,anInt),不足3位在前面补0
4.时间问题,抓主要矛盾(线性搜索改为二叉树搜索),new操作都是次要的,链表比数组慢也是次要的

下面是代码:

<

pre class=”brush:cpp;auto-links:false”>
// 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[])
{
node *head = NULL;
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;
node *phoneNode = findNodeWithNumber(head, phoneNumber);
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;
head = phoneNode;
}
}
// cout<<“done”<<endl;
output(head);
if (!haveDuplication) {
cout<<“No duplicates.”<<endl;
}
return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注