[資料結構筆記] Hashing

Hash maps and sets

演算法系列文

[Array & String]
- Sliding window
- Two Pointer & Prefix sum

[Hashing]

Hashing 其實是一種 data structure，以 JS 來說就是 Set/Map，若對他們基礎語法還不熟可以看我之前在鐵人賽的介紹 。

leetcode hash note

• 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

(2225. 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.

49. Group Anagrams

/**
 * 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

2342. Max Sum of a Pair With Equal Sum of Digits

Sum of Digits 也就是數字個別加總，例如 18 就是 9(1+8), 43 就是 7(4+3)，有以下兩種常見方法，當然第二種效率好很多

Sum of Digits

/**
 * 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

3. 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
};