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

章節連結

課程相關資訊
內容

資料結構
演算法
解題時的心態
演算法和程式的不同
解題的流程
小心不要常看解答

LeetCode 題目

231. Power of Two
66. Plus One
1. Two Sum
167. Two Sum II – Input array is sorted

一腳踏入軟體工程師寫 Code 的世界，不免俗地會碰上 Leetcode 的測驗，來測試你的溝通力、系統性地解決問題的能力和如何化抽象為具體。第一週的活動算是暖身階段，筆記下獲得到的重點，以及小試身手解個幾題。

課程對應章節：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/

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

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

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

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

// 方法 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    
      }
}

// 方法 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/

// 方法 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]