Leetcode Solutions (161 Part Series)
1 Solution: Next Permutation
2 Solution: Trim a Binary Search Tree
… 157 more parts…
3 Leetcode Solutions Index
4 Solution: Minimize Deviation in Array
5 Solution: Vertical Order Traversal of a Binary Tree
6 Solution: Count Ways to Make Array With Product
7 Solution: Smallest String With A Given Numeric Value
8 Solution: Linked List Cycle
9 Solution: Path With Minimum Effort
10 Solution: Concatenation of Consecutive Binary Numbers
11 Solution: Minimum Operations to Make a Subsequence
12 Solution: Longest Harmonious Subsequence
13 Solution: Simplify Path
14 Solution: Building Boxes
15 Solution: Decode XORed Permutation
16 Solution: Binary Tree Right Side View
17 Solution: Find Kth Largest XOR Coordinate Value
18 Solution: Change Minimum Characters to Satisfy One of Three Conditions
19 Solution: Shortest Distance to a Character
20 Solution: Peeking Iterator
21 Solution: Convert BST to Greater Tree
22 Solution: Copy List with Random Pointer
23 Solution: Valid Anagram
24 Solution: Number of Steps to Reduce a Number to Zero
25 Solution: Shortest Path in Binary Matrix
26 Solution: Is Graph Bipartite?
27 Solution: Maximum Score From Removing Substrings (ver. 1)
28 Solution: Maximum Score From Removing Substrings (ver. 2)
29 Solution: Sort the Matrix Diagonally
30 Solution: The K Weakest Rows in a Matrix (ver. 1)
31 Solution: The K Weakest Rows in a Matrix (ver. 2)
32 Solution: Letter Case Permutation
33 Solution: Container With Most Water
34 Solution: Arithmetic Slices
35 Solution: Minimum Remove to Make Valid Parentheses
36 Solution: Roman to Integer
37 Solution: Broken Calculator
38 Solution: Find the Most Competitive Subsequence
39 Solution: Longest Word in Dictionary through Deleting
40 Solution: Search a 2D Matrix II
41 Solution: Score of Parentheses
42 Solution: Shortest Unsorted Continuous Subarray
43 Solution: Validate Stack Sequences
44 Solution: Divide Two Integers (ver. 1)
45 Solution: Divide Two Integers (ver. 2)
46 Solution: Maximum Frequency Stack
47 Solution: Distribute Candies
48 Solution: Set Mismatch (ver. 1)
49 Solution: Set Mismatch (ver. 2)
50 Solution: Missing Number
51 Solution: Intersection of Two Linked Lists
52 Solution: Average of Levels in Binary Tree
53 Solution: Short Encoding of Words (ver. 1)
54 Solution: Design HashMap (ver. 1)
55 Solution: Short Encoding of Words (ver. 2)
56 Solution: Design HashMap (ver. 2)
57 Solution: Remove Palindromic Subsequences
58 Solution: Add One Row to Tree
59 Solution: Integer to Roman
60 Solution: Coin Change
61 Solution: Check If a String Contains All Binary Codes of Size K
62 Solution: Binary Trees With Factors
63 Solution: Swapping Nodes in a Linked List
64 Solution: Encode and Decode TinyURL
65 Solution: Best Time to Buy and Sell Stock with Transaction Fee
66 Solution: Generate Random Point in a Circle
67 Solution: Wiggle Subsequence
68 Solution: Keys and Rooms
69 Solution: Design Underground System
70 Solution: Reordered Power of 2
71 Solution: Vowel Spellchecker
72 Solution: 3Sum With Multiplicity
73 Solution: Advantage Shuffle
74 Solution: Pacific Atlantic Water Flow
75 Solution: Word Subsets
76 Solution: Palindromic Substrings
77 Solution: Reconstruct Original Digits from English
78 Solution: Flip Binary Tree To Match Preorder Traversal
79 Solution: Russian Doll Envelopes
80 Solution: Stamping The Sequence
81 Solution: Palindrome Linked List
82 Solution: Ones and Zeroes
83 Solution: Longest Valid Parentheses
84 Solution: Design Circular Queue
85 Solution: Global and Local Inversions
86 Solution: Minimum Operations to Make Array Equal
87 Solution: Determine if String Halves Are Alike
88 Solution: Letter Combinations of a Phone Number
89 Solution: Verifying an Alien Dictionary
90 Solution: Longest Increasing Path in a Matrix
91 Solution: Deepest Leaves Sum
92 Solution: Beautiful Arrangement II
93 Solution: Flatten Nested List Iterator
94 Solution: Partition List
95 Solution: Fibonacci Number
96 Solution: Remove All Adjacent Duplicates in String II
97 Solution: Number of Submatrices That Sum to Target
98 Solution: Remove Nth Node From End of List
99 Solution: Combination Sum IV
100 Solution: N-ary Tree Preorder Traversal
101 Solution: Triangle
102 Solution: Brick Wall
103 Solution: Count Binary Substrings
104 Solution: Critical Connections in a Network
105 Solution: Rotate Image
106 Solution: Furthest Building You Can Reach
107 Solution: Power of Three
108 Solution: Unique Paths II
109 Solution: Find First and Last Position of Element in Sorted Array
110 Solution: Powerful Integers
111 Solution: Prefix and Suffix Search
112 Solution: Course Schedule III
113 Solution: Running Sum of 1d Array
114 Solution: Non-decreasing Array
115 Solution: Jump Game II
116 Solution: Convert Sorted List to Binary Search Tree
117 Solution: Delete Operation for Two Strings
118 Solution: Super Palindromes
119 Solution: Construct Target Array With Multiple Sums
120 Solution: Count Primes
121 Solution: Maximum Points You Can Obtain from Cards
122 Solution: Range Sum Query 2D – Immutable
123 Solution: Ambiguous Coordinates
124 Solution: Flatten Binary Tree to Linked List
125 Solution: Valid Number
126 Solution: Binary Tree Cameras
127 Solution: Longest String Chain
128 Solution: Find Duplicate File in System
129 Solution: Minimum Moves to Equal Array Elements II
130 Solution: Binary Tree Level Order Traversal
131 Solution: Find and Replace Pattern
132 Solution: N-Queens
133 Solution: To Lower Case
134 Solution: Evaluate Reverse Polish Notation
135 Solution: Partitioning Into Minimum Number Of Deci-Binary Numbers
136 Solution: Maximum Product of Word Lengths
137 Solution: Maximum Erasure Value
138 Solution: N-Queens II
139 Solution: Maximum Gap
140 Solution: Search Suggestions System
141 Solution: Max Area of Island
142 Solution: Interleaving String
143 Solution: Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
144 Solution: Open the Lock
145 Solution: Maximum Performance of a Team
146 Solution: Longest Consecutive Sequence
147 Solution: Min Cost Climbing Stairs
148 Solution: Construct Binary Tree from Preorder and Inorder Traversal
149 Solution: Jump Game VI
150 Solution: My Calendar I
151 Solution: Stone Game VII
152 Solution: Minimum Number of Refueling Stops
153 Solution: Palindrome Pairs
154 Solution: Maximum Units on a Truck
155 Solution: Matchsticks to Square
156 Solution: Generate Parentheses
157 Solution: Number of Subarrays with Bounded Maximum
158 Solution: Swim in Rising Water
159 Solution: Pascal’s Triangle
160 Solution: Out of Boundary Paths
161 Solution: Redundant Connection
This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode’s forums.
Note: This is my second version of a solution for this problem. The first version is more in line with an Easy problem, but it doesn’t really address the actual nature of a hashmap. This solution breaks down in detail what a hashmap accomplishes and why it’s beneficial.
Leetcode Problem #706 (Easy): Design HashMap
Description:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
Design a HashMap without using any built-in hash table libraries.
To be specific, your design should include these functions:
put(key, value): Insert a(key, value)pair into the HashMap. If the value already exists in the HashMap, update the value.get(key): Returns the value to which the specified key is mapped, or-1if this map contains no mapping for the key.remove(key): Remove the mapping for the value key if this map contains the mapping for the key.
Examples:
Example: Input: [“MyHashMap”,”put”,”put”,”get”,”get”,”put”,”get”, “remove”, “get”]
[[],[1,1],[2,2],[1],[3],[2,1],[2],[2],[2]]Output: [null,null,null,1,-1,null,1,null,-1] Explanation: MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);
hashMap.put(2, 2);
hashMap.get(1); // returns 1
hashMap.get(3); // returns -1 (not found)
hashMap.put(2, 1); // update the existing value
hashMap.get(2); // returns 1
hashMap.remove(2); // remove the mapping for 2
hashMap.get(2); // returns -1 (not found)
Constraints:
- All keys and values will be in the range of
[0, 1000000].- The number of operations will be in the range of
[1, 10000].- Please do not use the built-in HashMap library.
Idea:
(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)
Hashmaps were created to speed up the lookup time of data to a hopefully O(1) time. Arrays do this naturally with index lookups, but it becomes more complicated if you’re trying to look up an entry by some other non-index value instead.
We can see from a simple Array solution that it’s easy enough to mimic a key lookup if the keys themselves are integers that are constrained enough to act as their own indexes. But what if they’re not? Or what if they’re some other data type, like strings?
Surprisingly, the idea in that case is somewhat similar. We can still use an Array to store the data, but we must first find a way to transform the key into an index. For that, we look to a hashing function. Hashing functions exist to convert data into a randomized, but reproduceable, integer version of themselves.
In this case, we can use a hashing function to convert the key into an integer within the bounds of our hashmap array’s index range. In an ideal situation, that would allow us to reduce the size of the hashmap array to the maximum number of entries, which is 10^4. Unfortunately, however, it’s always possible for collisions to exist when two keys devolve to the same integer via the hashing function.
To deal with collisions, we can just make each of our hashmap array’s elements a linked list. This will allow us to treat them like a simple stack, where we look first at the most recently added node and then move to the next until we find the correct key.
Since navigating a linked list will drop our lookup time past O(1), the goal of a good hashing function is to randomize the keys’ hashes enough to limit collisions as much as possible for a given hashmap array size, thus keeping down the average lookup time complexity.
Therefore, the size of our hashmap array should probably be at least equal to the number of entries. Increasing the size of the hashmap array will naturally reduce collisions (and therefore time complexity) at the expense of space complexity, and vice versa. The tradeoff is highly dependent on the quality of the hashing function.
There are many, many hashing functions out there, but for this problem we’ll use a very simple multiplicative hashing function utilizing a large prime multiplier and then modulo the result to the desired size (also a prime) of our hashmap array. This should hopefully result in an even distribution of the entries throughout the hashmap array.
The get() method is fairly easy, then. We just hash() our key, access the corresponding bucket in our hashmap array (data), and navigate through the linked list (if necessary) and return the correct val, or -1 if the key is not found.
For the put() method, we should first remove() any earlier instance of that key to avoid chaining multiple versions of a key definition in our linked list. Then we simply form a new ListNode at the head of the proper hashmap bucket, pushing any others back.
The remove() method will be similar to the get() method, except that we need to find and stitch together the nodes on either side of the node that matches the key, removing it from the linked list entirely.
Implementation:
Python has deque and Java has LinkedList that can do the work of the linked list management, but it comes at the cost of efficiency. In this case, it’s not really worth using over a custom ListNode class implementation.
Javascript Code:
(Jump to: Problem Description || Solution Idea)
class ListNode {
constructor(key, val, next) {
this.key = key
this.val = val
this.next = next
}
}
class MyHashMap {
constructor() {
this.size = 19997
this.mult = 12582917
this.data = new Array(this.size)
}
hash(key) {
return key * this.mult % this.size
}
put(key, val) {
this.remove(key)
let h = this.hash(key)
let node = new ListNode(key, val, this.data[h])
this.data[h] = node
}
get(key) {
let h = this.hash(key), node = this.data[h]
for (; node; node = node.next)
if (node.key === key) return node.val
return -1
}
remove(key) {
let h = this.hash(key), node = this.data[h]
if (!node) return
if (node.key === key) this.data[h] = node.next
else for (; node.next; node = node.next)
if (node.next.key === key) {
node.next = node.next.next
return
}
}
};
Enter fullscreen mode Exit fullscreen mode
Python Code:
(Jump to: Problem Description || Solution Idea)
class ListNode:
def __init__(self, key, val, nxt):
self.key = key
self.val = val
self.next = nxt
class MyHashMap:
def __init__(self):
self.size = 19997
self.mult = 12582917
self.data = [None for _ in range(self.size)]
def hash(self, key):
return key * self.mult % self.size
def put(self, key, val):
self.remove(key)
h = self.hash(key)
node = ListNode(key, val, self.data[h])
self.data[h] = node
def get(self, key):
h = self.hash(key)
node = self.data[h]
while node:
if node.key == key: return node.val
node = node.next
return -1
def remove(self, key: int):
h = self.hash(key)
node = self.data[h]
if not node: return
if node.key == key:
self.data[h] = node.next
return
while node.next:
if node.next.key == key:
node.next = node.next.next
return
node = node.next
Enter fullscreen mode Exit fullscreen mode
Java Code:
(Jump to: Problem Description || Solution Idea)
class ListNode {
int key, val;
ListNode next;
public ListNode(int key, int val, ListNode next) {
this.key = key;
this.val = val;
this.next = next;
}
}
class MyHashMap {
static final int size = 19997;
static final int mult = 12582917;
ListNode[] data;
public MyHashMap() {
this.data = new ListNode[size];
}
private int hash(int key) {
return (int)((long)key * mult % size);
}
public void put(int key, int val) {
remove(key);
int h = hash(key);
ListNode node = new ListNode(key, val, data[h]);
data[h] = node;
}
public int get(int key) {
int h = hash(key);
ListNode node = data[h];
for (; node != null; node = node.next)
if (node.key == key) return node.val;
return -1;
}
public void remove(int key) {
int h = hash(key);
ListNode node = data[h];
if (node == null) return;
if (node.key == key) data[h] = node.next;
else for (; node.next != null; node = node.next)
if (node.next.key == key) {
node.next = node.next.next;
return;
}
}
}
Enter fullscreen mode Exit fullscreen mode
C++ Code:
(Jump to: Problem Description || Solution Idea)
struct Node {
public:
int key, val;
Node* next;
Node(int k, int v, Node* n) {
key = k;
val = v;
next = n;
}
};
class MyHashMap {
public:
const static int size = 19997;
const static int mult = 12582917;
Node* data[size];
int hash(int key) {
return (int)((long)key * mult % size);
}
void put(int key, int val) {
remove(key);
int h = hash(key);
Node* node = new Node(key, val, data[h]);
data[h] = node;
}
int get(int key) {
int h = hash(key);
Node* node = data[h];
for (; node != NULL; node = node->next)
if (node->key == key) return node->val;
return -1;
}
void remove(int key) {
int h = hash(key);
Node* node = data[h];
if (node == NULL) return;
if (node->key == key) data[h] = node->next;
else for (; node->next != NULL; node = node->next)
if (node->next->key == key) {
node->next = node->next->next;
return;
}
}
};
Enter fullscreen mode Exit fullscreen mode
Leetcode Solutions (161 Part Series)
1 Solution: Next Permutation
2 Solution: Trim a Binary Search Tree
… 157 more parts…
3 Leetcode Solutions Index
4 Solution: Minimize Deviation in Array
5 Solution: Vertical Order Traversal of a Binary Tree
6 Solution: Count Ways to Make Array With Product
7 Solution: Smallest String With A Given Numeric Value
8 Solution: Linked List Cycle
9 Solution: Path With Minimum Effort
10 Solution: Concatenation of Consecutive Binary Numbers
11 Solution: Minimum Operations to Make a Subsequence
12 Solution: Longest Harmonious Subsequence
13 Solution: Simplify Path
14 Solution: Building Boxes
15 Solution: Decode XORed Permutation
16 Solution: Binary Tree Right Side View
17 Solution: Find Kth Largest XOR Coordinate Value
18 Solution: Change Minimum Characters to Satisfy One of Three Conditions
19 Solution: Shortest Distance to a Character
20 Solution: Peeking Iterator
21 Solution: Convert BST to Greater Tree
22 Solution: Copy List with Random Pointer
23 Solution: Valid Anagram
24 Solution: Number of Steps to Reduce a Number to Zero
25 Solution: Shortest Path in Binary Matrix
26 Solution: Is Graph Bipartite?
27 Solution: Maximum Score From Removing Substrings (ver. 1)
28 Solution: Maximum Score From Removing Substrings (ver. 2)
29 Solution: Sort the Matrix Diagonally
30 Solution: The K Weakest Rows in a Matrix (ver. 1)
31 Solution: The K Weakest Rows in a Matrix (ver. 2)
32 Solution: Letter Case Permutation
33 Solution: Container With Most Water
34 Solution: Arithmetic Slices
35 Solution: Minimum Remove to Make Valid Parentheses
36 Solution: Roman to Integer
37 Solution: Broken Calculator
38 Solution: Find the Most Competitive Subsequence
39 Solution: Longest Word in Dictionary through Deleting
40 Solution: Search a 2D Matrix II
41 Solution: Score of Parentheses
42 Solution: Shortest Unsorted Continuous Subarray
43 Solution: Validate Stack Sequences
44 Solution: Divide Two Integers (ver. 1)
45 Solution: Divide Two Integers (ver. 2)
46 Solution: Maximum Frequency Stack
47 Solution: Distribute Candies
48 Solution: Set Mismatch (ver. 1)
49 Solution: Set Mismatch (ver. 2)
50 Solution: Missing Number
51 Solution: Intersection of Two Linked Lists
52 Solution: Average of Levels in Binary Tree
53 Solution: Short Encoding of Words (ver. 1)
54 Solution: Design HashMap (ver. 1)
55 Solution: Short Encoding of Words (ver. 2)
56 Solution: Design HashMap (ver. 2)
57 Solution: Remove Palindromic Subsequences
58 Solution: Add One Row to Tree
59 Solution: Integer to Roman
60 Solution: Coin Change
61 Solution: Check If a String Contains All Binary Codes of Size K
62 Solution: Binary Trees With Factors
63 Solution: Swapping Nodes in a Linked List
64 Solution: Encode and Decode TinyURL
65 Solution: Best Time to Buy and Sell Stock with Transaction Fee
66 Solution: Generate Random Point in a Circle
67 Solution: Wiggle Subsequence
68 Solution: Keys and Rooms
69 Solution: Design Underground System
70 Solution: Reordered Power of 2
71 Solution: Vowel Spellchecker
72 Solution: 3Sum With Multiplicity
73 Solution: Advantage Shuffle
74 Solution: Pacific Atlantic Water Flow
75 Solution: Word Subsets
76 Solution: Palindromic Substrings
77 Solution: Reconstruct Original Digits from English
78 Solution: Flip Binary Tree To Match Preorder Traversal
79 Solution: Russian Doll Envelopes
80 Solution: Stamping The Sequence
81 Solution: Palindrome Linked List
82 Solution: Ones and Zeroes
83 Solution: Longest Valid Parentheses
84 Solution: Design Circular Queue
85 Solution: Global and Local Inversions
86 Solution: Minimum Operations to Make Array Equal
87 Solution: Determine if String Halves Are Alike
88 Solution: Letter Combinations of a Phone Number
89 Solution: Verifying an Alien Dictionary
90 Solution: Longest Increasing Path in a Matrix
91 Solution: Deepest Leaves Sum
92 Solution: Beautiful Arrangement II
93 Solution: Flatten Nested List Iterator
94 Solution: Partition List
95 Solution: Fibonacci Number
96 Solution: Remove All Adjacent Duplicates in String II
97 Solution: Number of Submatrices That Sum to Target
98 Solution: Remove Nth Node From End of List
99 Solution: Combination Sum IV
100 Solution: N-ary Tree Preorder Traversal
101 Solution: Triangle
102 Solution: Brick Wall
103 Solution: Count Binary Substrings
104 Solution: Critical Connections in a Network
105 Solution: Rotate Image
106 Solution: Furthest Building You Can Reach
107 Solution: Power of Three
108 Solution: Unique Paths II
109 Solution: Find First and Last Position of Element in Sorted Array
110 Solution: Powerful Integers
111 Solution: Prefix and Suffix Search
112 Solution: Course Schedule III
113 Solution: Running Sum of 1d Array
114 Solution: Non-decreasing Array
115 Solution: Jump Game II
116 Solution: Convert Sorted List to Binary Search Tree
117 Solution: Delete Operation for Two Strings
118 Solution: Super Palindromes
119 Solution: Construct Target Array With Multiple Sums
120 Solution: Count Primes
121 Solution: Maximum Points You Can Obtain from Cards
122 Solution: Range Sum Query 2D – Immutable
123 Solution: Ambiguous Coordinates
124 Solution: Flatten Binary Tree to Linked List
125 Solution: Valid Number
126 Solution: Binary Tree Cameras
127 Solution: Longest String Chain
128 Solution: Find Duplicate File in System
129 Solution: Minimum Moves to Equal Array Elements II
130 Solution: Binary Tree Level Order Traversal
131 Solution: Find and Replace Pattern
132 Solution: N-Queens
133 Solution: To Lower Case
134 Solution: Evaluate Reverse Polish Notation
135 Solution: Partitioning Into Minimum Number Of Deci-Binary Numbers
136 Solution: Maximum Product of Word Lengths
137 Solution: Maximum Erasure Value
138 Solution: N-Queens II
139 Solution: Maximum Gap
140 Solution: Search Suggestions System
141 Solution: Max Area of Island
142 Solution: Interleaving String
143 Solution: Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
144 Solution: Open the Lock
145 Solution: Maximum Performance of a Team
146 Solution: Longest Consecutive Sequence
147 Solution: Min Cost Climbing Stairs
148 Solution: Construct Binary Tree from Preorder and Inorder Traversal
149 Solution: Jump Game VI
150 Solution: My Calendar I
151 Solution: Stone Game VII
152 Solution: Minimum Number of Refueling Stops
153 Solution: Palindrome Pairs
154 Solution: Maximum Units on a Truck
155 Solution: Matchsticks to Square
156 Solution: Generate Parentheses
157 Solution: Number of Subarrays with Bounded Maximum
158 Solution: Swim in Rising Water
159 Solution: Pascal’s Triangle
160 Solution: Out of Boundary Paths
161 Solution: Redundant Connection
暂无评论内容