首页 > 其他分享 >【寻迹#3】 哈希与哈希表

【寻迹#3】 哈希与哈希表

时间:2024-09-01 20:26:35浏览次数:10  
标签:Hash ull int 寻迹 哈希 字符串 operatorname

哈希和哈希表

哈希算法是通过一个哈希函数 \(\operatorname H\) ,将一种数据(包括字符串、较大的数等)转化为能够用变量表示或是直接就可作为数组下标的数,通过哈希函数转化得到的数值我们称之为哈希值。通过哈希值可以实现快速查找和匹配。哈希算法具体应用有:字符串 \(\operatorname {Hash}\) 、哈希表。

一、字符串 \(\operatorname{Hash}\)

1.字符串匹配问题

寻找长度为 \(n\) 的主串 \(S\) 中的匹配串 \(T\) (长度为 \(m\) )出现的位置或次数的问题属于字符串匹配问题。朴素的想法是枚举所有起始的位置,再直接检查是否匹配。字符串 \(\operatorname {Hash}\) 的原理是直接比较长度为 \(m\) 的主串 \(S\) 的字串的哈希值与 \(T\) 的哈希值是否相等。

2.具体流程

如果我们用 \(O(m)\) 的时间直接计算长度为 \(m\) 的字符串的哈希值,总的时间复杂度并没有改观。所以需要用到滚动哈希的优化技巧。

所以我们选取两个互质常数 \(b\) 和 \(h\) ( \(b<h\) ),假设字符串 \(C=c_1c_2...c_m\) ,那么我们定义哈希函数 \(\operatorname H(C)=(c_1b^{m-1}+c_2b^{m-2}+...+c_mb^{0}) \bmod h\) 。仔细观察这个式子发现很像 \(b\) 进制下的某数字的展开。只不过这里将字符 \(c_i\) 看作为一个数字。

这一个过程是递推计算的,设 \(\operatorname H(C,k)\) 为前 \(k\) 个字符构成的字符串的哈希值,则: \(\operatorname H(C,k+1)=\operatorname H(C,k)\times b+c_{k+1}\)

举个例子:现有字符串 \(C=acda\) (为方便处理我们可以令 \(a\) 表示 \(1\) , \(b\) 表示 \(2\) ,以此类推),则:

\(\operatorname H(C,1)=1\)

\(\operatorname H(C,2)=H(C,1)\times b+c_2=1\times b+3\)

$\operatorname H(C,3)=H(C,2)\times b+c_3=1\times b^2+3\times b+4 $

$\operatorname H(C,4)=H(C,3)\times b+c_4=1\times b^3+3\times b^2+4\times b +1 $

通常题目要求的是判断主串的一段字符与另一个匹配串是否匹配,即判断字符串 \(C=c_1c_2...c_m\) 从位置 \(k+1\) 开始的长度为 \(n\) 的字串 \(C'=c_{k+1}c_{k+2}...c_{k+n}\) 与另一匹配串 \(S=s_1s_2...s_m\) 的哈希值是否相等,则等价于判断 \(\operatorname H(C')=\operatorname H(C,k+n)-\operatorname H(C,k)\times b^n\) 是否与 \(\operatorname H(S)\) 相等。

所以只需要预处理 \(b^n\) 既可以在 \(O(1)\) 的复杂度内得到任意字符串的子串哈希值,从而完成字符串匹配,那么上述字符串匹配问题的算法复杂度就为 \(O(n+m)\)

借助上面的例子,假设 \(S=cd\) ,那么当 \(k=1,n=2\) 时,

\(\operatorname H(C')=H(C,1+2)-H(C,1)\times b^2=3\times b+4\)

\(\operatorname H(S)=3\times b+4=H(C')\) ,所以就可以认为 \(C'\) 与 \(S\) 是匹配的。

可以将 \(b\) 一个较大的定质数,这样在使用 $\operatorname{unsigned} \operatorname{long} \operatorname{long} $ 类型计算时可以自然溢出,一定程度上减少了哈希冲突的产生。(自己声明一个 \(MOD\) 用来取余也可以)

二、哈希表

1.定义

哈希表是一种高效的数据结构。它的优点是查找的算法时间复杂度是常数,缺点是会消耗较多的内存。但是以空间换时间,还是一种常用的策略。所以哈希表还是有着极其不错的应用价值。

2.实现

先从一个具体的例子来感受哈希表的实现方法。假设有一个含 \(n\) 个数的数列,我们只需要开一个数组,依次将数组里的数存储到 \(a_1,a_2,...,a_n\) 中即可。但是这样做的缺点是当我们需要查找某一元素时,就需要遍历全部数组或者二分查找。所以查找复杂度为 \(O(1)\) 的算法就是对于每一个 \(key\) 值,直接令 \(A_{key}=key\) ,下标就是对应的数值。但是这样还有一个问题就是如果数据特别大,数据规模很广,对空间的开销又过于大了。于是我们想到字符串 \(\operatorname{Hash}\) 中有一个操作就是自然溢出,换句话说就是取模。所以我们可以设计一个函数 \(\operatorname H(key)=key \mod 13\) 再令 \(A_{\operatorname H(key)}=key\)

可是这样依旧不够完美,因为取余不能保证结果唯一,就比如 \(1\) 和 \(40\) 取余 \(13\) 的结果都为 \(1\) 。但这个问题也好解决,只需要像链表一样,将取余后结果相同的数据链接在同一下标处即可。

3.哈希函数的构造

大致了解了哈希表的存储方式以后,最后的问题就在于如何构造哈希函数。哈希函数没有硬性的规定,只要尽可能减少哈希冲突,就是好的函数,下面给出几种例子。

(1)余数法

就是上文提及到的。选择一个适当正整数 \(b\) 构造 \(\operatorname{H}(x)=x\bmod b\) 。一般地说,如果 \(b\) 的约数越多,那么冲突的几率就越大。

(2)乘积取整法

选择一个实数 \(A\) ,(\(A\in(0,1)\))作为乘数(最好是无理数,例如 \(\dfrac{\sqrt{5}-1}{2}\) 的实际效果就很好),将目标值 \(k\) 乘 \(A\) ,得到一个 \((0,k)\) 间的实数,然后取其小数部分,乘以哈希表的大小 \(M\) 再向下取整,即得 \(k\) 在哈希表的位置。可以表达为 $\operatorname{H}(x)= \left\lfloor\ M(x\times A \bmod 1) \right\rfloor $

(3)基数转化法

就是进制转化。将 \(k\) 看作 \(n\) 进制下的一个数然后将 \(k\) 重新转化为十进制数,再用取余。一般选用大于 \(10\) 的数作为转换的基数( \(n>10\) ),且最好满足 \(\gcd(n,10)=1\) 。

三、题单

1.【模板】字符串哈希

image

思路:

模板题。读入所有字符串后,对所有字符串进行字符串哈希,然后将哈希值存储。最后看有多少个不同的哈希值即可。因为有自然溢出,可以减少哈希冲突。

代码:

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
#define N 10050
#define M 1550
int n,l[N],b=131,cnt;
char ch[N][M];
ull Hash[N];
bool cmp (ull a,ull b) { return a>b; }
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) { scanf("%s",ch[i]);l[i]=strlen(ch[i]); }
	for(int i=1;i<=n;i++)
		for(int j=1;j<=l[i];j++)
			Hash[i]=Hash[i]*b+(ch[i][j]-'A'+1);
	sort(Hash+1,Hash+1+n,cmp);
	for(int i=1;i<=n;i++) if(Hash[i]!=Hash[i+1]) cnt++; 
	cout<<cnt<<endl;
	return 0;
}

2.子串查找

image

思路:

应用前缀和的思想 \(O(n)\) 求出以 \(i\) 为终点的字符串的哈希值,再求出目标字符串的哈希值。枚举每一个起点, \(O(1)\) 判断以 \(i\) 为起点长度为目标字符串长度的子串是否与目标字符串匹配。

代码:

#include<bits/stdc++.h>
using namespace std;
#define N 1000050
typedef unsigned long long ull;
char ch[N],s[N];
int n,m,cnt;
int b=131;
ull power[N],Hash[N],sum;
int main()
{
	scanf("%s",ch+1);
	scanf("%s",s+1);
	n=strlen(ch+1);m=strlen(s+1);
	power[0]=1;Hash[0]=0;sum=0;
	for(int i=1;i<=n;i++) power[i]=power[i-1]*b;
	for(int i=1;i<=n;i++) Hash[i]=Hash[i-1]*b+(ull)(ch[i]-'A'+1);
	for(int i=1;i<=m;i++) sum=sum*b+(ull)(s[i]-'A'+1);
	for(int i=0;i<=n-m;i++)
		if(sum==Hash[i+m]-Hash[i]*power[m]) cnt++; 
	cout<<cnt<<endl;
	return 0;
} 

3.Seek the name,seek the fame

image

思路:

先预处理出以 \(i\) 为终点的字符串的哈希值。然后枚举每一个位置 \(i\) ,判断开头前 \(i\) 个字母与最后 \(i\) 个字母构成的字符串的哈希值是否相等即可。时间复杂度 \(O(n)\) 。

代码:

#include<bits/stdc++.h>
using namespace std;
#define N 400050
typedef unsigned long long ull;
ull power[N],Hash[N];
int b=131,n,cnt,ans[N];
string ch,s;
int main()
{
	while(cin>>s)
	{
		cnt=0;power[1]=b;
		ch=' '+s;
		memset(ans,0,sizeof(ans));
		memset(Hush,0,sizeof(Hash));
		n=s.length();
		for(int i=2;i<=n;i++) power[i]=power[i-1]*b;
		for(int i=1;i<=n;i++) Hash[i]=Hash[i-1]*b+(ull)(ch[i]-'A'+1);
		for(int i=1;i<=n;i++)
			if(Hash[i]==(Hash[n]-Hash[n-i]*power[i])) cout<<i<<" ";
		puts("");
	}
	return 0;
} 

4.power string

image

思路:

一开始没有想明白复杂度为什么是对的。

暴力枚举分段点,写一个 \(\operatorname{check}\) 函数检验分段点是否合理,因为题目中说分段数尽可能大,所以找到第一个分段点可以直接结束。

检验时算出第一段的哈希值,后面几段依次比对看看是否均相同,不相同就直接返回继续枚举。

可能原因:估计复杂度是 \(O(n\sqrt{n})\) ,但是很可能跑不满。所以就冲过去了?

代码:

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
#define N 1000050
char ch[N];
int n,b=131,ans;
ull power[N],Hash[N],sum;
inline void init() { power[0]=1;for(int i=1;i<=n;i++) power[i]=power[i-1]*b; }
int check(int x)
{
	Hash[0]=0;
	for(int i=1;i<=n;i++) Hash[i]=Hash[i-1]*b+(ull)(ch[i]-'A'+1);
	sum=Hash[x];
	for(int i=x;i<=n-x;i+=x)
		if(Hash[i+x]-Hash[i]*power[x]!=sum) return 0;
	return 1;
}
int main()
{
	while(1)
	{
		scanf("%s",ch+1);
		n=strlen(ch+1);
		init();
		if(n==1&&ch[1]=='.') break;
		int book=0;
		for(int i=1;i<=n;i++)
			if(!(n%i))
				if(check(i)) { ans=n/i;book=1;break; }
		if(book==0) cout<<1<<endl;
		else cout<<ans<<endl;
	}
	return 0;
}  

5.Three Friends

image

思路:

先从简单的地方思考。

首先 \(n\) 一定是奇数,并且如果最后有解,那么将字符串分成两半,一定至少有一半就是正确答案(字符串 \(S\) )。

所以我们大致有了一个思路就是将字符串拆成两半,对左边一半枚举每一个位置的字符被删除后的情况。做完后再对右边进行相同的操作,每找到一个可以被删除的字符 \(cnt\) 就统计一下答案,最后如果 \(cnt=1\) 就说明答案唯一, \(cnt=0\) 说明无解,否则有多组解。

这样我们的时间复杂度是 \(O(n)\) ,面对 \(n\leq2\times 10^6\) 这种数据范围,我们需要尽可能快的方法来检验该位置是否可以删除字符。

于是我们想到字符串 \(\operatorname{Hash}\) 是用前缀和处理的,如果我们能够直接计算出修改字符后哈希值的变化,那每一次判断时间复杂度就变为 \(O(1)\) 。

我们已知 \([l,r]\) 内的哈希值可以表示为 \(\operatorname{Cal}(l,r)= Hash[r]-Hash[l-1]\times b^{r-l+1}\) ,如果现在 \([l,r]\) 内 \(x\) 位置的字符被删除那么哈希值该怎么表示呢?

我们知道哈希值的表示可以看作是 \(b\) 进制下的数,那么我们可以将删除后 \([l,r]\) 内的哈希值表示为 \(\operatorname{Modify}(l,r)=\operatorname {Cal}(l,x-1)\times b^{r-x}+\operatorname{Cal}(x+1,r)\) 。

到此所有问题都解决,代码实现即可。注意部分细节。

代码:

#include<bits/stdc++.h>
using namespace std;
#define N 2000050
typedef unsigned long long ull;
ull power[N],Hash[N],sum1,sum2;
char ch[N];
string a,b,c,d;
int n,p=131,mid,cnt;
inline ull Cal(int l,int r) { return (Hash[r]-Hash[l-1]*power[r-l+1]); }
inline ull modify(int l,int r,int k) { return (Cal(l,k-1)*power[r-k]+Cal(k+1,r)); }
int main()
{
	cin>>n;
	scanf("%s",ch+1);
	if(!(n&1)) { puts("NOT POSSIBLE");return 0; }
	power[0]=1;
	for(int i=1;i<=n;i++) power[i]=power[i-1]*p;
	for(int i=1;i<=n;i++) Hash[i]=Hash[i-1]*p+(ull)(ch[i]-'A'+1);
	mid=(1+n)>>1;
	sum1=Cal(mid+1,n);
	for(int i=mid+1;i<=n;i++) a.push_back(ch[i]);
	for(int i=1;i<=mid;i++)
	{
		sum2=modify(1,mid,i);
		if(sum1==sum2)
		{
			cnt++;
			c=a;
			break;
		}
	}
	sum2=Cal(1,mid-1);
	for(int i=1;i<mid;i++) b.push_back(ch[i]);
	for(int i=mid;i<=n;i++)
	{
		sum1=modify(mid,n,i);
		if(sum1==sum2)
		{
			cnt++;
			d=b;
			break;
		}
	}
	if(!cnt) puts("NOT POSSIBLE");
	else if(cnt==1||c==d) 
	{
		if(c.size()) cout<<c<<endl;
		else cout<<d<<endl;
	}
	else puts("NOT UNIQUE");
	return 0;
} 

6.可怕的诗

image

思路:

有点像前面做过的一道题,但是这个询问次数有点吓人,每次做一遍肯定超时。(是一道卡常题)

首先关于循环节我们需要知道:循环节是区间字符串长度的约数;如果 \(n\) 是一个循环节,那么 \(k\times n\) 也一定是一个循环节。

假设 \(\operatorname {Cal}(l,r)\) 表示字符串区间 \([l,r]\) 内的哈希值。考虑找最小的循环节就是找最小的 \(len\) 使得 \(\operatorname{Cal}(l,r-len)=\operatorname{Cal}(l+len,r)\) 。

所以我们的思路是令 \(len\) 一开始为区间长度,用 \(fac_{len}\) 存储 \(len\) 的最小质因子。

如果当前 \(len\) 是循环节的长度则接着判断 \(len/fac_{len}\) 是否可以,重复执行直到不可以为止。则最后成立的 \(len\) 就是最小循环节长度。

最小质因子可以用线性筛来实现。

代码:

#include<bits/stdc++.h>
using namespace std;
#define N 500050
typedef unsigned long long ull;
ull Hash[N],power[N];
char ch[N];
int n,q,b=131,ans,len,cnt,l,r;
int isPrime[N],Prime[N],fac[N];
inline int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9') { if(c=='-')f=-1;c=getchar(); }
	while(c>='0'&&c<='9') { x=x*10+c-48;c=getchar(); }
	return x*f;
}
inline void Getprime(int n)
{
	for(int i=2;i<=n;i++) isPrime[i]=1;
	for(int i=2;i<=n;i++)
	{
		if(isPrime[i]) { Prime[++cnt]=i;fac[i]=i; }
		for(int j=1;j<=cnt&&i*Prime[j]<=n;j++)
		{
			isPrime[i*Prime[j]]=0;fac[i*Prime[j]]=Prime[j];
			if(i%Prime[j]==0) break;
		}
	}
}
inline void init()
{
	power[0]=1;
	for(int i=1;i<=n;i++) power[i]=power[i-1]*b;
	for(int i=1;i<=n;i++) Hash[i]=Hash[i-1]*b+(ull)(ch[i]-'a'+1);
	Getprime(n);
}
inline int Cal(int l,int r) { return Hash[r]-Hash[l-1]*power[r-l+1]; }
int main()
{
	n=read();
	for(int i=1;i<=n;i++) cin>>ch[i];
	q=read();
	init();
	while(q--)
	{
		l=read();r=read();
		ans=len=r-l+1;
		if(Cal(l,r-1)==Cal(l+1,r)) { puts("1");continue; }
		while(len>1)
		{
			if(Cal(l,r-ans/fac[len])==Cal(l+ans/fac[len],r)) ans/=fac[len];
			len/=fac[len];
		}
		printf("%d\n",ans);
	}
	return 0;
} 

(你猜我为什么用快读?)

7.珍珠项链Beads

image

思路:

首先第一想法是枚举 \(k\) ,然后比较不同 \(k\) 下的段数并找出最优。

接下来我们来看看时间复杂度是否符合题目要求,枚举 \(k\) 时间复杂度为 \(O(n)\) ,对于每一个 \(k\) 共有 \(\left\lfloor\dfrac{n}{k}\right\rfloor\) 个字符串。

所以总时间复杂度为 \(\sum\limits_{i=1}^n {\left\lfloor\dfrac{n}{k}\right\rfloor}\) ,

原式展开化简可得, \(\sum\limits_{i=1}^n {\left\lfloor\dfrac{n}{k}\right\rfloor}=n\left(1+\dfrac{1}{2}+\dfrac{1}{3}+...+\dfrac{1}{n}\right)\approx n\ln n<n\log_2{n}\) ,

所以我们可以认为时间复杂度为 \(O(n\log_2{n})\) 。

数据范围 \(n\leq 2\times 10^5\) ,这个做法显然是符合题目要求的。

代码:

#include<bits/stdc++.h>
using namespace std;
#define N 200050
#define MOD 10000007
typedef unsigned long long ull;
int n,b=19260113;
int f[N],h[MOD];
int cnt,ans,sum;
ull a[N],power[N],Hash_front[N],Hash_back[N];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-')f=-1;ch=getchar(); }
	while(ch>='0'&&ch<='9') { x=x*10+ch-48;ch=getchar(); }
	return x*f;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++) cin>>a[i];
	power[0]=1;
	for(int i=1;i<=n;i++) power[i]=(power[i-1]*(ull)b)%MOD;
	for(int i=1;i<=n;i++) Hash_front[i]=((Hash_front[i-1]*b)+a[i])%MOD;
	for(int i=n;i>=1;i--) Hash_back[i]=((Hash_back[i+1]*b)+a[i])%MOD; 
	for(int k=1;n/k>=ans;k++)
	{
		cnt=0;
		for(int i=k;i<=n;i+=k)
		{
			int p=(Hash_front[i]-Hash_front[i-k]*power[k])%MOD;
			int q=(Hash_back[i-k+1]-Hash_back[i+1]*power[k])%MOD;
			if(h[p]==k) continue;
			cnt++;
			h[p]=k;
			h[q]=k;
		}
		if(cnt>ans)
		{
			ans=cnt;
			sum=0;
		}
		if(cnt==ans) f[++sum]=k;
	}
	cout<<ans<<" "<<sum<<endl;
	for(int i=1;i<=sum;i++) cout<<f[i]<<" ";
	return 0;
}

8.反转字符串Antisymmetry

image

思路:

在这里讨论哈希的做法。

看到数据范围 \(n\leq5\times10^5\) ,想到复杂度可能是 \(O(n\log_2{n})\) 。

发现反转字符串长度一定是偶数,并且可以理解为异或条件下的回文字符串,即前面有一个 \(0\) 后面对应位置就应当是一个 \(1\) 。

所以我们可以枚举对称轴的位置,然后用二分去找可以从对称轴向外扩展的长度 \(l\) ,则该反转字符串长度为 \(2l\) 。

接下来考虑其对答案的贡献,反转字符串的所有字串有相同的对称轴,所以任意长度为 \(2l\) 的反转字符串对答案的贡献是 \(l\) 。所以累加每一个位置做对称轴时对应的 \(l\) 即可。

最后考虑对字符串哈希的处理,正向哈希我们可以正常存储,反向哈希我们就把 \(0\) 看作 \(1\) 即可。

需要注意的细节:

① 对称轴位于 \(1\) 或 \(0\) 这些数字之间,即对称轴所处的位置不是数组的下标,在写数组下标时要谨慎。

② 每一次二分长度时右端点初始值 \(r=\min(i,n-i)\) , \(i\) 为当前对称轴所在的位置

代码:

#include<bits/stdc++.h>
using namespace std;
#define N 500050
typedef unsigned long long ull;
typedef long long ll;
int n,b=131;
int l,r,mid,x;
ll ans;
char ch[N];
ull Hash_front[N],Hash_back[N],power[N];
ull Cal1(int l,int r) { return Hash_front[r]-Hash_front[l-1]*power[r-l+1]; }
ull Cal2(int l,int r) { return Hash_back[l]-Hash_back[r+1]*power[r+1-l]; }
bool check(int l,int r) { return Cal1(l,r)==Cal2(l,r); }
int main()
{
	cin>>n;
	scanf("%s",ch+1);
	power[0]=1;
	for(int i=1;i<=n;i++) power[i]=power[i-1]*(ull)b; 
	for(int i=1;i<=n;i++) Hash_front[i]=Hash_front[i-1]*b+(ch[i]=='1');
	for(int i=n;i>=1;i--) Hash_back[i]=Hash_back[i+1]*b+(ch[i]=='0');
	for(int i=1;i<n;i++)
	{
		l=0;r=min(i,n-i);x=0;
		while(l<=r)
		{
			mid=(l+r)>>1;
			if(check(i-mid+1,i+mid)) { l=mid+1;x=mid; }
			else r=mid-1;
		}
		ans+=x;
	}
	cout<<ans<<endl;
	return 0;
} 

9.门票

image

思路:

这道题目有很多种做法,可以用 stl 里的 map 或者 unordered_set (用 map 可能会tle ),

或者直接开布尔数组,因为布尔数组占字节数小,可以开的很大, \(1\times10^9\) 大小完全没问题。

在这里讲一下手写 \(\operatorname{Hash}\) 的做法,正好借这个机会学习一下自定义 \(namespace\) 的写法。

手写哈希表,首先构造哈希函数 \(\operatorname{H}\) ,这里采用的是除余法 $\operatorname{H}(key)=key\mod{ P } $ ,

哈希表的原理就是将哈希值相同的关键字以链表的形式存储,

接下来就比较简单了,将 \(a_0\) 先存入表中,接下来对于每一个 \(a_i\) 先检查是否已经在邻接表里出现过,若出现过则直接找到了重复的项,没有的话就将 \(a_i\) 加入邻接表中,并且更新 \(a_i\) 。

代码:

#include<bits/stdc++.h>
using namespace std;
#define MOD 1000009
#define N 2000050
typedef long long ll;
ll A,B,C,num=1;
namespace Hash
{
	int head[N],ver[N],Next[N],tot=-1;
	inline void init() { memset(head,-1,sizeof(head)); }
	inline int H(int x) { return x%MOD; }
	inline void ADD(int x,int y)
	{
		ver[++tot]=y;
		Next[tot]=head[x];
		head[x]=tot;
	}
	inline bool check(int x,int y)
	{
		for(int i=head[x];~i;i=Next[i])
			if(ver[i]==y) return true;
		return false;
	}
}
using namespace Hash;
int main()
{
	init();
	cin>>A>>B>>C;
	for(int i=0;i<=2000000;i++)
	{
		if(check(H(num),num)) { cout<<i<<endl;return 0; }
		ADD(H(num),num);
		num=(num*A+num%B)%C;
	}
	puts("-1");
	return 0;
}

标签:Hash,ull,int,寻迹,哈希,字符串,operatorname
From: https://www.cnblogs.com/Cybersites/p/18391667

相关文章

  • 【Leetcode_Hot100】哈希
    哈希1.两数之和49.字母异位词分组128.最长连续序列1.两数之和方法一:HashMap在元素放入数组之前就进行判断,保证了不会取出同一个元素的情况,,例如[3,3],如果先将数组中的所有元素放入hashMap,再判断是否存在,则返回结果为[1,1],不符合题意。classSolution{publicint[......
  • 基于感知哈希算法的以图搜图系统的设计
    摘 要随着数字媒体和计算机网络的迅猛发展,互联网上在线图像的飞速增长,用户对图形图像的搜索需求日益提高,一种“以图搜图”的新型搜索模式应运而生。“以图搜图”是以用户提供的图形图像图片等为视觉特征基础,为用户提供互联网上相关图形图像资料检索服务,这是一种专业的搜索引......
  • 代码随想录算法day5 - 哈希表1
    题目1242.有效的字母异位词给定两个字符串*s*和*t*,编写一个函数来判断*t*是否是*s*的字母异位词。字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语,通常只使用所有原始字母一次。示例1:输入:s="anagram",t="nagaram"输出:true示例2:......
  • 哈希表hashtable课堂笔记
    /*哈希表,表示键/值对的集合,这些键/值对根据键的哈希代码进行组织。它的每个元素都是一个存储在DictionaryEntry对象中的键/值对。键不能为空引用,但值可以。哈希表的构造函数有多种,这里介绍两种最常用的。*///(1)使用默认的初始容量、加载因子、哈希代码提供程序和比......
  • Hash哈希学习笔记
    概念:通过一个hash函数建立值与存储地址的关系原则:开小数组+冲突解决冲突越少,用时越少;可通过调整余数或优质的hash算法尽量使hash值分散,减少碰撞hash算法的构成:hash函数的初始化构造hash函数:典型的函数包括除余法H......
  • 哈希
    树状数组是个好东西,写起来也相对好看。但是操作比较局限,区间修改就掉回\(O(nlogn)\),那还不如\(O(n)\)。线段树完美的解决问题。线段树,也可以理解的一堆线段组成的树。大致如上,有一线段\([l,r]\)当\(l\ner\)可化为\([l,mid]\),\([mid+1,r]\)PS:\(mid=(l+r......
  • Python——集合基本操作以及哈希函数
    Python中的集合(Set)是一个无序的、不包含重复元素的数据结构。集合主要用于数学上的集合操作,如并集、交集、差集和对称差集等。集合使用大括号 {} 来表示,但注意空集合不能使用 {} 表示(这会创建一个空字典),而应该使用 set() 来创建。创建集合1.使用大括号 {}:这是最直接......
  • 哈希表(及简单实现)
    1、什么是哈希表(散列表)要说哈希表,我们必须先了解一种新的存储方式—散列技术。散列技术是指在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每一个关键字都对应一个存储位置。即:存储位置=f(关键字)。这样,在查找的过程中,只需要通过这个对应关系f找到......
  • 哈希-快乐数
     解决这个问题的关键在于,判断结束遍历的条件,即当n!=1或者在循环过程中,没有出现过重复的数。 classSolution:defisHappy(self,n:int)->bool:defget_score(n):sum_=0whilen>0:end_=n%10......
  • 代码随想录 -- 哈希表 -- 四数之和
    18.四数之和-力扣(LeetCode)思路:(与三数之和类似,在外面加一层循环)    1. 先将nums 按升序排序    2. 初始状态:k=0,i= k+1,left= i+1,right= len(nums)-1        3. 进入第一层for循环:        如果 nums[k]>0andtarget>0 ......