【考研思维题】【哈希表 || 什么时候用哈希表呢?快速查询的时候】【我们一起60天准备考研算法面试(大全)-第九天 9/60】

这篇具有很好参考价值的文章主要介绍了【考研思维题】【哈希表 || 什么时候用哈希表呢?快速查询的时候】【我们一起60天准备考研算法面试(大全)-第九天 9/60】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

专注 效率 记忆
预习 笔记 复习 做题

欢迎观看我的博客,如有问题交流,欢迎评论区留言,一定尽快回复!(大家可以去看我的专栏,是所有文章的目录)
 
文章字体风格:
红色文字表示:重难点★✔
蓝色文字表示:思路以及想法★✔
 
如果大家觉得有帮助的话,感谢大家帮忙
点赞!收藏!转发!

本博客带大家一起学习,我们不图快,只求稳扎稳打。
由于我高三是在家自学的,经验教训告诉我,学习一定要长期积累,并且复习,所以我推出此系列。
只求每天坚持40分钟,一周学5天,复习2天
也就是一周学10道题
60天后我们就可以学完81道题,相信60天后,我们一定可以有扎实的代码基础!我们每天就40分钟,和我一起坚持下去吧!
qq群:878080619

十、哈希表

1. 模拟散列表

【考研思维题】【哈希表 || 什么时候用哈希表呢?快速查询的时候】【我们一起60天准备考研算法面试(大全)-第九天 9/60】,【60天学完复试笔试-秘籍大全】考研408-数据结构(笔试),考研,散列表,算法

开散列方法(拉链法)

就记住有N个链表头节点

对于原数据可以 (x % N + N) % N;找到合适位置插入到头节点

#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e5 + 3;  // 取大于1e5的第一个质数,取质数冲突的概率最小 可以百度

//* 开一个槽 h
int h[N], e[N], ne[N], idx;  //邻接表

void insert(int x) {
    // c++中如果是负数 那他取模也是负的 所以 加N 再 %N 就一定是一个正数
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}

bool find(int x) {
    //用上面同样的 Hash函数 讲x映射到 从 0-1e5 之间的数
    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 n;

int main() {
    cin >> n;

    memset(h, -1, sizeof h);  //将槽先清空 空指针一般用 -1 来表示

    while (n--) {
        string op;
        int x;
        cin >> op >> x;
        if (op == "I") {
            insert(x);
        } else {
            if (find(x)) {
                puts("Yes");
            } else {
                puts("No");
            }
        }
    }
    return 0;
}
开放寻址法代码
本质:(最多存1e5个数)
#include <cstring>
#include <iostream>

using namespace std;

//开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了
const int N = 2e5 + 3;        //大于数据范围的第一个质数
const int null = 0x3f3f3f3f;  //规定空指针为 null 0x3f3f3f3f

int h[N];

int find(int x) {
    int t = (x % N + N) % N;
    while (h[t] != null && h[t] != x) {
        t++;
        if (t == N) {
            t = 0;
        }
    }
    return t;  //如果这个位置是空的, 则返回的是他应该存储的位置
}

int n;

int main() {
    cin >> n;

    memset(h, 0x3f, sizeof h);  //规定空指针为 0x3f3f3f3f

    while (n--) {
        string op;
        int x;
        cin >> op >> x;
        if (op == "I") {
            h[find(x)] = x;
        } else {
            if (h[find(x)] == null) {
                puts("No");
            } else {
                puts("Yes");
            }
        }
    }
    return 0;
}

2. 未出现过的最小正整数( 2018年全国硕士研究生招生考试 )

【考研思维题】【哈希表 || 什么时候用哈希表呢?快速查询的时候】【我们一起60天准备考研算法面试(大全)-第九天 9/60】,【60天学完复试笔试-秘籍大全】考研408-数据结构(笔试),考研,散列表,算法
由于我们需要从1去找 是否出现在数组中

如果1去遍历一遍数组
2遍历一遍数组
太麻烦

如何一步到位?
其实可以用
哈希思想

把数组出现的数都映射存储到数组中

如何都没有出现

那么一定是大于数组的个数+1的那个值文章来源地址https://www.toymoban.com/news/detail-544412.html

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

到了这里,关于【考研思维题】【哈希表 || 什么时候用哈希表呢?快速查询的时候】【我们一起60天准备考研算法面试(大全)-第九天 9/60】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 快速入门ChatGPT和AIGC:底层原理、热门工具、行业现状【我们能做什么】

    最近大家热议的ChatGPT和AI绘画工具的底层技术原理是什么?是如何发展到现在的?有哪些应用场景、热门工具?AIGC产业上下游有哪些公司?作为普通用户,我们还能接触哪些应用AI技术打造的商业解决方案?…… 我们查阅了AIGC相关相关的调研报告和各类资料,按照优化后的

    2024年02月09日
    浏览(47)
  • 【Golang】三分钟让你快速了解Go语言&为什么我们需要Go语言?

    博主简介: 努力学习的大一在校计算机专业学生,热爱学习和创作。目前在学习和分享:数据结构、Go,Java等相关知识。 博主主页: @是瑶瑶子啦 所属专栏: Go语言核心编程 近期目标: 写好专栏的每一篇文章 Go 语言从 2009 年 9 月 21 日开始作为谷歌公司 20% 兼职项目,即相关

    2023年04月21日
    浏览(62)
  • GPT-4助力我们突破思维定势

           GPT-4在突破思维局限、激发灵感和促进知识交叉融合方面的作用不可小觑,它正逐渐成为一种有力的工具,助力各行业和研究领域的创新与发展。           GPT-4在突破传统思维模式、拓宽创新视野和促进跨学科知识融合方面扮演着越来越重要的角色: 突破思维局限

    2024年02月21日
    浏览(47)
  • 考研依据数学思维导图,整理出的章节知识大纲

    线性代数 | 整体写 | 第二章矩阵及其运算|整体文档|(思维导图,概念)-CSDN博客 线性代数 | 分开写 | 第二章 矩阵及其运算 | 1 线性方程组和矩阵-CSDN博客 线性代数 | 分看写 |第二章 矩阵及其运算 | 2 矩阵的运算-CSDN博客  线性代数 | 分开写 |第二章 矩阵及其运算 | 3. 逆矩阵-C

    2024年04月22日
    浏览(46)
  • 【我们一起60天准备考研算法面试(大全)-第二十九天 29/60】【二进制】

    专注 效率 记忆 预习 笔记 复习 做题 欢迎观看我的博客,如有问题交流,欢迎评论区留言,一定尽快回复!(大家可以去看我的专栏,是所有文章的目录) 文章字体风格: 红色文字表示:重难点★✔ 蓝色文字表示:思路以及想法★✔ 如果大家觉得有帮助的话,感谢大家帮

    2024年02月15日
    浏览(51)
  • java思维导图 - -13张思维导图带你快速入门 --

    java!!!!!!!!! 13张思维导图带你快速入门 --满满干货(建议收藏) –怒肝一周,只求一赞!!! 囊括了java大部分的知识点,今天分享给大家,希望能帮助到各位友友! 分为电脑端和手机端! 手机端隐藏了部分分支,便于观看 电脑端是完整版,根据需求自行选择。

    2024年02月02日
    浏览(69)
  • MySQL什么时候要分表,什么时候要分库

    在MySQL中,是否需要对表或数据库进行分区的决策取决于多种因素,如数据大小、性能要求、可扩展性需求和底层硬件基础设施。对于何时分区表或数据库,没有固定的阈值,因为它取决于具体的应用程序和工作负载。 当表的大小增长到影响查询性能、维护任务或存储需求时

    2024年02月08日
    浏览(50)
  • windows系统下查询下载文件哈希值

    1、win + r 启动 windows 运行窗口 2、输入Powershell命令,启动Powershell命令窗口 3、改为你要校验的文件路径。如果该文件不在当前工作目录,需要输入完整的文件路径。(对于 Powershell,文件路径中如果有空格,还需要用引号把路径括起来,并在最前面插入一个。) 例如,要效验

    2024年02月11日
    浏览(44)
  • 联表查询的时候外键id是字符串

    2024年02月09日
    浏览(39)
  • 我们在选择服务器的时候,经常会看到单线服务器,多线服务器和BGP服务器,那这些线路的服务器有存在哪些不同呢?

    我们在选择服务器的时候,经常会看到单线服务器,多线服务器和BGP服务器,那这些线路的服务器有存在哪些不同呢? 单线 所谓的单线服务器是单网卡单个IP,指只有电信、联通或者移动一条线路。 缺点:由于线路单一,所选线路为电信线路时,联通或移动的用户访问时可

    2024年02月12日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包