POJ1002 TLE求助！
代码有点长，delHyp（）是删除输入串中的‘-’，changeStr（）是全部转为‘0’-‘9’之间的字符，转换后之接冒泡排序的，可是一直超时；后来换了qsort（）之后还是TLE，实在不知道什么地方效率低，还望高手指点……
PS:总是很喜欢C++的动态分配，感觉这样空间不会浪费，不知道是不是因为这个耗费了太多时间哦？
#include <iostream>
#include <string>
using namespace std;
void changeStr(string & a)
{
int i = 0;
int len = a.length();
for (i = 0; i < len; i++)
{
if (a[i] == 'A' || a[i] == 'B' || a[i] == 'C')
a[i] = '2';
else if (a[i] == 'D' || a[i] == 'E' || a[i] == 'F')
a[i] = '3';
else if (a[i] == 'G' || a[i] == 'H' || a[i] == 'I')
a[i] = '4';
else if (a[i] == 'J' || a[i] == 'K' || a[i] == 'L')
a[i] = '5';
else if (a[i] == 'M' || a[i] == 'N' || a[i] == 'O')
a[i] = '6';
else if (a[i] == 'P' || a[i] == 'S' || a[i] == 'R')
a[i] = '7';
else if (a[i] == 'T' || a[i] == 'U' || a[i] == 'V')
a[i] = '8';
else if (a[i] == 'W' || a[i] == 'X' || a[i] == 'Y')
a[i] = '9';
}
}
void delHyp(string & a)
{
string::iterator it;
for (it = a.begin(); it <= a.end(); it++)
{
if (*it == '-')
a.erase(it);
}
}
int main()
{
int n;
cin >> n;
string *str = new string[n];
string *reStr = new string[n];
int *flagStr = new int[n];
int i = 0;
for (i = 0; i < n; i++)
{
cin >> str[i];
delHyp(str[i]);
changeStr(str[i]);
flagStr[i] = 0;
}
int j = 0;
int Gflag = 0;
for (i = 0; i < n; i++)
{
if (flagStr[i] == 0)
{
for (j = i + 1; j < n; j++)
{
if (str[i] == str[j])
{
flagStr[i]++;
flagStr[j] = -1;
Gflag = 1;
}
}
}
}
if (Gflag == 0)
cout << "No duplicates." << endl;
else
{
j = 0;
for(i = 0; i < n; i++)
{
if (flagStr[i] > 0)
{
reStr[j] = str[i];
flagStr[j] = flagStr[i];
j++;
}
}
int reStrlen = j;
string temp;
int flagTmp;
for ( i = 0; i < reStrlen; i++)
{
for (j = i + 1; j < reStrlen; j++)
if (reStr[i] > reStr[j])
{
temp = reStr[i];
reStr[i] = reStr[j];
reStr[j] = temp;
flagTmp = flagStr[i];
flagStr[i] = flagStr[j];
flagStr[j] = flagTmp;
}
}
for (i = 0; i < reStrlen; i++)
{
for (j = 0; j < 3; j++)
{
cout << reStr[i][j];
}
cout << '-';
for (j = 3; j < 7; j++ )
cout << reStr[i][j];
cout << ' ' << flagStr[i] + 1 << endl;
}
}
delete []flagStr;
delete []reStr;
delete []str;
return 0;
}
[解决办法]
http://topic.csdn.net/u/20100421/15/a4f5b5b0-92ea-446e-b0f3-7b0dc92490a5.html
- C/C++ code
#include<iostream>using std::cin;using std::cout;using std::endl;#ifdef DEBUG#include<string>using std::string;using std::freopen;string input_file_name = __FILE__;#endif//here add other file need to included, and declare namespace need to use.#include<stdlib.h>//here declare global variables;char dictionary[26] = {2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 0, 7, 7, 8, 8, 8, 9, 9, 9, 0};char nos[100002][50];//here add funtions.void format_number(char* no){ int len = strlen(no); //printf("%s\n", no); int count = 0; for(int i = 0; i < len; ++i) { if(no[i] >= 'A' && no[i] <= 'Z') { no[i] = '0' + dictionary[no[i] - 'A']; } else if(no[i] == '-') { ++count; } if(no[i] != '-') no[i - count] = no[i]; } no[len - count] = '\0'; //printf("%s\n", no);}int cmp(const void* a, const void* b){ return strcmp((char*)a, (char*)b);}int main(int argc, char* argv[]){ #ifdef DEBUG if(!freopen((input_file_name.substr(0, input_file_name.size() - 4) + ".in").c_str(), "r", stdin)) { cout << "input data error, not found input file." << endl; return -1; } #endif //here add code for solve problem. int n = 0; //input scanf("%d", &n); for(int i = 0; i <= n; ++i) { gets(nos[i]); format_number(nos[i]); } qsort(nos, n + 1, 50, cmp); //output int count = 0; bool flag = false; for(int i = 0; i <= n; ++i) { if(strcmp(nos[i], nos[i + 1]) == 0) ++count; else { if(count > 0) { printf("%c%c%c-%c%c%c%c %d\n", nos[i - 1][0], nos[i - 1][1], nos[i - 1][2], nos[i - 1][3], nos[i - 1][4], nos[i - 1][5], nos[i - 1][6], count + 1); flag = true; } count = 0; } } if(!flag) { printf("No duplicates.\n"); } return 0;}
[解决办法]
字符到数字的转换，用if-else是不行的.
7位数的号码，直接bitmap就可以了，别排序.
- C/C++ code
#include <stdio.h>int main( ){ static int i, j, k, n, hash[10000000]={0}; char tel[32], map[256]; map['A'] = map['B'] = map['C'] = 2; map['D'] = map['E'] = map['F'] = 3; map['G'] = map['H'] = map['I'] = 4; map['J'] = map['K'] = map['L'] = 5; map['M'] = map['N'] = map['O'] = 6; map['P'] = map['R'] = map['S'] = 7; map['T'] = map['U'] = map['V'] = 8; map['W'] = map['X'] = map['Y'] = 9; for (i='0'; i<='9'; i++) map[i] = i-'0'; scanf("%d", &n); while (n--) { scanf("%s", tel); for (i=k=0,j=1000000; tel[i]; i++) { if (tel[i]=='-') continue; k += map[tel[i]] * j; j /= 10; } hash[k]++; } for (i=j=0; i<10000000; i++) if (hash[i]>1) { j++; printf("%03d-%04d %d\n", i/10000, i%10000, hash[i]); } if (j==0) puts("No duplicates.");}
[解决办法]
for (it = a.begin(); it <= a.end(); it++)错了，
改成
for (it = a.begin(); it < a.end(); it++)
给你两个建议：
1、加强代码的可读性以及软件的用户体验，要是没有你的说明谁都搞不懂这个软件在干啥
2、使用之前最好仔细看看STL的用法，不然以后你还会面对同样的奇怪问题
以上
[解决办法]