问题要求如下:
输入格式:
输入第一行是一个正整数 N (1 <= N <= 100000),表示一共有 N 个用户名。接下来有 N 行,每一行是一个用户名,长度不超过 100,均由大写字母和小写字母组成。
输出格式:
请按照输入顺序输出,如果用户名在前面出现过则输出“Yes”,否则输出“No”,一行输出一个。
我的解答如下,并不能被系统AC,求问为什么。。。测试数据能过
#include
#include
#include
using namespace std;
class HashTable
{
private:
int size;
string* elem;
public:
HashTable()
{
size=200000;
elem=new string[size];
for(int i=0;i
{
elem[i]="#";
}
}
~HashTable()
{
delete[] elem;
}
int hash(string& index)
{
int code=0;
for(size_t i=0;i
{
if(isupper(index[i]))
index[i]=index[i] - 'A' + 'a';
}
for(size_t i=0;i
{
code=(code*256+index[i]+128)%size;
}
return code;
}
bool search(string& index, int& pos, int& times)
{
pos=hash(index);
times=0;
while(elem[pos]!="#" && elem[pos]!=index)
{
times++;
if(times
{
pos=(pos+1)%size;
}
else
{
return false;
}
}
if(elem[pos]==index)
{
return true;
}
else
{
return false;
}
}
int insert(string& index)
{
int pos,times;
if(search(index,pos,times))
{
return 2;
}
else if(times
{
elem[pos]=index;
return 1;
}
else
{
recreate();
return 0;
}
}
void recreate()
{
string* temp_elem;
temp_elem=new string[size];
int copy_size=size;
for(int i=0;i
{
temp_elem[i]=elem[i];
}
delete[] elem;
size=size*2;
elem=new string[size];
for(int i=0;i
{
elem[i]="#";
}
for(int i=0;i
{
if(temp_elem[i]!="#")
{
insert(temp_elem[i]);
}
}
delete[] temp_elem;
}
};
int main()
{
HashTable hashtable;
int n, temp_pos, temp_times;
cin>>n;
string buffer;
cin>>buffer;
hashtable.insert(buffer);
cout<<"NO"<
for(int i=0;i
{
cin>>buffer;
if(hashtable.search(buffer,temp_pos,temp_times))
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
hashtable.insert(buffer);
}
return 0;
}