10个过了9个最后一个答案一样就是没过,不懂了
查看原帖
10个过了9个最后一个答案一样就是没过,不懂了
838527
LjL67172377楼主2022/11/11 21:36

10个过了9个 见下图9个ac下载数据最后结果是对的 代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int m=19997;
string strHash[m]{};

int h1(string k){
	int ans=0;
	int bitWeight=1;
	for(int i=0;i<k.length();i++){
		int bitValue=int(k[i]);
		ans=(ans+bitValue*bitWeight)%m;
		bitWeight=(bitWeight*128)%m;
	}
	return ans;
}
int h2(string k){
	int ans=0;
	int bitWeight=1;
	for(int i=0;i<k.length();i++){
		int bitValue=int(k[i]);
		ans=(ans+bitValue*bitWeight)%(m-1);
		bitWeight=(bitWeight*128)%(m-1);
	}
	ans+=1;
	return ans;
}
int h(string k,int i){
	return (h1(k) + i*h2(k)) %m;
}

void putInHash(string toPush){
	for(int i=0;i<m;i++){
		int place =h(toPush,i)-1;
		if(strHash[place]==""){
			strHash[place]=toPush;
			//cout<<"placed one string at"<<place<<"\n";
			return;
			
		}
		if(strHash[place]==toPush) return;
	}
	//cout<<"error\n";
}

int checkHashAmount(){
	int amount=0;
	for(int i=0;i<m;i++){
		if(strHash[i]!="") amount++;
	}
	return amount;
}
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		string inNow;
		cin>>inNow;
		putInHash(inNow);
	}
	cout<<checkHashAmount();
}

用的是双重散列(就是用两个除法散列函数生成一个函数进行开放选址) 实在是不知道怎么回事了,大佬帮忙看看

2022/11/11 21:36
加载中...