保研机试备考十一:哈希表和KMP
AcWing 840. 模拟散列表
题目
https://www.acwing.com/problem/content/842/
思路
https://blog.csdn.net/weixin_45798993/article/details/122724398
代码
#include<iostream>
#include<cstring>
using namespace std;
#define null 0x3f3f3f3f
const int N=2e5+3;
int h[N];
int find(int x)
{
int k=(x%N+N)%N;
while(h[k]!=null&&h[k]!=x)
{
k++;
if(k==N) k=0;
}
return k;
}
int main()
{
memset(h,0x3f,sizeof(h));
int n,x;
char op;
cin>>n;
while(n--)
{
cin>>op>>x;
if(op=='I')
h[find(x)]=x;
else
if(h[find(x)]==null)
puts("No");
else
puts("Yes");
}
return 0;
}
AcWing 3820. 未出现过的最小正整数
题目
思路
先把数组中的所有元素存到哈希表里去
再从1到10^9^去遍历查找,找到第一个找不到的位置,即为答案
代码
#define null 0x3f3f3f3f
const int N=3e5+3; //这里用数据规模的3倍,2倍的话过不了
class Solution {
public:
int h[N];
int find(int x)
{
int k=(x%N+N)%N;
while(h[k]!=null&&h[k]!=x)
{
k++;
if(k==N) k=0;
}
return k; //别忘了返回位置k
}
int findMissMin(vector<int>& nums) {
memset(h,0x3f,sizeof(h)); //别忘了一开始初始化h所有元素为空
for(int i=0;i<nums.size();i++)
h[find(nums[i])]=nums[i];
for(int i=1;i<=1e9;i++)
if(h[find(i)]==null)
return i;
}
};
新思路与代码
分情况讨论:
+ 如果$1$到$n$都出现过,那么答案就是$n+1$
+ 如果$1$到$n$中某个元素没有出现过,那答案$≤n$
所以答案只会在$1$到$n+1$之间出现,所以使用一个大小为$n+1$的数组就行。
class Solution {
public:
int findMissMin(vector<int>& nums) {
int n=nums.size();
vector<bool> hash(n+1);
for(int x:nums)
if(x>=1&&x<=n)
hash[x]=true;
for(int i=1;i<=n;i++)
if(!hash[i]) return i;
return n+1;
}
};
AcWing 831. KMP字符串
题目
https://www.acwing.com/problem/content/833/
思路
https://blog.csdn.net/weixin_45798993/article/details/122652083
https://zhuanlan.zhihu.com/p/105629613
代码
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+10;
int ne[N];
int n,m;
string p,s;
int main()
{
cin>>n>>p>>m>>s;
//求模式串的next数组
int j=-1;
ne[0]=-1;
for(int i=1;i<n;i++) //从1开始
{
while(j!=-1&&p[i]!=p[j+1]) //&& 不是 ||
j=ne[j];
if(p[i]==p[j+1])
j++;
ne[i]=j;
}
//kmp
j=-1;
for(int i=0;i<m;i++) //从0开始
{
while(j!=-1&&s[i]!=p[j+1])
j=ne[j];
if(s[i]==p[j+1])
j++;
if(j==n-1)
{
printf("%d ",i-n+1);
j=ne[j];
}
}
return 0;
}