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

章節連結

課程相關資訊
內容

什麼是演算法
排序演算法
搜尋演算法

LeetCode 題目

324. Wiggle Sort II
853. Car Fleet
1424. Diagonal Traverse II

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

課程對應章節：Week6 U41~U43

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

內容

什麼是演算法

有限時間內，以有限個指令完成特定功能的一種按部就班解決問題的方法。

Input：外界至少提供 ≥ 0 個輸入
Output：Algorithm 至少產生 ≥ 1 個輸出結果
Definiteness (明確)：每個指令必須是 Clear and Unambiguous
Finiteness (有限性)：Algorithm 在執行有限個步驟後，必定終止
Effectiveness (有效性)：用紙跟筆即可追蹤 Algorithm 執行的過程及結果

演算法是抽象的，可用程式語言的特性、邏輯控管…等來實現。

排序演算法

選擇排序法(Selection Sort)

1. 常會使用到雙重迴圈
2. 最後會使用交換的方式，來讓陣列得以排序
3. 一一掃瞄未排序資料，找出最大值(or最小)

插入排序法(Insertion Sort)

1. 依序由未排序的資料中選一筆資料
2. 運用 while loop，讓選取的資料得以插入正確位置，且原本在該位置的資料要往右移 ( 由小到大的情況下 )

氣泡排序法(Bubble Sort)

1. 對未排序資料兩兩比對掃瞄
2. 排序後，兩兩會交換位置，會是以最右邊開始陸續出現排序結果

快速排序法(Quick Sort)

1. 將比基準值(Pivot)小的數值移到左邊，大者反之
2. 對基準值的左、右子數列遞迴相同動作

合併排序(Merge Sort)

待整理

堆積排序(Heap Sort)

待整理

以上的圖形化示意可點右邊網址前往觀看：https://visualgo.net/en/sorting

搜尋演算法

線性搜尋法 (Linear Search)

循序搜尋，按照順序一個個找

二元搜尋法 (Binary Search)

必須要先行排序，每次搜尋會留下一半的查找目標

雜湊搜尋法 (Hashing Search)

資料按照某特定法則轉換為資料儲存位置，應用時是以資料鍵值(key value)轉換來查找

LeetCode 題目

324. Wiggle Sort II

連結：https://leetcode.com/problems/wiggle-sort-ii/

// 題目要求為 一小一大 的數字來間隔排序
// 所以，將 array 中的數字先行由小到大排序後，從中間分成兩半
// 再填入原本 nums 的陣列中即可

var wiggleSort = function(nums) {
    nums.sort((a,b)=> a-b > 0 ? 1 : -1 )
    const middlePoint = Math.ceil(nums.length / 2)
    const [smallNums, bigNums ] = [ nums.slice(0, middlePoint), nums.slice(middlePoint, nums.length)]
    
    for(let i=0; i<nums.length; i++){
        if(i%2===0){
            nums[i] = smallNums.pop()
        }else{
            nums[i] = bigNums.pop()
        }
    }
};

// 題目要求為一小一大的數字來間隔排序

// 所以，將 array 中的數字先行由小到大排序後，從中間分成兩半

// 再填入原本 nums 的陣列中即可

var wiggleSort = function(nums) {

nums.sort((a,b)=> a-b > 0 ? 1 : -1 )

const middlePoint = Math.ceil(nums.length / 2)

const [smallNums, bigNums ] = [ nums.slice(0, middlePoint), nums.slice(middlePoint, nums.length)]

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

if(i%2===0){

nums[i] = smallNums.pop()

}else{

nums[i] = bigNums.pop()

}

};

853. Car Fleet

連結：https://leetcode.com/problems/car-fleet/

// 做出一個 cars 的陣列，儲存其所在位置和還要花多少時間才會抵達終點的 map
// 將 cars 以 position 位置由大到小排序
// 遍歷 cars 陣列，並用一個 fleet 的陣列來儲存用來比較的基準時間
// 如果 fleets 用來比較的基準時間比 car 的 remainTime 還少，代表會被追上，視同一個 fleet
// 最後返回 fleets 的長度即可

var carFleet = function(target, position, speed) {
    const cars = []
    const fleets = []
    
    for(let i=0; i<position.length;i++){
        cars[i] = {position: position[i], remainTime: (target-position[i])/speed[i]} 
    }
    
    cars.sort((a,b)=> b.position - a.position > 0 ? 1 : -1)
        
    for(let i=0; i< cars.length; i++){
        if(fleets.length === 0){
            fleets.push(cars[i].remainTime)
            continue
        }
        if(cars[i].remainTime > fleets[fleets.length - 1]){
            fleets.push(cars[i].remainTime)
        }
    }
    
    return fleets.length
};

// 做出一個 cars 的陣列，儲存其所在位置和還要花多少時間才會抵達終點的 map

// 將 cars 以 position 位置由大到小排序

// 遍歷 cars 陣列，並用一個 fleet 的陣列來儲存用來比較的基準時間

// 如果 fleets 用來比較的基準時間比 car 的 remainTime 還少，代表會被追上，視同一個 fleet

// 最後返回 fleets 的長度即可

var carFleet = function(target, position, speed) {

const cars = []

const fleets = []

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

cars[i] = {position: position[i], remainTime: (target-position[i])/speed[i]}

}

cars.sort((a,b)=> b.position - a.position > 0 ? 1 : -1)

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

if(fleets.length === 0){

fleets.push(cars[i].remainTime)

continue

}

if(cars[i].remainTime > fleets[fleets.length - 1]){

fleets.push(cars[i].remainTime)

}

return fleets.length

};

1424. Diagonal Traverse II

連結：https://leetcode.com/problems/diagonal-traverse-ii

// 遍歷 nums 和 nums[i]，分別在 result 中塞入指定 result[index] 的陣列中
// 如果 result[index] 一開始不存在，那先初始化建立一個
// 這樣所形成的對角線數字陣列，是由右上到左下的形式，所以要翻轉過來

var findDiagonalOrder = function(nums) {
    let result = []
    let level = -1
    
    for(let i=0; i<nums.length; i++){
        level++
        for(let j=0; j<nums[i].length; j++){      
            result[level + j] = result[level + j] || []
            result[level + j].push(nums[i][j])
        }
    }
    
    result = result.reduce((acc,items)=>{
       acc.push(...items.reverse())
       return acc
    },[])
    
    return result
};