Data Structure and Algorithm 8 | Hashtable

1. Hashtable

(1) Hashset Implementation

Design a hashset.

Leetcode 75.

​x
1
class MyHashSet:
2
​
3
    def __init__(self):
4
        self.nbuckets = 10000
5
        self.set = [[] for _ in range(self.nbuckets)]
6
​
7
    def add(self, key: int) -> None:
8
        if not self.contains(key):
9
            index = key % self.nbuckets
10
            self.set[index].append(key)
11
​
12
    def remove(self, key: int) -> None:
13
        if self.contains(key):
14
            index = key % self.nbuckets
15
            self.set[index].remove(key)
16
        
17
    def contains(self, key: int) -> bool:
18
        index = key % self.nbuckets
19
        return key in self.set[index]

(2) Hashset Implementation

Design a hashmap.

Leetcode 75.

xxxxxxxxxx
17
1
class MyHashMap:
2
​
3
    def __init__(self):
4
        self.map = {}
5
​
6
    def put(self, key: int, value: int) -> None:
7
        self.map[key] = value
8
        
9
    def get(self, key: int) -> int:
10
        if key in self.map:
11
            return self.map[key]
12
        else:
13
            return -1
14
​
15
    def remove(self, key: int) -> None:
16
        if key in self.map:
17
            self.map.pop(key)

(3) Single Number

Find the only number appeared once.

Leetcode 136.

xxxxxxxxxx
12
1
class Solution:
2
    def singleNumber(self, nums: List[int]) -> int:
3
        
4
        visited = set()
5
        
6
        for num in nums:
7
            if num not in visited:
8
                visited.add(num)
9
            else:
10
                visited.remove(num)
11
                
12
        return visited.pop()

(4) Happy Number

Check if an integer follows the rule of a happy number.

Leetcode 202.

xxxxxxxxxx
19
1
class Solution:
2
    def isHappy(self, n: int) -> bool:
3
        
4
        visited = set()
5
        visited.add(n)
6
        
7
        while True:
8
            
9
            next_n = sum([int(i)**2 for i in str(n)])
10
            
11
            if next_n == 1:
12
                return True
13
            
14
            elif next_n in visited:
15
                return False
16
            
17
            else:
18
                visited.add(next_n)
19
                n = next_n

(5) Two Sum

Find two values sum up to target.

Leetcode 1.

xxxxxxxxxx
11
1
class Solution(object):
2
    def twoSum(self, nums, target):
3
        
4
        hashmap = {o: i for i, o in enumerate(nums)}
5
        
6
        for i in range(len(nums)):
7
            
8
            j = target - nums[i]
9
            
10
            if j in hashmap and hashmap[j] != i:
11
                return [i, hashmap[j]]

(6) Isomorphic Strings

Leetcode 205.

xxxxxxxxxx
26
1
class Solution:
2
    def isIsomorphic(self, s: str, t: str) -> bool:
3
        
4
        hashmap = {}
5
        
6
        for i in range(len(s)):
7
            if s[i] in hashmap:
8
                if hashmap[s[i]] != t[i]:
9
                    return False
10
                else:
11
                    continue
12
            else:
13
                hashmap[s[i]] = t[i]
14
                
15
        hashmap = {}
16
        
17
        for i in range(len(t)):
18
            if t[i] in hashmap:
19
                if hashmap[t[i]] != s[i]:
20
                    return False
21
                else:
22
                    continue
23
            else:
24
                hashmap[t[i]] = s[i]
25
                
26
        return True

(7) Find Restaurant

Trick: mapping keywords to index.

Leetcode 599.

xxxxxxxxxx
18
1
class Solution:
2
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
3
        
4
        minval = math.inf
5
        keyword = []
6
        
7
        map1 = {o:i for i, o in enumerate(list1)}
8
        map2 = {o:i for i, o in enumerate(list2)}
9
        
10
        for key in set(list1).intersection(set(list2)):
11
            sumval = map1[key] + map2[key]
12
            if sumval < minval:
13
                minval = sumval
14
                keyword = [key]
15
            elif sumval == minval:
16
                keyword.append(key)
17
​
18
        return keyword