[筆記] AlphaCamp 不只是刷題的 Leetcode 訓練營

章節連結

課程相關資訊
內容

Map
Set
HashMap
HashMap Collision 的問題

LeetCode 題目

448. Find All Numbers Disappeared in an Array
451. Sort Characters By Frequency
80. Remove Duplicates from Sorted Array II

一腳踏入軟體工程師寫 Code 的世界，不免俗地會碰上 Leetcode 的測驗，來測試你的溝通力、系統性地解決問題的能力和如何化抽象為具體。第三週的活動以 Map 和 Set 為主。

課程對應章節：Week3 U22~U24

請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。

內容

Map

在高階的程式語言(如：JavaScript, Python, Ruby…等)中，會提供 Map 和 Set 的方法。若以 JavaScript 中的 new Map() 為例子：

// map 中的資料是有順序的，這點和 object 有明顯不同。
// 同時，後者的 key 只能是字串
let map = new Map([
  ["eins", "zwei","trei"],
]);

// 可以有如 CRUD 的 Get, Set 和 Delete 方法
map.set("deux", "zwei");
map.get("deux")
map.delete("deux");

// 或是轉換成類似 array (array-like) 的結構
map.keys()
map.values()
map.entries()

// map 中的資料是有順序的，這點和 object 有明顯不同。

// 同時，後者的 key 只能是字串

let map = new Map([

["eins", "zwei","trei"],

]);

// 可以有如 CRUD 的 Get, Set 和 Delete 方法

map.set("deux", "zwei");

map.get("deux")

map.delete("deux");

// 或是轉換成類似 array (array-like) 的結構

map.keys()

map.values()

map.entries()

Set

數學上的交集(Intersection)的概念，而且在 Set 裡面的值一定是唯一的，如果有重複的輸入會被忽略，它並沒有內建 get() 的用法。因為 Set 多半是會跟 Set 來進行比較。

HashMap

雜湊表（Hash table，中國方面稱為哈希表），是依據鍵（Key）而直接查詢在記憶體儲存位置的資料結構。換言之，透過輸入函數，將值映射到表中一個位置來查詢記錄，這加快了查找速度。以數學的角度而言，這樣的映射函數被稱做雜湊函數，存放記錄的數組稱做雜湊表。

HashMap Collision 的問題

1. 用 Linked List 的方式，來依序連結
2. 如果有占用，就往下移一位，並以此類推
3. 如果 Bucket 不夠怎麼辦？可以使用 Dynamic Hash

LeetCode 題目

448. Find All Numbers Disappeared in an Array

連結：https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/

/**
 * Runtime: 108 ms, faster than 91.48% of JavaScript online submissions for Find All Numbers Disappeared in an Array.
* Memory Usage: 46.5 MB, less than 67.12% of JavaScript online submissions for Find All Numbers Disappeared in an Array.
 * @param {number[]} nums
 * @return {number[]}
 */
//1. 把 nums[i] - 1 作為 index，index 沒有負數，所以要取絕對值
//2. 遍歷第一次，把遍歷到的位置的值變成負數當作標記。如果已經有標記呈負數，那就保持原狀
//3. 遍歷第二次，把 nums[i] 仍然大於 0 的 傳 index + 1 到結果中
var findDisappearedNumbers = function(nums) {        
    let result = []
    
    for(let i=0; i<nums.length; i++){
        let index = Math.abs(nums[i])-1
        nums[index] = - Math.abs(nums[index])
    }
    
    for(let i=0; i<nums.length;i++){
        if(nums[i]>0){
            result.push(i+1)
        }
    }
    
    return result
};

/**

* Runtime: 108 ms, faster than 91.48% of JavaScript online submissions for Find All Numbers Disappeared in an Array.

* Memory Usage: 46.5 MB, less than 67.12% of JavaScript online submissions for Find All Numbers Disappeared in an Array.

* @param {number[]} nums

* @return {number[]}

//1. 把 nums[i] - 1 作為 index，index 沒有負數，所以要取絕對值

//2. 遍歷第一次，把遍歷到的位置的值變成負數當作標記。如果已經有標記呈負數，那就保持原狀

//3. 遍歷第二次，把 nums[i] 仍然大於 0 的傳 index + 1 到結果中

var findDisappearedNumbers = function(nums) {

let result = []

for(let i=0; i<nums.length; i++){

let index = Math.abs(nums[i])-1

nums[index] = - Math.abs(nums[index])

}

for(let i=0; i<nums.length;i++){

if(nums[i]>0){

result.push(i+1)

}

return result

};

451. Sort Characters By Frequency

連結：https://leetcode.com/problems/sort-characters-by-frequency/

// 1. 產生一個 map，記錄所有字母的出現次數
// 2-1. 用 Object.entries，依照出現次數排序，再用 String.repeat 方法輸出
// 2-2-1. 用 Object.keys，取得依照字母順序跑出的 key，搭配 String.repeat 方法輸出
// 2-2-2. 把 2-2-1 的方法，用 reduce 的方法寫出
var frequencySort = function(s) {   
let map = {}
    
for(let i=0; i<s.length;i++){
        map[s[i]] ? map[s[i]]++ : map[s[i]] = 1
    }

// 2-1.
// Runtime: 112 ms, faster than 32.67% of JavaScript online submissions for Sort Characters By Frequency.
// Memory Usage: 40.5 MB, less than 98.90% of JavaScript online submissions for Sort Characters By Frequency.

const sortedData = Object.entries(map).sort((a, b) => b[1] - a[1]);

let result = ''
for(const [key, value] of sortedData){
        result += key.repeat(value)
}
    
return result

// 2-2-1.
// Runtime: 96 ms, faster than 77.26% of JavaScript online submissions for Sort Characters By Frequency.
// Memory Usage: 40.8 MB, less than 97.13% of JavaScript online submissions for Sort Characters By Frequency.

const sortedOrder = Object.keys(map).sort((a, b) => map[b] - map[a]);
let result = ''
    
for(let i=0; i<sortedOrder.length;i++){
        result += sortedOrder[i].repeat(map[sortedOrder[i]])
}
    
return result

// 2-2-2.
// Runtime: 96 ms, faster than 77.26% of JavaScript online submissions for Sort Characters By Frequency.
// Memory Usage: 41.3 MB, less than 83.00% of JavaScript online submissions for Sort Characters By Frequency.

const sortedOrder = Object.keys(map).sort((a, b) => map[b] - map[a]);
return sortedOrder.reduce((acc,cur)=>acc+cur.repeat(map[cur]),'')
}

// 1. 產生一個 map，記錄所有字母的出現次數

// 2-1. 用 Object.entries，依照出現次數排序，再用 String.repeat 方法輸出

// 2-2-1. 用 Object.keys，取得依照字母順序跑出的 key，搭配 String.repeat 方法輸出

// 2-2-2. 把 2-2-1 的方法，用 reduce 的方法寫出

var frequencySort = function(s) {

let map = {}

for(let i=0; i<s.length;i++){

map[s[i]] ? map[s[i]]++ : map[s[i]] = 1

}

// 2-1.

// Runtime: 112 ms, faster than 32.67% of JavaScript online submissions for Sort Characters By Frequency.

// Memory Usage: 40.5 MB, less than 98.90% of JavaScript online submissions for Sort Characters By Frequency.

const sortedData = Object.entries(map).sort((a, b) => b[1] - a[1]);

let result = ''

for(const [key, value] of sortedData){

result += key.repeat(value)

}

return result

// 2-2-1.

// Runtime: 96 ms, faster than 77.26% of JavaScript online submissions for Sort Characters By Frequency.

// Memory Usage: 40.8 MB, less than 97.13% of JavaScript online submissions for Sort Characters By Frequency.

const sortedOrder = Object.keys(map).sort((a, b) => map[b] - map[a]);

let result = ''

for(let i=0; i<sortedOrder.length;i++){

result += sortedOrder[i].repeat(map[sortedOrder[i]])

}

return result

// 2-2-2.

// Runtime: 96 ms, faster than 77.26% of JavaScript online submissions for Sort Characters By Frequency.

// Memory Usage: 41.3 MB, less than 83.00% of JavaScript online submissions for Sort Characters By Frequency.

const sortedOrder = Object.keys(map).sort((a, b) => map[b] - map[a]);

return sortedOrder.reduce((acc,cur)=>acc+cur.repeat(map[cur]),'')

}

80. Remove Duplicates from Sorted Array II

連結：https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

/**
 * @param {number[]} nums
 * @return {number}
 * 1st：如果有重複，留下最開始出現的兩個
 * 先用一個計數器紀錄，若次數超過 2，就砍掉 nums[i]，並將 i--
 * 若 nums[i] 跟下一個不同，將 count 歸零
 * Runtime: 144 ms, faster than 5.36% of JavaScript online submissions for Remove Duplicates from Sorted Array II.
* Memory Usage: 40.4 MB, less than 49.09% of JavaScript online submissions for Remove Duplicates from Sorted Array II.
 */
var removeDuplicates = function(nums) {
    let count = 0 
    
    for(let i=0; i<nums.length; i++){
        count ++

        if(count>2){
            nums.splice(i,1)
            i--
        }
        
        if(nums[i] !== nums [i+1]){
            count = 0
        }
    }

    return nums.length
};

/**
 * @param {number[]} nums
 * @return {number}
 * 2nd：如果有重複，留下後面的，移除當下的
 * 遍歷整個迴圈，若 nums[index+2] 和 nums[index] 相同，那移除當下的。可能執行不只一次
 * 上一步完成後，index + 1
 * Runtime: 84 ms, faster than 90.23% of JavaScript online submissions for Remove Duplicates from Sorted Array II.
Memory Usage: 40.6 MB, less than 23.25% of JavaScript online submissions for Remove Duplicates from Sorted Array II.
 */
var removeDuplicates = function(nums) {
    let index = 0
    while(index<nums.length){
        while(nums[index+2]===nums[index]){
            nums.splice(index,1)
        }
        index++
    }
    return nums.length
};