首页 > 其他分享 >哈希表自记录

哈希表自记录

时间:2024-04-08 21:31:15浏览次数:23  
标签:return puts 记录 int cin 表自 哈希 NULL op

存储结构:

1.开放寻址法

#include<cstring>
#include <iostream>
using namespace std;
const int N=2000003, null = 0x3f3f3f3f;

int h[N];
int 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在哈希表当中k就是下标;如果k不在哈希表当中,k就是应该存储的位置。
} 

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    cin>>n;
    memset(h,0x3f,sizeof h);
    while(n--)
    {
        char op[2];
        int x;
        cin>>op>>x;
        int k = find(x);
        if(op[0]=='I') 
        {
            h[k] = x;
        }
        else 
        {
            if(h[k]!=null) puts("Yes");
            else puts("No");
            
        }
    }
    return 0;
}

2.拉链法

c++中的memset使用方法-->http://t.csdnimg.cn/XzqDc

#include<cstring>
#include <iostream>
using namespace std;
const int N=1000003;

int h[N], e[N], ne[N], idx;
int n;
void insert(int x)
{
    int k = (x%N+N)%N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}
bool find(int x)
{
    int k =(x%N+N)%N;
    for(int i=h[k];i!=-1;i=ne[i])
    {
        if(e[i] == x)
            return true;
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    cin>>n;
    memset(h,-1,sizeof h);
    while(n--)
    {
        char op[2];
        int x;
        cin>>op>>x;
        if(op[0]=='I') insert(x);
        else 
        {
            if(find(x)) puts("Yes");
            else puts("No");
            
        }
    }
    return 0;
}

字符串哈希方式:很多需要KMP的方法都可以用字符串哈希

作用:快速判断两个字符串是否相等

#include <iostream>
using namespace std;
typedef unsigned long long ULL;
const int N=100010, P=131;

int n,m;
char str[N];
ULL h[N],p[N];
ULL get(int l, int r)
{
    return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    cin>>n>>m>>str+1;
    p[0] =1;
    for(int i=1;i<=n;i++)
    {
        p[i] = p[i-1] *P;
        h[i] = h[i-1] *P+str[i];
    }
    while(m--)
    {
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        if(get(l1,r1)==get(l2,r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}

标签:return,puts,记录,int,cin,表自,哈希,NULL,op
From: https://blog.csdn.net/liu285783/article/details/137499176

相关文章

  • 【SVN】安装记录
    VisualSVNhttps://www.visualsvn.com/downloads/  TortoiseSVNTortoiseSVN官网打不开,去哪下最新的软件和中文包?官网:https://tortoisesvn.net能打开最好,但通常打不开,打不开时候去这个网站下;https://sourceforge.net/projects/tortoisesvn/这个网站开发软件的应该很熟......
  • AndroidStudio学习记录(5):图像按钮ImageView的实现
    <?xmlversion="1.0"encoding="utf-8"?><LinearLayoutxmlns:android="http://schemas.android.com/apk/res/android"android:layout_width="match_parent"android:layout_height="match_parent"......
  • Blazor学习记录_12._IIS部署_组件的引用_
    27.Blazor项目发布与IIS部署27.1如果是Auto模版的项目,选择两个项目中的Server项目进行发布27.2服务器必要的运行时安装与配置1.安装运行时可先通过命令行输入:dotnet--info来查看本地已经安装的运行时情况。运行时官方下载页面:https://dotnet.microsoft.com/zh-cn/dow......
  • Unity类银河恶魔城学习记录12-7-2 p129 Craft UI - part 2源代码
    Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释,可供学习Alex教程的人参考此代码仅为较上一P有所改变的代码 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩哔哩_bilibiliUI_CraftWindow.csusingUnityEngine.UI;usingTMPro;usingUnityEngine;usingU......
  • DNS 各记录类型说明及规则
    各记录类型使用目的记录类型使用目的A记录将域名指向一个IP地址。CNAME记录将域名指向另一个域名,再由另一个域名提供IP地址。MX记录设置邮箱,让邮箱能收到邮件。NS记录将子域名交给其他DNS服务商解析。AAAA记录将域名指向一个IPv6地址。SRV记录用来标识某台服......
  • Acwing 681. 疏散人群(dfs)(记录根节点下有几个子节点)
    输入样例:62132435261输出样例:4#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;typedefpair<LL,LL>PII;constLLN=100200,M=2020;constLLmod=998244353;vector<LL>g[N];LLsum[N];LLdfs(LLidx,LLfa){LL......
  • 记录linux从0部署java项目(宝塔)
    目录一、安装宝塔可视化界面 二、部署前端三、部署后端1、配置并连接Mysql数据库2、配置并连接redis3、安装jdk这里先记录一个安装后遇到的问题安装openJDK四、检查一、安装宝塔可视化界面宝塔面板下载,免费全能的服务器运维软件运行安装脚本安装完成后访问......
  • HJ19 简单错误记录
    描述开发一个简单错误记录功能小模块,能够记录出错的代码所在的文件名称和行号。处理:1、记录最多8条错误记录,循环记录,最后只用输出最后出现的八条错误记录。对相同的错误记录只记录一条,但是错误计数增加。最后一个斜杠后面的带后缀名的部分(保留最后16位)和行号完全匹配的记录才......
  • PCB学习记录-----入门&基础知识
    一、搭建环境1.下载嘉立创EDA 软件下载-嘉立创EDA(lceda.cn)选专业版在线编辑:嘉立创EDA(专业版)-V2.1.45(lceda.cn)官方教程:立创EDA专业版-使用教程(lceda.cn)2.新建工程文件-新建-项目,右键Board1可以重命名,原理图右键新增图页右侧图纸尺寸可自定义调整图纸......
  • 【LeetCode刷题记录】15. 三数之和
    15三数之和给你一个整数数组nums,判断是否存在三元组[nums[......