Hash Map¶
Table of Contents¶
- 383. Ransom Note (Easy)
- 350. Intersection of Two Arrays II (Easy)
- 1. Two Sum (Easy)
- 409. Longest Palindrome (Easy)
- 1365. How Many Numbers Are Smaller Than the Current Number (Easy)
- 202. Happy Number (Easy)
- 454. 4Sum II (Medium)
383. Ransom Note¶
"""
- Return `True` if the ransom note can be constructed from the magazines, otherwise, return `False`.
"""
from collections import Counter, defaultdict
# Array
def canConstructArray(ransomNote: str, magazine: str) -> bool:
if len(ransomNote) > len(magazine):
return False
record = [0 for _ in range(26)]
for i in magazine:
record[ord(i) - ord("a")] += 1
for j in ransomNote:
record[ord(j) - ord("a")] -= 1
for i in record:
if i < 0:
return False
return True
# Dict
def canConstructDict(ransomNote: str, magazine: str) -> bool:
if len(ransomNote) > len(magazine):
return False
record = defaultdict(int)
for i in magazine:
record[i] += 1
for j in ransomNote:
if j not in record or record[j] == 0:
return False
record[j] -= 1
return True
# Counter
def canConstructCounter(ransomNote: str, magazine: str) -> bool:
return not Counter(ransomNote) - Counter(magazine)
ransomNote = "aa"
magazine = "aab"
print(canConstructArray(ransomNote, magazine)) # True
print(canConstructDict(ransomNote, magazine)) # True
print(canConstructCounter(ransomNote, magazine)) # True
350. Intersection of Two Arrays II¶
"""
- Return the intersection of two arrays.
"""
from collections import defaultdict
from typing import List
# Hashmap
def intersect(nums1: List[int], nums2: List[int]) -> List[int]:
hashmap = defaultdict(int) # {num: count}
result = []
for i in nums1:
hashmap[i] += 1
for i in nums2:
if hashmap[i] > 0:
result.append(i)
hashmap[i] -= 1
return result
# |-------------|-------------|--------------|
# | Approach | Time | Space |
# |-------------|-------------|--------------|
# | Hashmap | O(n + m) | O(min(n, m)) |
# |-------------|-------------|--------------|
nums1 = [1, 2, 2, 1]
nums2 = [2, 2]
print(intersect(nums1, nums2)) # [2, 2]
1. Two Sum¶
"""
- Return the indices of the two numbers such that they add up to a specific target.
- Approach: Use a hashmap to store the indices of the numbers.
- Time Complexity: O(n)
- Space Complexity: O(n)
"""
from typing import List
def two_sum(nums: List[int], target: int) -> List[int]:
hashmap = {} # val: idx
for idx, val in enumerate(nums):
if (target - val) in hashmap:
return [hashmap[target - val], idx]
hashmap[val] = idx
return []
def test_two_sum():
assert two_sum([2, 7, 11, 15], 9) == [0, 1]
assert two_sum([3, 2, 4], 6) == [1, 2]
assert two_sum([3, 3], 6) == [0, 1]
assert two_sum([1, 2, 3, 4, 5], 10) == []
assert two_sum([-1, -2, -3, -4, -5], -8) == [2, 4]
#include <cassert>
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;
for (size_t i = 0; i < nums.size(); i++) {
int diff = target - nums[i];
if (map.find(diff) != map.end()) {
return {map[diff], (int)i};
}
map[nums[i]] = (int)i;
}
return {-1, -1};
}
};
int main() {
Solution solution;
vector<int> nums = {2, 7, 11, 15};
int target = 9;
vector<int> result = solution.twoSum(nums, target);
assert((result == vector<int>{0, 1}));
return 0;
}
409. Longest Palindrome¶
"""
- Return the length of the longest palindrome that can be built with the characters in the string.
"""
def longestPalindrome(s: str) -> int:
hashmap = dict()
result = 0
for char in s:
if char not in hashmap or hashmap[char] == 0:
hashmap[char] = 1
else:
result += 2
hashmap[char] = 0
if any(hashmap.values()):
result += 1
return result
print(longestPalindrome("abccccdd")) # 7
1365. How Many Numbers Are Smaller Than the Current Number¶
"""
- For each number in the array, return how many numbers are smaller than it.
"""
from typing import List
def smallerNumbersThanCurrent(nums: List[int]) -> List[int]:
sortedNums = sorted(nums)
hashmap = dict()
for i, num in enumerate(sortedNums):
if num not in hashmap:
hashmap[num] = i
result = []
for i in range(len(sortedNums)):
result.append(hashmap[nums[i]])
return result
nums = [8, 1, 2, 2, 3]
print(smallerNumbersThanCurrent(nums)) # [4, 0, 1, 1, 3]
202. Happy Number¶
"""
- Return `True` if the number is a happy number, otherwise, return `False`.
- A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
"""
def isHappy(n: int) -> bool:
def getSum(n):
sum_of_squares = 0
while n:
a, b = divmod(n, 10)
sum_of_squares += b**2
n = a
return sum_of_squares
record = set()
while True:
if n == 1:
return True
if n in record:
return False
else:
record.add(n)
n = getSum(n)
n = 19
print(isHappy(n)) # True
#include <cassert>
#include <unordered_set>
using namespace std;
class Solution {
public:
int getNext(int n) {
int res = 0;
while (n) {
int mod = n % 10;
res += mod * mod;
n /= 10;
}
return res;
}
bool isHappy(int n) {
unordered_set<int> seen;
while (n != 1) {
n = getNext(n);
if (seen.find(n) != seen.end()) return false;
seen.insert(n);
}
return true;
}
};
int main() {
Solution s;
assert(s.isHappy(19) == true);
assert(s.isHappy(2) == false);
return 0;
}
454. 4Sum II¶
"""
- Return the number of tuples `(i, j, k, l)` such that `A[i] + B[j] + C[k] + D[l] == 0`.
"""
from collections import defaultdict
from typing import List
def fourSumCount(
nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]
) -> int:
sumAB = defaultdict(int)
result = 0
for i in nums1:
for j in nums2:
sumAB[i + j] += 1
for i in nums3:
for j in nums4:
if -(i + j) in sumAB:
result += sumAB[-(i + j)]
return result
nums1 = [1, 2]
nums2 = [-2, -1]
nums3 = [-1, 2]
nums4 = [0, 2]
print(fourSumCount(nums1, nums2, nums3, nums4)) # 2