LeetCode 706. 设计哈希映射（数组法，稀疏矩阵法，链地址法，开放定址法）

2024-04-15 22:58
文章标签 leetcode 设计 数组 地址 哈希 开放 矩阵 映射 稀疏 706 定址法

本文主要是介绍LeetCode 706. 设计哈希映射（数组法，稀疏矩阵法，链地址法，开放定址法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

思路：

参考：https://leetcode-cn.com/problems/design-hashmap/solution/706-she-ji-ha-xi-ying-she-by-jyj407-nzcz/

解法1：
因为数据不大，直接用数组保存每个值的映射。

class MyHashMap {
private:vector<int>cache;
public:/** Initialize your data structure here. */MyHashMap() {cache.resize(1000005,-1);}/** value will always be non-negative. */void put(int key, int value) {cache[key] = value;}/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */int get(int key) {return cache[key];}/** Removes the mapping of the specified value key if this map contains a mapping for the key */void remove(int key) {cache[key] = -1;}
};

解法2：
二维稀疏矩阵，节省空间

class MyHashMap {
private:vector<vector<int>>data;int N = 1001;
public:/** Initialize your data structure here. */MyHashMap() {data.resize(N);}int getHashKey1(int x) {return x / N;}int getHashKey2(int x) {return x % N;}/** value will always be non-negative. */void put(int key, int value) {int hashKey1 = getHashKey1(key);int hashKey2 = getHashKey2(key);if(data[hashKey1].empty()) data[hashKey1].resize(N,-1);data[hashKey1][hashKey2] = value;}/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */int get(int key) {int hashKey1 = getHashKey1(key);int hashKey2 = getHashKey2(key);if(data[hashKey1].empty()) return -1;return data[hashKey1][hashKey2];}/** Removes the mapping of the specified value key if this map contains a mapping for the key */void remove(int key) {int hashKey1 = getHashKey1(key);int hashKey2 = getHashKey2(key);if(data[hashKey1].size()) data[hashKey1][hashKey2] = -1;}
};

解法3：
构建哈希表，拉链法解决哈希冲突

struct MyListNode {int key,val;MyListNode* next;MyListNode(): key(-1),val(-1),next(nullptr){}MyListNode(int _key,int _val):key(_key),val(_val),next(nullptr){}
};
class MyHashMap {
private:vector<MyListNode*>data;int N = 1009;
public:MyHashMap() {data.resize(N,new MyListNode());}int getHashKey(int key) {return key % N;}void put(int key, int value) {int hashKey = getHashKey(key);MyListNode *head = data[hashKey];MyListNode *p = head;MyListNode *tail = p;while(p != nullptr) {if(p -> key == key) {p -> val = value;return;}tail = p;p = p -> next;}tail -> next = new MyListNode(key,value);}int get(int key) {int hashKey = getHashKey(key);MyListNode* head = data[hashKey];MyListNode* p = head;while(p != nullptr) {if(p -> key == key) {return p -> val;}p = p -> next;}return -1;}void remove(int key) {int hashKey = getHashKey(key);MyListNode* head = data[hashKey];MyListNode* prev = head;MyListNode* p = head -> next;while(p != nullptr) {if(p -> key == key) {prev -> next = p -> next;p -> next = nullptr;delete(p);return;}prev = p;p = p -> next;}}
};

解法4：
STL实现的双向链表，使用双向链表的原因是在已知迭代器（指针）的情况下可以做到O(1)删除。

class MyHashMap {
private:vector<list<pair<int,int>>>data;int N = 1009;
public:MyHashMap() {data.resize(N);}int getHashKey(int key) {return key % N;}list<pair<int,int>>::iterator find(int key) {int hashKey = getHashKey(key);auto& it = data[hashKey];for(auto iter = it.begin();iter != it.end();iter++) {if(iter -> first == key) {return iter;}}return it.end();}void put(int key, int value) {int hashKey = getHashKey(key);auto iter = find(key);if(iter != data[hashKey].end()) {iter -> second = value;return;}data[hashKey].push_back({key,value});}   int get(int key) {int hashKey = getHashKey(key);auto iter = find(key);if(iter != data[hashKey].end()) {return iter -> second;}return -1;}void remove(int key) {int hashKey = getHashKey(key);auto iter = find(key);if(iter != data[hashKey].end()) {data[hashKey].erase(iter);}}
};

解法5：
C++实现的双向链表

struct MyListNode {int key,val;MyListNode* next;MyListNode* prev;MyListNode():key(-1),val(-1),next(nullptr),prev(nullptr){}MyListNode(int _key,int _val):key(_key),val(_val),next(nullptr),prev(nullptr){}
};
class MyHashMap {
private:vector<MyListNode*>data;int N = 1009;
public:MyHashMap() {data.resize(N,new MyListNode());}int getHashKey(int key) {return key % N;}MyListNode* find(int key) {int hashKey = getHashKey(key);MyListNode* head = data[hashKey];while(head != nullptr) {if(head -> key == key) return head;head = head -> next;}return nullptr;}void del(MyListNode* p) {p -> prev -> next = p -> next;if(p -> next) p -> next -> prev = p -> prev;p -> next = p -> prev = nullptr;delete(p);}void put(int key, int value) {int hashKey = getHashKey(key);MyListNode* p = find(key);MyListNode* head = data[hashKey];if(p != nullptr) {p -> val = value;return;}MyListNode* newNode = new MyListNode(key,value);newNode -> next = head -> next;if(head -> next != nullptr) {head -> next -> prev = newNode;}head -> next = newNode;newNode -> prev = head;}int get(int key) {int hashKey = getHashKey(key);MyListNode* iter = find(key);if(iter != nullptr) {return iter -> val;}return -1;}void remove(int key) {int hashKey = getHashKey(key);  MyListNode* iter = find(key);if(iter != nullptr) {del(iter);}}
};

解法6：
开放定址，线性探测

class MyHashMap {
private:const static int N = 20005;vector<pair<int,int>>hashTable;
public:MyHashMap() {hashTable.resize(N,{-1,-1});}int getHashKey(int key) {int k = key % N;while(hashTable[k].first != key && hashTable[k].first != -1) {k = (k + 1) % N;}return k;}void put(int key, int value) {int k = getHashKey(key);hashTable[k] = {key,value};}int get(int key) {int k = getHashKey(key);return hashTable[k].second;}void remove(int key) {int k = getHashKey(key);if(hashTable[k].first != -1) {hashTable[k].first = -2;}}
};

这篇关于LeetCode 706. 设计哈希映射（数组法，稀疏矩阵法，链地址法，开放定址法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/907162。

相关文章

C++中初始化二维数组的几种常见方法

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a
阅读更多...
shell编程之函数与数组的使用详解

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》：本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的
阅读更多...
Python中使用正则表达式精准匹配IP地址的案例

Python中使用正则表达式精准匹配IP地址的案例

《Python中使用正则表达式精准匹配IP地址的案例》Python的正则表达式(re模块)是完成这个任务的利器,但你知道怎么写才能准确匹配各种合法的IP地址吗,今天我们就来详细探讨这个问题,感兴趣的朋... 目录为什么需要IP正则表达式？IP地址的基本结构基础正则表达式写法精确匹配0-255的数字验证IP地
阅读更多...
resultMap如何处理复杂映射问题

resultMap如何处理复杂映射问题

《resultMap如何处理复杂映射问题》：本文主要介绍resultMap如何处理复杂映射问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录resultMap复杂映射问题Ⅰ 多对一查询：学生——老师Ⅱ 一对多查询：老师——学生总结resultMap复杂映射问题
阅读更多...
Java枚举类实现Key-Value映射的多种实现方式

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co
阅读更多...
C++原地删除有序数组重复项的N种方法

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体：最多保留两次五、分析和代码实现5.1、问题分析5.
阅读更多...
Linux系统中配置静态IP地址的详细步骤

Linux系统中配置静态IP地址的详细步骤

《Linux系统中配置静态IP地址的详细步骤》本文详细介绍了在Linux系统中配置静态IP地址的五个步骤,包括打开终端、编辑网络配置文件、配置IP地址、保存并重启网络服务,这对于系统管理员和新手都极具... 目录步骤一：打开终端步骤二：编辑网络配置文件步骤三：配置静态IP地址步骤四：保存并关闭文件步骤五：重
阅读更多...
Linux配置IP地址的三种实现方式

Linux配置IP地址的三种实现方式

《Linux配置IP地址的三种实现方式》：本文主要介绍Linux配置IP地址的三种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录环境RedHat9第一种安装 直接配置网卡文件第二种方式 nmcli(Networkmanager command-line
阅读更多...
Linux虚拟机不显示IP地址的解决方法(亲测有效)

Linux虚拟机不显示IP地址的解决方法(亲测有效)

《Linux虚拟机不显示IP地址的解决方法(亲测有效)》本文主要介绍了通过VMware新装的Linux系统没有IP地址的解决方法,主要步骤包括：关闭虚拟机、打开VM虚拟网络编辑器、还原VMnet8或修... 目录前言步骤0.问题情况1.关闭虚拟机2.China编程打开VM虚拟网络编辑器3.1 方法一：点击还原VM
阅读更多...
Java中数组转换为列表的两种实现方式(超简单)

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架（Arrays.asList）1.1 示例代码1.
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2