一腳踏入軟體工程師寫 Code 的世界，不免俗地會碰上 Leetcode 的測驗，來測試你的溝通力、系統性地解決問題的能力和如何化抽象為具體。第一週的活動算是暖身階段，筆記下獲得到的重點，以及小試身手解個幾題。
![[筆記] 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
課程對應章節：Week1 U1~U16
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
資料結構
1. String, Array, Object, Map, Set, Linked-List, Stacks, Queues, Tree
2. 解決空間複雜度、更有效率的存放到電腦中，以節省空間
演算法
1. Search, Sort, Recursion, Greedy, Divide and Conquer, Dynamic Programming
2. 藉由有效率的流程控制，讓執行速度得以提升
解題時的心態
觀察規律、拆解題目，使大問題變成小問題
演算法和程式的不同
演算法：特定時間下，完成特定的步驟並輸出結果
程式：會持續運行
解題的流程
把一道題目刷到極致，是因應 LeetCode 早已超過千題的時代，所應具備的心態
第一回合：思考，試著用紙筆 → 實際撰寫 (約 0.5 ~ 1 hour / per ) → 試著重構看看 (約 0.5 ~ 1 hour / per )
第二回合：隔幾天後再回來看看，也可以去查閱他人的寫法
小心不要常看解答
你會忽略掉自己思考的機會，你需要從爛的寫法和優質的寫法做比較
LeetCode 題目
231. Power of Two
連結：https://leetcode.com/problems/power-of-two/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
/* * Runtime: 88 ms, faster than 92.14% of JavaScript online submissions for Power of Two. * Memory Usage: 39.9 MB, less than 67.07% of JavaScript online submissions for Power of Two. */ /** * @param {number} n * @return {boolean} */ var isPowerOfTwo = function(n) { if(n<=0) return false if(n === 1) return true if(n%2===1) return false while(n>=2 && n%2 === 0){ n = n / 2 if(n===1) return true if(!Number.isInteger(n)) return false } return false }; |
66. Plus One
連結：https://leetcode.com/problems/plus-one/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
/* * Runtime: 80 ms, faster than 56.59% of JavaScript online submissions for Plus One. * Memory Usage: 38.7 MB, less than 27.46% of JavaScript online submissions for Plus One. */ /** * @param {number[]} digits * @return {number[]} */ var plusOne = function(digits) { let rawNumber = BigInt(digits.join("")) + 1n let plusOneArray = rawNumber.toString().split("").map(d=>Number(d)) let diffLength = digits.length - plusOneArray.length if(diffLength !== 0){ return [ ...Array.from({ length: diffLength }, () => 0 ), ... plusOneArray] }else{ return plusOneArray } }; |
1. Two Sum
連結：https://leetcode.com/problems/two-sum/
|
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 |
// 方法 I // 雙重迴圈，形同兩根指針，一個個遍歷後相加 // Runtime: 76 ms, faster than 90.96% of JavaScript online submissions for Two Sum. // Memory Usage: 38.7 MB, less than 84.01% of JavaScript online submissions for Two Sum. for(let i=0; i<nums.length-1;i++){ for(let j=i+1; j<nums.length;j++){ if(nums[i]+nums[j] === target) return [i,j] } } // 方法 II // 運用 Map // Runtime: 80 ms, faster than 79.38% of JavaScript online submissions for Two Sum. // Memory Usage: 38.6 MB, less than 84.01% of JavaScript online submissions for Two Sum. let map = {} for(let i=0; i<nums.length; i++){ // 將 target 相減後的值當作搜尋的 key let j = target - nums[i] // 如果 map 中不存在的話，那就在 map 中留下 nums[i] 為 key // value 為當下的 index if(map[j] === undefined){ map[nums[i]] = i }else{ return [map[j],i] // 如果有符合的，就吐回當下的 i 和保存在 map[j] 的 value } } |
167. Two Sum II – Input array is sorted
連結：https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
|
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 |
// 方法 I. 用 map 的方法，以 target-numbers[i] 當作搜尋用的 key // 當 map 中沒有對應值，那就留下 numbers[i] 為 key ，其 value 為 i + 1 // 因為是照順序排列的 array ，所以當找到值時，就回傳先前存在 [ map 中的值, i+1 ] // Runtime: 68 ms, faster than 98.91% of JavaScript online submissions for Two Sum II - Input array is sorted. // Memory Usage: 39 MB, less than 50.15% of JavaScript online submissions for Two Sum II - Input array is sorted. let map = {} for(let i=0; i<numbers.length; i++){ let j = target-numbers[i] if(map[j] === undefined){ map[numbers[i]] = i + 1 }else{ return [map[j],i+1] } } // 方法 II. 用 two pointer 的方法 // 若左右相加不等於 target，相加的和若太大，那就右邊指針往左移；若太小，就左邊指針右移 // 最後回傳 [left + 1, right + 1] // Runtime: 72 ms, faster than 96.60% of JavaScript online submissions for Two Sum II - Input array is sorted. // Memory Usage: 38.8 MB, less than 66.50% of JavaScript online submissions for Two Sum II - Input array is sorted. let left = 0 let right = numbers.length-1 while(numbers[left]+numbers[right] !== target){ if(numbers[left]+numbers[right]<target){ left += 1 }else{ right -= 1 } } return [left+1,right+1] |
