[資料結構筆記] Hashing
Hash maps and sets
演算法系列文
[Array & String]
- Sliding window
- Two Pointer & Prefix sum[Hashing]
Hashing 其實是一種 data structure,以 JS 來說就是 Set/Map,若對他們基礎語法還不熟可以看我之前在鐵人賽的介紹 。
- Hash map: is an unordered data structure that stores key-value pairs,擁有很好的效率 (取值,新增刪除都是 O(1) )
- Hash set: is an unordered data structure that with no duplicate values,當我們在在意值存不存在使用 set 簡單很多
Hash map’s key need to be immutable
要特別注意的是 Hash map 的 key 值必須為 immutable (value 則可以為任何型別)
let lookup = new Map()
// 通常會用 primitive type 存所以沒啥問題
lookup.set(1, 1)
lookup.set('1', 1)
lookup.set(true, 2)
// Arrays as keys? 但若你要存 array 會永遠抓不到值,因為他是 mutable
lookup.set([1,2], 1)
lookup.get([1,2], 1) // undefined
實務上常見的方法是先把 mutable type 的資料轉成 string 或 tuple 再放到 key 裡
lookup.set([1,2].join(), 'array to string')
lookup.get('1,2') // 'array to string'
// note: 是 join() 不是 join('')
// 不然 [1,11], [111] 會是一樣的
Key Point
Hashing 在 leetcode 上從只需運用原生方法存值取值的 easy 題,到結合其他不同演算法概念的 hard 都有,基本上無續存值的都會用到它
- using a hash map to store the frequency
- using a hash map to store the position(index) in array
Clean Code Tip
再使用 hash map 時,會不斷看到先用 has 判斷是否存在,不存在就初始化,存在再 + 1 之類,可以參考以下簡短寫法
let lookup = new Map()
if( lookup.has(str) ){
lookup.set(str, lookup.get(str) + 1 )
} else {
lookup.set(str, 1 )
}
// 改成以下更簡短
lookup.set(str, (lookup.get(str) ?? 0) + 1 )
Checking for existence
(難度 ★) 單純存值取值的變化題
以下題目只會稍微帶過因為真的不難,沒什麼好解釋 XD
數字陣列 nums
中,找出兩個相加等於 target
的 index 位置
Using map: key 存數字,value 存 index 位置 。(1. Two Sum)
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
/**
* Example 1
* Input: nums = [2,7,11,15], target = 9
* Output: [0,1]
*/
var twoSum = function(nums, target) {
let lookup = new Map();
for(let i=0; i< nums.length; i++){
if(lookup.has(target - nums[i])){
return [i, lookup.get(target - nums[i])]
}
lookup.set(nums[i], i)
}
};
找第一個重覆的字元
Using set: 只在意是否出現過,所以用 set 存字元。(2351. First Letter to Appear Twice)
/**
* @param {string} s
* @return {character}
*/
/**
* Example 1
* Input: s = "abccbaacz"
* Output: "c"
*/
var repeatedCharacter = function(s) {
let lookup = new Set()
for(const char of s){
if(lookup.has(char)){
return char
}
lookup.add(char)
}
};
Counting
(難度 ★★★) 通常會加上 Two pointer、Sliding window、 prefix sum 概念
這種進階題 hashing 只是幫助存值,真的要解出來還是必須熟悉不同的演算法
Find the length of the longest substring s: String[]
that contains at most k
distinct characters.
Using map: key 存值,value 存 frequency
- 要找連續最長但只能有 k 個不同字元,看到連續字樣所以猜應該是 sliding window
- 需要存字元,所以 using map: key 存字元,value 存 frequency
L
,R
,若字元 >
k 那L++
, 且 delete 在 lookup 上的L
/**
* @param {string} s
* @param {number} k
* @return {number}
*/
/**
* Example 1
* Input: s = "eceba", k = 2
* Output: 3
*/
let findLongestSubstring = (s, k) => {
let lookup = new Map();
let left = 0, ans = 0;
for (let right = 0; right < s.length; right++) {
lookup.set(s[right], (counts.get(s[right]) || 0) + 1);
while (lookup.size > k) {
lookup.set(s[left], lookup.get(s[left]) - 1);
if (lookup.get(s[left]) == 0) {
lookup.delete(s[left]);
}
left++;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}
Given an integer array nums
and an integer k
, find the number of subarrays whose sum is equal to k
Using map: key 存 prefixSum,value 存 frequency 。(560. Subarray Sum Equals K)
- 看到 sums of a subarray 所以應該會用到 sliding window + prefix sum
- Using Map: key 存
prefixSum -k
, value 存 frequency,記得要先初始化 0: 0
[1,1,1]
[1,2,3] // prefix sum
let lookup = new Map([[0,1]]) // 記得要先初始化 0: 1
// 加總等於 2, 從 lookup 找以下
[-1, 0, 1]
-1 沒找到,此時 lookup: {0: 1, 1: 1}
0 找到,此時 lookup: {0: 1, 1: 1, 2: 1}
1 找到,此時 lookup: {0: 1, 1: 1, 2: 1, 3: 1}
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
/**
* Example 1
* Input: nums = [1,1,1], k = 2
* Output: 2
* Example 2
* Input: [1,2,3], k = 3
* Output: 2
*/
var subarraySum = function(nums, k) {
let lookup = new Map([[0,1]])
let count = 0
let prefixSum = 0
for(let i =0; i< nums.length; i++){
prefixSum += nums[i]
if( lookup.has(prefixSum - k) ){
count += lookup.get(prefixSum - k)
}
lookup.set(prefixSum, (lookup.get(prefixSum) ?? 0) + 1)
}
return count
};
- 1248. Count Number of Nice Subarrays 原理也一樣只是 Nice Subarrays 從 sum = k 變成基數
Given a string s
, determine if all characters have the same frequency
Using map: key 存字元,value 存 frequency。(1941. Check if All Characters Have Equal Number of Occurrences)
- Using Map: key 存字元, value 存 frequency
/**
* @param {string} s
* @return {boolean}
*/
/**
* Example 1
* Input: s = "abacbc"
* Output: true
* Example 2
* Input: s = "aaabb"
* Output: false
*/
var areOccurrencesEqual = function(s) {
let lookup = new Map()
for(const str of s){
lookup.set(str, (lookup.get(str) ?? 0) + 1 )
}
return new Set(lookup.values()).size === 1
};
Find Players With Zero or One Losses
這題算是蠻有挑戰性,要整理好思緒再寫!題目基本上就是給你一連串 Array<[winner, loser]>
,然後要回傳完全沒輸跟只輸一場的 player
/**
* Example 1
* Input: matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
* Output: [[1,2,10],[4,5,7,8]]
* Example 2
* Input: matches = [[2,3],[1,3],[5,4],[6,4]]
* Output: [[1,2,5,6],[]]
*/
/**
* @param {number[][]} matches
* @return {number[][]}
*/
var findWinners = function(matches) {}
- Using Map 這個 map 只關心輸了幾場: key 存 player, value 存輸了幾場
[[1,3],[2,3],[3,6]]
{
1: 0 // 代表沒輸
3: 2 // 輸兩場,因為不在意贏了幾場所以贏那場不須列入計算
2: 0 // 全贏
6: 1 // 輸一場
}
// 最後可以得知 value = 0 就是全贏, value = 1 就是只輸一場
Given an array of strings strs
, group the anagrams together. You can return the answer in any order.
/**
* Example 1
* Input: strs = ["eat","tea","tan","ate","nat","bat"]
* Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
* Example 2
* Input: strs = [""]
* Output: [[""]]
*/
/**
* @param {string[]} strs
* @return {string[][]}
*/
var groupAnagrams = function(strs) {}
- 先排序
- Using Map: key 存排序後的例如
“eat”
, value 存 anagrams 例如[“ate”,”eat”,”tea”]
Max Sum of a Pair With Equal Sum of Digits
Sum of Digits 也就是數字個別加總,例如 18 就是 9(1+8), 43 就是 7(4+3),有以下兩種常見方法,當然第二種效率好很多
/**
* Example 1
* Input: nums = [18,43,36,13,7]
* Output: 54
* Example 2
* Input: nums = [10,12,19,14]
* Output: -1
*/
/**
* @param {string[]} strs
* @return {string[][]}
*/
var maximumSum = function(nums) {}
- Using map: key 放
sumOfDigit
, value 放index
- 最後找到
nums[index1] + nums[index2]
Longest Substring Without Repeating Characters
/**
* Example 1
* Input: s = "abcabcbb"
* Output: 3
* Example 2
* Input: s = "pwwkew"
* Output: 3
*/
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {}
這是我最近的面試題 XD
- 看到 Longest Substring 所以也是 sliding window
- Using set: 存字元
- 利用
L
,R
,若字元重覆那L ++
一開始我是這樣寫
var getLengthOfLongestSubstring = function(s) {
let L = 0;
let R = 0;
let longest = 0
let lookup = new Set()
while(R < s.length){
if(lookup.has(s[R])){
longest = Math.max(longest, R - L)
lookup.delete(s[L])
L ++;
}
lookup.add(s[R])
R++
}
return longest
};
但不符合 ”pwwkew”
跟“ ”
test case ,後來 if 變 while, longest 拉到最下面才成功
var getLengthOfLongestSubstring = function(s) {
let L = 0;
let R = 0;
let longest = 0
let lookup = new Set()
while(R < s.length){
// 若連續兩個字元重覆例如 "pwwkew" L 就需要+兩次
// R = 2 碰到 w, L=1, 但此時又是 w 所以 L 需要在往右
while(lookup.has(s[R])){
lookup.delete(s[L])
L ++;
}
lookup.add(s[R])
R++
longest = Math.max(longest, R - L)
}
return longest
};