hash表算法模板和相关题目

706. 设计哈希映射

难度简单

不使用任何内建的哈希表库设计一个哈希映射

具体地说，你的设计应该包含以下的功能

put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更新这个值。
get(key)：返回给定的键所对应的值，如果映射中不包含这个键，返回-1。
remove(key)：如果映射中存在这个键，删除这个数值对。

示例：

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);          
hashMap.put(2, 2);         
hashMap.get(1);            // 返回 1
hashMap.get(3);            // 返回 -1 (未找到)
hashMap.put(2, 1);         // 更新已有的值
hashMap.get(2);            // 返回 1 
hashMap.remove(2);         // 删除键为2的数据
hashMap.get(2);            // 返回 -1 (未找到)

注意：

所有的值都在 [0, 1000000]的范围内。
操作的总数目在[1, 10000]范围内。
不要使用内建的哈希库。

 1 class Bucket:
 2     def __init__(self):
 3         self.bucket = []
 4 
 5     def get(self, key):
 6         for (k, v) in self.bucket:
 7             if k == key:
 8                 return v
 9         return -1
10 
11     def update(self, key, value):
12         found = False
13         for i, kv in enumerate(self.bucket):
14             if key == kv[0]:
15                 self.bucket[i] = (key, value)
16                 found = True
17                 break
18 
19         if not found:
20             self.bucket.append((key, value))
21 
22     def remove(self, key):
23         for i, kv in enumerate(self.bucket):
24             if key == kv[0]:
25                 del self.bucket[i]
26 
27 
28 class MyHashMap(object):
29 
30     def __init__(self):
31         """
32         Initialize your data structure here.
33         """
34         # better to be a prime number, less collision
35         self.key_space = 2069
36         self.hash_table = [Bucket() for i in range(self.key_space)]
37 
38 
39     def put(self, key, value):
40         """
41         value will always be non-negative.
42         :type key: int
43         :type value: int
44         :rtype: None
45         """
46         hash_key = key % self.key_space
47         self.hash_table[hash_key].update(key, value)
48 
49 
50     def get(self, key):
51         """
52         Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
53         :type key: int
54         :rtype: int
55         """
56         hash_key = key % self.key_space
57         return self.hash_table[hash_key].get(key)
58 
59 
60     def remove(self, key):
61         """
62         Removes the mapping of the specified value key if this map contains a mapping for the key
63         :type key: int
64         :rtype: None
65         """
66         hash_key = key % self.key_space
67         self.hash_table[hash_key].remove(key)
68 
69 
70 # Your MyHashMap object will be instantiated and called as such:
71 # obj = MyHashMap()
72 # obj.put(key,value)
73 # param_2 = obj.get(key)
74 # obj.remove(key)

View Code

Example

样例 1:

输入:  key = "abcd", size = 1000
输出: 978	
样例解释：(97 * 33^3 + 98*33^2 + 99*33 + 100*1)%1000 = 978

样例 2:

输入:  key = "abcd", size = 100
输出: 78	
样例解释：(97 * 33^3 + 98*33^2 + 99*33 + 100*1)%100 = 78

Clarification

对于这个问题，您没有必要设计自己的哈希算法或考虑任何冲突问题，您只需要按照描述实现算法.

 1 class Solution:
 2     """
 3     @param key: A string you should hash
 4     @param HASH_SIZE: An integer
 5     @return: An integer
 6     """
 7     def hashCode(self, key, HASH_SIZE):
 8         # write your code here
 9         ans = 0
10         for x in key:
11             ans = (ans *33 + ord(x))%HASH_SIZE
12             
13         return ans

View Code

129. 重哈希

哈希表容量的大小在一开始是不确定的。如果哈希表存储的元素太多（如超过容量的十分之一），我们应该将哈希表容量扩大一倍，并将所有的哈希值重新安排。假设你有如下一哈希表：

size=3, capacity=4

[null, 21, 14, null]
       ↓    ↓
       9   null
       ↓
      null

哈希函数为：

int hashcode(int key, int capacity) {
    return key % capacity;
}

这里有三个数字9，14，21，其中21和9共享同一个位置因为它们有相同的哈希值1(21 % 4 = 9 % 4 = 1)。我们将它们存储在同一个链表中。

重建哈希表，将容量扩大一倍，我们将会得到：

size=3, capacity=8

index:   0    1    2    3     4    5    6   7
hash : [null, 9, null, null, null, 21, 14, null]

给定一个哈希表，返回重哈希后的哈希表。

Example

样例 1

输入 : [null, 21->9->null, 14->null, null]
输出 : [null, 9->null, null, null, null, 21->null, 14->null, null]

 1 """
 2 Definition of ListNode
 3 class ListNode(object):
 4 
 5     def __init__(self, val, next=None):
 6         self.val = val
 7         self.next = next
 8 """
 9 class Solution:
10     """
11     @param hashTable: A list of The first node of linked list
12     @return: A list of The first node of linked list which have twice size
13     """
14     def rehashing(self, hashTable):
15         # write your code here
16         HASH_SIZE = 2 * len(hashTable)
17         new_hash_table = [None for _ in range(HASH_SIZE)]
18         
19         for item in hashTable:
20             point = item
21             while point != None:
22                 self._add_node(new_hash_table, point.val)
23                 point = point.next
24                 
25         return new_hash_table 
26                 
27     def _add_node(self, new_hash_table, value):
28         index = value % (len(new_hash_table))
29         if new_hash_table[index] == None:
30             new_hash_table[index] = ListNode(value)
31         else:
32             self._add_list_node(new_hash_table[index], value)
33     
34     
35     def _add_list_node(self, node, value):
36         if node.next != None:
37             self._add_list_node(node.next, value)
38         else:
39             node.next = ListNode(value)
40

View Code

138. 子数组之和

Notice

至少有一个子数组的和为 0

 1 class Solution:
 2     """
 3     @param nums: A list of integers
 4     @return: A list of integers includes the index of the first number and the index of the last number
 5     """
 6     def subarraySum(self, nums):
 7         # write your code here
 8         prefix_hash = {0:-1}
 9         prefix_sum = 0
10         for index, num in enumerate(nums):
11             prefix_sum += num
12             if prefix_sum in prefix_hash.keys():
13                 return [prefix_hash[prefix_sum]+1, index]
14             prefix_hash[prefix_sum] = index
15         
16         return [-1, -1]

View Code

325. 和等于 k 的最长子数组长度

难度中等

给定一个数组 nums 和一个目标值 k，找到和等于 k 的最长子数组长度。如果不存在任意一个符合要求的子数组，则返回 0。

注意:
nums 数组的总和是一定在 32 位有符号整数范围之内的。

示例 1:

输入: nums = [1, -1, 5, -2, 3], k = 3
输出: 4 
解释: 子数组 [1, -1, 5, -2] 和等于 3，且长度最长。

示例 2:

输入: nums = [-2, -1, 2, 1], k = 1
输出: 2 
解释: 子数组 [-1, 2] 和等于 1，且长度最长。

进阶:
你能使时间复杂度在 O(n) 内完成此题吗?

 1 class Solution:
 2     def maxSubArrayLen(self, nums: List[int], k: int) -> int:
 3         prefix_hash = {0:-1}
 4         prefix_sum = 0
 5         ans = 0
 6         for index, num in enumerate(nums):
 7             prefix_sum += num
 8             if prefix_sum-k in prefix_hash.keys():
 9                 ans = max(index-prefix_hash[prefix_sum-k], ans)
10                 
11             if prefix_sum not in prefix_hash.keys():
12                 prefix_hash[prefix_sum] = index
13         
14         return ans

View Code

560. 和为K的子数组

难度中等

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

说明 :

数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

 1 class Solution:
 2     def subarraySum(self, nums: List[int], k: int) -> int:
 3         prefix_hash = {0:1}
 4         prefix_sum = 0
 5         ans = 0
 6         for index, num in enumerate(nums):
 7             prefix_sum += num
 8             if prefix_sum-k in prefix_hash.keys():
 9                 ans += prefix_hash[prefix_sum-k]
10                 
11             prefix_hash[prefix_sum] = prefix_hash.setdefault(prefix_sum, 0) + 1
12         
13         return ans

View Code

hash表 算法模板和相关题目

706. 设计哈希映射

128. 哈希函数

Example

Clarification

129. 重哈希

Example

138. 子数组之和

Example

Notice

325. 和等于 k 的最长子数组长度

560. 和为K的子数组

相关推荐

hash表算法模板和相关题目