保研机试备考十一：哈希表和KMP

https://www.acwing.com/problem/content/842/

https://blog.csdn.net/weixin_45798993/article/details/122724398

#include
#include
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;
}

先把数组中的所有元素存到哈希表里去
再从1到10⁹去遍历查找，找到第一个找不到的位置，即为答案

#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& nums) {
        memset(h,0x3f,sizeof(h));  //别忘了一开始初始化h所有元素为空
        for(int i=0;i 
新思路与代码 
分情况讨论：
 
如果
     
      
       
        
         1
        
       
       
        1
       
      
     1到
     
      
       
        
         n
        
       
       
        n
       
      
     n都出现过，那么答案就是
     
      
       
        
         n
        
        
         +
        
        
         1
        
       
       
        n+1
       
      
     n+1
如果
     
      
       
        
         1
        
       
       
        1
       
      
     1到
     
      
       
        
         n
        
       
       
        n
       
      
     n中某个元素没有出现过，那答案
     
      
       
        
         ≤
        
        
         n
        
       
       
        ≤n
       
      
     ≤n
 
所以答案只会在
     
      
       
        
         1
        
       
       
        1
       
      
     1到
     
      
       
        
         n
        
        
         +
        
        
         1
        
       
       
        n+1
       
      
     n+1之间出现，所以使用一个大小为
    
     
      
       
        n
       
       
        +
       
       
        1
       
      
      
       n+1
      
     
    n+1的数组就行。
 
class Solution {
public:
    int findMissMin(vector& nums) {
        int n=nums.size();
        vector 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
#include
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
        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
        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;
}