一腳踏入軟體工程師寫 Code 的世界，不免俗地會碰上 Leetcode 的測驗，來測試你的溝通力、系統性地解決問題的能力和如何化抽象為具體。第三週的活動以 Map 和 Set 為主。
![[筆記] AlphaCamp 不只是刷題的 Leetcode 訓練營 – 3](https://smlpoints.com/wp-content/uploads/notes-alphacamp-leetcode-training-camp-1.jpg "[筆記] AlphaCamp 不只是刷題的 Leetcode 訓練營 – 3")
課程相關資訊
[連結]：https://www.accupass.com/event/2010251353233453323900
課程對應章節：Week3 U22~U24
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
Map
在高階的程式語言(如：JavaScript, Python, Ruby…等)中，會提供 Map 和 Set 的方法。若以 JavaScript 中的 new Map() 為例子：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// 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/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
/** * 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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
// 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/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
/** * @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 }; |
