哈希!错误的答案,找不到
问题描述:
我在解决问题HASH IT时出错了。我无法弄清楚我错在哪里。有人可以提供一些我的代码失败的测试用例。感谢提前:)哈希!错误的答案,找不到
链接到我的代码
#include<bits/stdc++.h>
using namespace std;
int main(){
long long int t;
scanf("%lld",&t);
while(t--){
long long int x,i,f=0;
string s,s1;
map<long long int,string> m;
map<string,long long int> m1;
set<long long int> t;
scanf("%lld",&x);
for(i=0;i<x;i++){
s1="";
cin>>s;
long long int j,ans=0;
for(j=4;j<s.length();j++){
ans=(ans+(int)(s[j])*(j-3))%101;
s1+=s[j];
}
if(s[0]=='A'){
ans=(ans*19)%101;
// cout<<ans<<endl;
// cout<<m[ans]<<s<<endl;
if(m[ans].compare(s1)==0 || m[m1[s1]]==s1){ continue; }
else if(m[ans]==""){
m[ans]=s1;
m1[s1]=ans;
f++;
t.insert(ans);
}
else{
long long int count=1;
while(count!=20){
if(m[(ans+(count*count)+(23*count))%101]==""){
m[(ans+(count*count)+(23*count))%101]=s1;
m1[s1]=(ans+(count*count)+(23*count))%101;
t.insert((ans+(count*count)+(23*count))%101);
f++;
break;
}
count++;
}
}
}
else{
if(m[m1[s1]]==s1){
m[m1[s1]]="";
m1[s1]=-1;
--f;
}
else if(m[m1[s1]].length()!=0){
m[m1[s1]]="";
m1[s1]=-1;
f--;
}
}
}
printf("%lld\n",f);
set<long long int>::iterator it;
for(it=t.begin();it!=t.end();it++){
if(m[*it].length()!=0 && m1[m[*it]]!=-1)
cout<<*it<<":"<<m[*it]<<endl;
}
}
return 0;
}
答
你一直在负责实施哈希表 - 这包括定义数据类型和函数来处理这些类型。我不知道你在做什么。
首先定义一个散列表 - 通过定义两种类型来做到这一点;一个表格类型和一个插槽类型。
typedef struct table table;
typedef struct slot slot;
该表是槽的一个简单的数组:
struct table {
slot slots[101];
}
槽是数据的相关的一个限定串的集合:
struct slot {
char status;
int hash;
char key[16];
};
甲时隙要么未使用的,删除或根据状态的值使用。 槽的散列值是密钥串上散列函数的值。 密钥字符串存储在密钥变量中。
要在表格中存储字符串,只需找到合适的插槽并覆盖数据。要做到这一点,搜索所有的插槽(使用所描述的算法),直到找到一个未使用的插槽或已经匹配密钥的插槽。如果找不到,则查找已删除的插槽并覆盖该插槽。
要查找字符串,请逐步查看表格 - 如果某个槽匹配密钥,则返回它,如果找到未使用的槽或找到已删除的匹配槽,请停止该过程。如果你已经看过所有的插槽,那就停下来。
要删除一个字符串,首先找到它,然后将状态设置为删除。
您没有机会获得低质量的警告,甚至可能是因为没有正确格式化代码而导致您工作的区块? – Deduplicator 2014-09-13 19:55:07
请提出具体问题。这应该做什么,它做错了什么? – Barmar 2014-09-13 19:55:44