一腳踏入軟體工程師寫 Code 的世界，不免俗地會碰上 Leetcode 的測驗，來測試你的溝通力、系統性地解決問題的能力和如何化抽象為具體。第二週的活動以 BigO 和資料結構的簡介，並簡單試個 String, Array, Object。
![[筆記] 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
課程對應章節：Week2 U17~U20
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
資料結構
將資料定義成一組抽象資料型態，並讓程式存取
1. 資料：一堆元素所組成的有限集合；結構：元素間的組成關係
2. 資料先存放於記憶體，有需要才拿出來使用
更有效的存取方法，讓程式更有效的運用記憶體和效率
ADT ( Abstract Data Type )
資料結構本身和實作是分開的。如果該程式語言沒有提供某種資料結構，那你有可能會需要自己定義。
Array, String, Object
1. String 是儲存變數，immutable，僅占一格記憶體位置
2. Array 為 mutable，儲存記憶體位置，若其內有 N 個值，那會占用 N 格記憶體空間
3. Object 沒有順序，所以需要 key
4. 在 JavaScript 中，Object 近似於 HashMap
5. 如何複製一個物件 / 陣列？
如果是陣列的話，可以用 Array.slice，或是 [ … ] 運算子
如果是物件的話，Object.assign 可作到第一層淺拷貝，如果是深拷貝的話，那轉成字串再回來是種方式，但會取決於你的 key-value 都是可以轉成 JSON 格式
如何變數交換
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// basic let a = 1, b = 2, tmp; tmp = a; a = b; b = tmp; // for numbers var a = 1, b = 2; a = a + b; // a = 3, b = 2 b = a - b; // a = 3, b = 1 a = a - b; // a = 2, b = 1 // JavaScript ES6 寫法 let a = 1, b = 2; [a, b] = [b, a] |
LeetCode 題目
414. Third Maximum Number
連結：https://leetcode.com/problems/third-maximum-number/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Runtime: 84 ms, faster than 55.08% of JavaScript online submissions for Third Maximum Number. // Memory Usage: 38.8 MB, less than 87.10% of JavaScript online submissions for Third Maximum Number. var thirdMax = function(nums) { if(nums.length === 1) return nums[0] // Array 只有一個值，直接回傳 if(nums.length === 2) return Math.max(...nums) // Array 有兩個值，直接傳回最大的 let count = 0 // 計數用 let result = Infinity // 設一個值為 Infinity nums = nums.sort((a,b)=>a<b? 1 : -1) // 先將陣列由大到小排序 // 由第一個開始遍歷，若遍歷到的值比 result 小，就將 result 換掉，並將 count + 1 for(let i=0; i<nums.length; i++){ if(nums[i]<result){ result = nums[i] count += 1 } if(count === 3) return result // 當數到 3 時，表示第三大的值出現了，所以回傳 } return nums[0] // 若全部遍歷完, count 一直都沒有到 3 ，表示陣列中其實只有兩種數字，那就回傳第一個就好 }; |
442. Find All Duplicates in an Array
連結：https://leetcode.com/problems/find-all-duplicates-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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
// 第一思考，將 array 用 filter 和 index 作篩選，可以篩掉重複的，那就將其邏輯反過來就好。 /** * @param {number[]} nums * @return {number[]} */ // Runtime: 4380 ms, faster than 5.13% of JavaScript online submissions for Find All Duplicates in an Array. // Memory Usage: 46.7 MB, less than 60.90% of JavaScript online submissions for Find All Duplicates in an Array. var findDuplicates = function(nums) { return nums.filter((num,index)=>nums.indexOf(num)!==index) }; /** * @param {number[]} nums * @return {number[]} */ // Runtime: 112 ms, faster than 81.09% of JavaScript online submissions for Find All Duplicates in an Array. // Memory Usage: 46.7 MB, less than 60.90% of JavaScript online submissions for Find All Duplicates in an Array. // 優化：將 array 內的值當作 index，給予 nums[i] 標註為負數。由於同樣的數字，會標註同樣位置的 nums[i]。換言之，若你發現 nums[i] 為負數，那就表示這個數字重複了，將其推入 result 的陣列中。 var findDuplicates = function(nums) { let result = [] for(let i=0; i<nums.length; i++){ let index = Math.abs(nums[i])-1 if( nums[index] < 0 ){ result.push(Math.abs(nums[i])) } nums[index] *= -1 } return result }; |
268. Missing Number
連結：https://leetcode.com/problems/missing-number/
|
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 |
//第一想法： 將數字由小到大排序後，再從頭開始遍歷。若 i !== nums[i] ，那就回傳 i // Runtime: 88 ms, faster than 65.17% of JavaScript online submissions for Missing Number. // Memory Usage: 41.1 MB, less than 47.39% of JavaScript online submissions for Missing Number. /** * @param {number[]} nums * @return {number} */ var missingNumber = function(nums) { nums.sort( (a,b) => a-b> 0 ? 1 : -1 ); for(let i=0; i<=nums.length; i++) { if(i !== nums[i]) { return i } } }; //第二想法： 從 0 加到 N 的總和 減去 array 內的所有數字總和，就是 missing number // Runtime: 88 ms, faster than 65.17% of JavaScript online submissions for Missing Number. // Memory Usage: 40.9 MB, less than 64.02% of JavaScript online submissions for Missing Number. var missingNumber = function(nums) { let sum = 0 let sumInarray = 0 for(let i=0; i<=nums.length; i++){ sum += i } for(let i=0; i<nums.length; i++){ sumInarray += nums[i] } return sum - sumInarray }; |
36. Valid Sudoku
連結：https://leetcode.com/problems/valid-sudoku/
|
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 |
// Runtime: 96 ms, faster than 83.94% of JavaScript online submissions for Valid Sudoku. // Memory Usage: 41.3 MB, less than 81.68% of JavaScript online submissions for Valid Sudoku. /** * @param {character[][]} board * @return {boolean} */ var isValidSudoku = function(board) { for(let i=0; i<9; i++){ let row = [] let column = [] let box = [] for(let j=0; j<9;j++){ let rowValue = board[i][j] // 橫列值 let columnValue = board[j][i] // 直行值 let boxValue = board[3*Math.floor(i/3)+Math.floor(j/3)][3*(i%3)+j%3] // box 區塊值 // 如果有 '.' 跳過，若沒有則進入判斷 // 當讀取到的值不存在，那就加入暫存，如果已經存在，就傳 falsr if(rowValue !== '.'){ if(row.indexOf(rowValue) === -1){ row.push(rowValue) }else{ return false } } if(columnValue !== '.'){ if(column.indexOf(columnValue) === -1){ column.push(columnValue) }else{ return false } } if(boxValue !== '.'){ if(box.indexOf(boxValue) === -1){ box.push(boxValue) }else{ return false } } } } // 完成上面全部檢驗，那就傳 true return true }; |
316. Remove Duplicate Letters
連結：https://leetcode.com/problems/remove-duplicate-letters/
|
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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
/** * @param {string} s * @return {string} * 第一次嘗試 * Runtime: 100 ms, faster than 36.43% of JavaScript online submissions for Remove Duplicate Letters. * Memory Usage: 42.9 MB, less than 7.75% of JavaScript online submissions for Remove Duplicate Letters. */ var removeDuplicateLetters = function(s) { // I. 記錄下所有字母出現的次數，並宣告一個 result 陣列 let alphabetCount = {} let result = [] for(let i of s){ alphabetCount[i] = (alphabetCount[i] + 1) || 1 } for(let i=0; i<s.length;i++){ // II. 開始遍歷，每遍歷一個，出現次數就 - 1 alphabetCount[s[i]] -= 1 // III. result內有出現過，就直接進到下一輪 if(result.includes(s[i])){ continue } // IV. 用 Stack 的概念，取得 top 的值 let top = result.slice(-1)[0] // V. 當 top 有值、該字母(top) 後面還會出現、比新加入的 s[i] 的字母順序大、result 不為空，那就可以將該子母給捨棄掉，這動作可能不只執行一次 while(top && alphabetCount[top] && top>s[i] && result.length){ result.pop() top = result.slice(-1)[0] } // VI. 經過上面判斷過後，將s[i]加入 result result.push(s[i]) } // 回傳 result.join("") 拼接而成的字串即可 return result.join("") }; 優化：用 result.includes 來找尋有無重複，最差的情況下會從頭到尾遍歷。所以改用 map 來處理。 /** * @param {string} s * @return {string} * Runtime: 92 ms, faster than 84.50% of JavaScript online submissions for Remove Duplicate Letters. * Memory Usage: 41.8 MB, less than 22.48% of JavaScript online submissions for Remove Duplicate Letters. */ var removeDuplicateLetters = function(s) { let alphabetCount = {} for(let i of s){ alphabetCount[i] = (alphabetCount[i] + 1) || 1 } let result = [] const map = {} for(let i=0; i<s.length;i++){ alphabetCount[s[i]] -= 1 if(s[i] in map){ continue } let top = result.slice(-1)[0] while(top && alphabetCount[top] && top>s[i] && result.length){ delete map[top] result.pop() top = result.slice(-1)[0] } result.push(s[i]) map[s[i]] = 1 } return result.join("") }; |
