---
# System prepended metadata

title: Algorithm & Data Structure in Javascript
tags: [study]

---

# Algorithm & Data Structure in Javascript

[演算法解說](http://alrightchiu.github.io/SecondRound/mu-lu-yan-suan-fa-yu-zi-liao-jie-gou.html)

[傑哥演算法筆記](https://medium.com/%E7%AA%AE%E6%8F%9A%E5%82%91%E7%9A%84%E6%99%AE%E9%80%9A%E5%B8%B8%E8%AD%98/algorithm/home)

<font color="red">**前端必考**</font>
- bubble sort
- binary tree

一般會用到quick sort和insertion sort
merge sort在資料量小才會用

![](https://i.imgur.com/bDIiTRT.png =600x)

## Real Example in Life
- Google Map
- Youtube
- FB/IG
- Excel

## Comparing Algorithm
分為時間和空間比較, 進行比較時不可以拿執行環境(runtime)做比較, 因為不同電腦配備不同執行後的結果也會不同
> code's runtime is not realistic
> different computer power machine gives different run time

## Complexity 複雜度
主要指時間複雜度
越多運算子operator(><= etc..), 就表示運用的時間就會越多, 有幾個就會乘上幾次, complexity正向增加
- `+` addition
- `-` subtraction
- `*` multiplication
- `/` division

### example
```=javascript
function exmaple(n) {
    for (i< 3 *n){

    }
    for (i<n) {
      for(j<n) {

      }
    }
    console.log('h');
    console.log('h');
    console.log('h');
    console.log('h');
}

// 執行
example(2)
```

從上述例子看總共會印幾次h?
第一個外圈是`3*2`, 第二個外圈和內圈是`2*2`, 最後4次h
所以是`(3*2)+(2*2)+4 =14`

### 用公式解說複雜度
`f(n)=n^2 + 3n + 4`
- `n` 表示input size
- `f(n)` 表示 complexity
解一元二次方程式, 帶入數字來看, 會得到
```
n=2, f(n)=14
n=3, f(n)=22
n=4, f(n)=32
n=5, f(n)=44
n=9, f(n)=112
```
從14到112是10倍的成長, 平方越大時間複雜度越高, 花費時間也會越久

## Big O Notation
### 怎麼取出Big O
- constant 不看
- small terms 不看
- Log 底數不看

### example
- f(n)= 3n, Big O是 `O(n)`
- f(n)= 3n^2+6n, Big O是 `O(n^2)`
- f(n)= log2n, Big O是 `O(Log n)`
- f(n)= 2n, Big O是 `O(n)`
- f(n)= 13n^3+6n+7, Big O是 `O(Log n)`
- f(n)= 4log2n, Big O是 `O(Log n)`
- f(n)= 5, Big O是 ==O(5), 但要算換成1,所以是O(1)==

### 好到壞
平方的時間複雜度越高, 通常會想辦法把`5`和`6`,優化成`3`和`4`
1. O(1)
2. O(Logn)
3. O(n)
4. O(nLogn)
5. O(n^2)
6. O(n^3)

### Array and Object
- Object, Array是Hash Table的資料結構
- Hash Table的優點是佔用記憶體小
- 物件和陣列皆有`insertion`,`removal`,`searching`,`accessing`對應的Big O
- 底線沒有任何意義,是為了分開obj,arr
``` mermaid
graph TD;
Object-->_insertion;
Object-->_removal;
Object-->_searching;
Object-->_accessing;
```
- _insertion: O(1)
- _removal:   O(1)
- _searching: O(n)
- _accessing: O(1)

``` mermaid
graph TD;
Array-->insertion;
insertion-->push;
insertion-->unshift;
Array-->removal;
removal-->pop;
removal-->shift;
Array-->searching;
Array-->accessing;
```
- insertion-push: O(1) 新增元素至末端
- insertion-unshift: O(n)  新增元素到開頭
- removal-pop: O(1) 移除末端元素
- removal-shift: O(n) 移除開頭元素
- searching: O(n)
- accessing: O(1)

Queue: shift, unshift 先進先出 FIFO
Stack: pop, push 後進先出 LIFO

![](https://i.imgur.com/hjcXAMd.png =600x)

![](https://i.imgur.com/yexDrws.png =600x)

## Algorithm Design
### Linear Search
漸進式搜尋, sequentially check each element

![](https://i.imgur.com/Lpj8cPu.jpg =500x)

- Pseudocode
```
for i form O+0
array.length -1:
  if(array[i] == n):
   return 1
return -1
```
- Coding Practice
```=javascript
function linearSearch(arr, n) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === n) {
      console.log("Found number " + n + " at index " + i);
      return i;
    }
  }
  console.log("Cannot find " + n);
  return -1;
}

linearSearch(numbers, 24);
```

- Overview
  - worst: O(n), 要找的i在arr的最後一項
  - best: O(1), 要找的在arr的第一項
  - average: O(n/2)

### Binary Search
二元搜尋, 切一半找
- 只用在已排序的陣列 ==sorted array==
- more efficient

![](https://i.imgur.com/CjD46FM.png =500x)

- Coding Practice
```=javascript
function binarySearch(arr, n) {
  let min = 0;
  let max = arr.length - 1;
  let step = 0;

  while (min <= max) {
    step++;
    // floor取整數
    let middle = Math.floor((max + min) / 2);
    if (n > arr[middle]) {
      min = middle + 1;
    } else if (n < arr[middle]) {
      max = middle - 1;
    } else if (n === arr[middle]) {
      console.log("Found number " + n + " at position " + middle);
      console.log("Found it after " + step + " steps.");
      return middle;
    }
  }

  console.log("Cannot find number " + n);
  return -1;
}

binarySearch(numbers, 213); // 6 - 7
```
以8個元素為例,除2再除2,就會是
8 > 4 > 2 > 1
at lest 3 steps
換成Log就是 Log2的8 = 3, 也就是Log2的n
- Overview
  - worst: O(Logn)
  - best: O(1)
  - average: O(Logn)

### Intersection Problem 交集
找出兩個陣列中重複的元素

![](https://i.imgur.com/H56vbMu.png =500x)

- O(n^2)
- Coding Practice
```=javascript
function intersection(arr1, arr2) {
  let result = [];
  for (let i = 0; i < arr1.length; i++) {
    for( let j = 0; j < arr2.length; j++) {
      console.log(arr1[i] , arr2[j]);
      if(arr1[i] == arr2[j]) {
        result.push(arr1[i]);
      }
    }
  }
  console.log(result);
  return result;
}

intersection([1,2,3,7,9], [5,16,10,3,1]);
```

### Counter
可以改善Intersection Problem
讓交集的intersction==O(n^2)== 變成 ==O(n)==

![](https://i.imgur.com/9qdhjxu.png =500x)

- O(n)
- Coding Practice
```=javascript
intersection([1,2,3,7,9], [5,16,10,3,1]);

function intersction( arr1: number[], arr2: number[]) {
  let res: number[] = [];
  let arr3: any[] = arr1.concat(arr2);
  let counter: any = {};

  for( let i: number = 0; i < arr3.length; i++ ) {
    if(!counter[arr3[i]]){
      counter[arr3[i]] = 1;
    } else {
      counter[arr3[i]] ++;
    }
  }
  for ( let property in counter) {
    if(counter[property] >= 2) {
      res.push(+property);
    }
  }
  console.log(`res ${res}`);
  return res;
}
```

### Frequency Problem
- for*3 -> O(3n) -> O(n)
- Coding Practice
```=typescript
function sameFreq( st1: string, st2: string): boolean {
  let ar1: string[] = st1.split('');
  let ar2: string[] = st2.split('');

  if(ar1.length !== ar2.length) return false;

  let counter1: any = {};
  let counter2: any = {};

  for( let i: number = 0; i < ar1.length; i++) {
    if(!counter1[ar1[i]]) {
      counter1[ar1[i]] = 1;
    } else {
      counter1[ar1[i]] ++;
    }
  }

  for( let i: number = 0; i < ar2.length; i++) {
    if(!counter2[ar2[i]]) {
      counter2[ar2[i]] = 1;
    } else {
      counter2[ar2[i]] ++;
    }
  }

  console.log(counter1, counter2);

  for(let property in counter1) {
    console.log(`c1: ${counter1[property]}`);
    console.log(`c2: ${counter2[property]}`);
    if(!counter2[property]) return false;
    if(counter2[property] !== counter1[property]) return false;
  }
  return true;
  
}
sameFreq("aabc", "abbc");
```

### Average Pair
- 只用在已排序的陣列 ==sorted array==

![](https://i.imgur.com/JmJ2ePi.png =500x)

- O(n^2)
- 找出成對的數字
- Coding Practice
```=javascript
averagePair([-11, 0, 1, 2, 3, 9, 14, 17, 21], 1.5);

function averagePair(arr, avg) {
  let result = [];
  // 事情做完才+1
  // body做完, j才會++
  // j的for做完, i才會++
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if ((arr[i] + arr[j]) / 2 == avg) {
        result.push([arr[i], arr[j]]);
      }
    }
  }

  // O(n^2) => O(n)
  console.log(result);
  return result;
}
```

### Pointer
可以解決
1. AvagePair
2. Palindrome
3. Subsequence Problem
4. Slide Window

![](https://i.imgur.com/fXStHAZ.png =500x)

- 讓==O(n^2)== 變成 ==O(n)==
- O(n)
- Coding Practice
```=javascript
averagePair([-11, 0, 1, 2, 3, 9, 14, 17, 21], 1.5);

function averagePair( arr: number[], avg: number) {
  let left: number = 0;
  let right: number = arr.length -1;
  let res: number[] = [];

  while( right > left) {
    let tempAvg = (arr[right] + arr[left])/2;
    if( tempAvg > avg) {
      right --;
    } else if ( tempAvg < avg) {
      left ++;
    } else if ( tempAvg === avg) {
      res.push(arr[right], arr[left]);
      right --;
      left ++;
    }
  }
  console.log(res);
  return res;
}
```

### Palindrome
從前或後讀是一樣的, i.e. `tacocat`
可以用pointer解

![](https://i.imgur.com/CdYCCXl.png =500x)

- O(Log n)
- Coding Practice
```=javascript
palindrome('tacocat');
// palindrome('amanaplanacanalpanama');
// palindrome('asdfsafeaw');

function palindrome(str: string): boolean | void{
  let left: number = 0;
  let right: number = str.length -1;

  while( right >= left) {
    if(str[left] === str[right]) {
      left ++;
      right --;
    } else {
      return false;
    }
    console.log(true);
    return true;
  }
}
```

### Subsequence Problem
不能改變原本的相對位置, [`book`, `brooklyn`]
可以用pointer解

![](https://i.imgur.com/jVBDDjB.png =500x)

- O(Log n)
- Coding Practice
```=javascript
// isSubsequence("hello", "hello Dear"); // true
// isSubsequence("book", "brooklyn"); // true
// isSubsequence("abc", "bac"); // false (order matters)
isSubsequence("", "abc"); // true

function isSubsequence(str1, str2) {
  if (str1.length == 0) {
    console.log(true);
    return true;
  }

  let pointer1 = 0;
  let pointer2 = 0;

  while (pointer2 < str2.length) {
    if (str1[pointer1] == str2[pointer2]) {
      pointer1++;
    }
    if (pointer1 >= str1.length) {
      console.log(true);
      return true;
    }
    pointer2++;
  }

  console.log(false);
  return false;
}
```

### Slide Window
![](https://i.imgur.com/jwTykzM.jpg =400x)

Max Sum
Min Sum

![](https://i.imgur.com/JPaFRu5.jpg =400x)

![](https://i.imgur.com/eqVKO9V.jpg =400x)

- O(n^2)
- Coding Practice
```=javascript
maxSum([2, 7, 3, 0, 6, 1, -5, -12, -11], 2); // 12
minSum([2, 7, 3, 0, 6, 1, -5, -12, -11], 3); // -28

function maxSum(arr, size) {
  let max_value = -Infinity;

  if (size > arr.length) {
    return null;
  }

  for (let i = 0; i <= arr.length - size; i++) {
    let attempt = 0;
    for (let j = i; j < i + size; j++) {
      attempt += arr[j];
    }
    if (attempt > max_value) {
      max_value = attempt;
    }
  }

  console.log(max_value);
  return max_value;
}

function minSum(arr, size) {
  let min_value = Infinity;

  if (size > arr.length) {
    return null;
  }

  for (let i = 0; i <= arr.length - size; i++) {
    let attempt = 0;
    for (let j = i; j < i + size; j++) {
      attempt += arr[j];
    }
    if (attempt < min_value) {
      min_value = attempt;
    }
  }

  console.log(min_value);
  return min_value;
}
```

### Improve Maxsum
- O(2n) -> O(n)
- Coding Practice
```=javascript
maxSum([2, 7, 3, 7, 25, 0, 6, 1, -5, 12, -11], 3); // 12

function maxSum(arr, size) {
  if (size > arr.length) {
    return null;
  }

  let maxValue = 0;
  for (let i = 0; i < size; i++) {
    maxValue += arr[i];
  }

  let temValue = maxValue;
  for (let j = size; j < arr.length; j++) {
    temValue = temValue + arr[j] - arr[j - size];
    if (temValue > maxValue) {
      maxValue = temValue;
    }
  }

  console.log(maxValue);
  return maxValue;
}
```

### Min Sub Array
![](https://i.imgur.com/I7Tvb2q.jpg =400x)

- O(Log n)
- Coding Practice
```=javascript
function minSubArray(arr, sum) {
  let start = 0;
  let end = 0;
  let total = 0;
  let minLength = Infinity;

  while (start < arr.length) {
    if (total < sum && end < arr.length) {
      total += arr[end];
      end++;
    } else if (total >= sum) {
      let currentLength = end - start;
      if (minLength > currentLength) {
        minLength = currentLength;
      }
      total -= arr[start];
      start++;
    } else if (end >= arr.length) {
      break;
    }
  }

  if (minLength === Infinity) {
    console.log("Cannot find subarray that can sum up to the given number");
    return 0;
  } else {
    console.log(minLength);
    return minLength;
  }
}

minSubArray([8, 1, 6, 15, 3, 16, 5, 7, 14, 30, 12], 70);
```

### Unique Letter Substring
- O(Log n)
- Coding Practice
```=javascript
function uniqueLetterString(str) {
  let start = 0;
  let end = 0;
  let counter = {};
  let maxLength = -Infinity;

  while (end < str.length) {
    console.log(counter);
    if (counter[str[end]]) {
      counter[str[start]]--;
      start++;
    } else {
      counter[str[end]] = 1;
      end++;
      if (end - start > maxLength) {
        maxLength = end - start;
      }
    }
  }

  if (maxLength == -Infinity) {
    console.log("Cannot find unique letters substring.");
    return null;
  }

  console.log(maxLength);
  return maxLength;
}

uniqueLetterString(""); // 6
```

### Largest Product
- O(NLog n)
- Coding Practice
```=javascript
let thousandDigits = 
[7, 3, 1, 6, 7, 1, 7, 6, 5, 3, 1, 3, 3, 0, 6, 2, 4, 9, 1, 9, 2, 2, 5, 1, 1,
 9, 6, 7, 4, 4, 2, 6, 5, 7, 4, 7, 4, 2, 3, 5, 2, 4, 9, 1, 9, 2, 2, 5, 1, 1];
 
function largestProduct(n) {
  let currentProduct;
  let maxProduct = -Infinity;
  let left = 0;
  let right = n - 1;

  while (right < thousandDigits.length) {
    currentProduct = 1;
    for (let i = left; i <= right; i++) {
      currentProduct *= thousandDigits[i];
    }
    if (currentProduct > maxProduct) {
      maxProduct = currentProduct;
    }
    right++;
    left++;
  }

  console.log(maxProduct);
  return maxProduct;
}

largestProduct(13);
```

### Recursion 遞迴
用在處理stack資料結構
- Ox
- Coding Practice
```=javascript
```

### Fibonacci Sequence
- O(n)
- Coding Practice
```=javascript
function fs(n) {
  if (n == 0) {
    return 0;
  } else if (n == 1) {
    return 1;
  } else {
    return fs(n - 1) + fs(n - 2);
  }
}

for (let i = 0; i < 15; i++) {
  console.log(fs(i));
}
```

### Array of Arrays
- O(n)
- Coding Practice
```=javascript
let arrs = [[[["a", [["b", ["c"]], ["d"]]], [["e"]], [[["f", "g", "h"]]]]]];

function collector(arr1) {
  let result = [];
  helper(arr1);
  return result;

  function helper(arr2) {
    for (let i = 0; i < arr2.length; i++) {
      if (Array.isArray(arr2[i])) {
        helper(arr2[i]);
      } else {
        result.push(arr2[i]);
      }
    }
  }
}

console.log(collector(arrs));
```

## Merge Sort, Quick Sort
使用原則：根據輸入的數據大小，選擇合適的演算法。

### Merge Sort
> 使用情境：數據量小，且記憶體空間足夠的話使用(用空間換時間)
- Time complexity：
best case: O(nlogn)
average case: O(nlogn)
worst case: O(nlogn)
space complexity：O(n)

### Quick Sort
> 使用情境：數據量大時使用；
但如果遇到幾乎已排序的輸入數據，時間複雜度會衝到：O(N²)，這時候我選擇用Quick Sort搭配 Insertion sort 以降低時間複雜度

- Time complexity：
best case: O(nlogn)
average case: O(nlogn)
worst case: O(N²)
space complexity：in place sort(原地排序)，不需額外的記憶體空間

## Sorting Algorithms I
最慢的三個, Average Performance O(n^2)

### Bubble Sort
- compares adjacent element and swap if they are in the wrong order
- 最簡單的演算法，現實生活中幾乎是沒有被應用

![](https://i.imgur.com/Vra8SSY.jpg =400x)

```=javascript
function bubbleSort(arr: number[]) {
  let step = 0;
  for (let i: number = 0; i <= arr.length - 2; i++) {

    for (let j: number = arr.length - 1; j >= i + 1; j--) {
      if (arr[j] < arr[j - 1]) {
        // swap arr[j] and arr[j - 1]
        let temp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = temp;
        step++;
      }
    }

  }
  console.log("It takes " + step + " steps to complete.");
  console.log(arr);
}

let test = [];

for (let i = 0; i < 100; i++) {
  test.push(Math.floor(Math.random() * 100));
}

bubbleSort(test);
```
### Insertion Sort
- 比bubble sort有效一點,但Big O一樣是 O(n^2)
- Keeping inserting a new value into a sorted array

![](https://i.imgur.com/wOWk0zc.jpg =500x)

```=javascript
let unsorted = [14, -4, 17, 6, 22, 1, -5];

insertionSort(unsorted);

function insertionSort(arr) {
  for (let j = 1; j <= arr.length - 1; j++) {
    let key = arr[j];
    i = j - 1;
    while (i >= 0 && arr[i] > key) {
      arr[i + 1] = arr[i];
      i -= 1;
    }
    arr[i + 1] = key;
  }

  console.log(arr);
  return arr;
}
```

### Selection Sort
- select the smallest value in unsorted array, and then swap it with the left most value in this unsorted array

![](https://i.imgur.com/Iw7XCNS.png =500x)


```=javascript
let unsorted = [14, -4, 17, 6, 22, 1, -5];

selectionSort(unsorted);

function selectionSort(arr) {
  for (let i = 0; i <= arr.length - 2; i++) {
    let minIndex = i;
    for (let j = i; j <= arr.length - 1; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // swap arr[minIndex] and arr[i]
    let temp = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = temp;
    console.log(arr);
  }

  console.log(arr);
  return arr;
}
```

## Sorting Algorithms II
Performance O(logn)

### Merge Sort
是一種基於分治法的排序算法。它的基本思想是：
- 原理
1. 將數組不斷地對半分割，直到每個子數組只剩一個元素。
2. 將兩個有序的子數組合併成一個有序的數組。
3. 重複這個過程，直到所有子數組合併成一個有序數組。
- 步驟
1. 分割：將數組從中間劃分為兩部分。
2. 遞歸排序：對每一部分分別遞歸進行 Merge Sort。
3. 合併：將兩個有序的子數組合併成一個有序的數組。
- combining two sorting arrays
- a classic example of "divde and conquer"
- 用的記憶體比較多，因為會宣告新的array

```=ts
function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  // 分割數組
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  // 遞歸排序
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  // 合併兩個有序數組
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // 合併剩餘的元素
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

// 測試 mergeSort
let arr = [3, 6, 8, 10, 1, 2, 1];
console.log(mergeSort(arr)); // [1, 1, 2, 3, 6, 8, 10]
```
例子
假設有一個數組 [3, 6, 8, 10, 1, 2, 1]，我們進行 Merge Sort 的過程如下：

1. 分割：將數組從中間劃分為兩部分：
- 左邊部分：[3, 6, 8]
- 右邊部分：[10, 1, 2, 1]

2. 遞歸分割：
- 將左邊部分 [3, 6, 8] 再次分割為 [3] 和 [6, 8]：
[6, 8] 再次分割為 [6] 和 [8]。
- 將右邊部分 [10, 1, 2, 1] 再次分割為 [10, 1] 和 [2, 1]：
[10, 1] 再次分割為 [10] 和 [1]。
[2, 1] 再次分割為 [2] 和 [1]。
3. 合併：
- 合併 [3] 和 [6, 8]，得到 [3, 6, 8]。
- 合併 [10] 和 [1]，得到 [1, 10]。
- 合併 [2] 和 [1]，得到 [1, 2]。
- 合併 [1, 10] 和 [1, 2]，得到 [1, 1, 2, 10]。
- 最後合併 [3, 6, 8] 和 [1, 1, 2, 10]，得到 [1, 1, 2, 3, 6, 8, 10]。

![](https://i.imgur.com/iD633vo.png)

complexity = n * log2n
Big O = O(nlogn)

```=javascript
// a1 and a2 is sorted array
function merge(a1, a2) {
  let result = [];
  let i = 0;
  let j = 0;

  while (i < a1.length && j < a2.length) {
    if (a1[i] > a2[j]) {
      result.push(a2[j]);
      j++;
    } else {
      result.push(a1[i]);
      i++;
    }
  }

  // a1 or a2 might have some elements left
  // use loop to put them all into result

  while (i < a1.length) {
    result.push(a1[i]);
    i++;
  }
  while (j < a2.length) {
    result.push(a2[j]);
    j++;
  }

  return result;
}

// Math.floor()最大整數
function mergeSort(arr) {
  if (arr.length === 1) {
    return arr;
  } else {
    let middle = Math.floor(arr.length / 2);
    let left = arr.slice(0, middle);
    let right = arr.slice(middle, arr.length);
    return merge(mergeSort(right), mergeSort(left));
  }
}

console.log(mergeSort([15, 3, 17, 18, 35, 11, 0, 36, -336, 1054]));
```

### Tree
- abstract data type
- node 指圈圈
- edge 指箭頭
- a tree should only have only one root
- tree is acyclic "graph"

![](https://i.imgur.com/FFHPXyK.png =400x)

#### Binary Tree 二元樹
each node has at most two children, which are referred to as the left child and right child

#### Complete Binary Tree
"almost-full" binary tree, the right most nodes of the bottom might be missing. 右邊不是完整的

#### Full Binary Tree
左右深度(長度)要一樣
a binary tree in which all leaf nodes have the same depth

#### Max Heap
a complete binary tree where the largest node is always the at root for any sub-trees
- 一定是complete binary tree
- any subtree, the root is always the biggest
- 任何一個subtree, root 都是最大的

![](https://i.imgur.com/uMP7tLF.jpg =400x)

![](https://i.imgur.com/NMU85gW.png =400x)

## Heap Sort
- uses ==Max Heap== to sort
- 用max heap做heap sort
- heap sort是用root和最後一個值互換,然後把root的值拿出來到新的array, 最後一個到root位置,一路比大小,重複動作

![](https://i.imgur.com/yyfCMvq.jpg =400x)

實做heap sort前提是個binary tree的arr,然後三步驟完成heap sort
1. build max heap
2. heap sort
3. max heapify

```=javascript
let heapSize;
let arr = [15, 3, 17, 18, 20, 2, 1, 666];
heapSort();
console.log(arr);

function buildMaxHeap() {
  heapSize = arr.length - 1;
  for (let i = Math.floor(heapSize / 2); i >= 0; i--) {
    maxHeapify(i);
  }
}

function maxHeapify(i) {
  let largest;
  let l = i * 2 + 1;
  let r = i * 2 + 2;
  if (l <= heapSize && arr[l] > arr[i]) {
    largest = l;
  } else {
    largest = i;
  }

  if (r <= heapSize && arr[r] > arr[largest]) {
    largest = r;
  }

  if (largest != i) {
    // swap A[i] with A[largest]
    let temp = arr[i];
    arr[i] = arr[largest];
    arr[largest] = temp;
    maxHeapify(largest);
  }
}

function heapSort() {
  buildMaxHeap();
  for (let i = arr.length - 1; i >= 0; i--) {
    // exchange A[0] with A[i]
    let temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
    heapSize -= 1;
    maxHeapify(0);
  }

  return arr;
}
```

### QuickSort
- 原理
Quick Sort 是一種基於分治法的排序算法。它的基本思想是：

1. 選擇一個「pivot」（樞軸）元素。
2. 將數組分成兩個部分：小於 pivot 的元素和大於 pivot 的元素。
3. 對這兩部分遞歸地進行 Quick Sort。

- 步驟
1. 選擇 pivot：通常選擇數組的第一個元素、中間元素或最後一個元素作為 pivot。
2. 分區：重新排序數組，使得所有小於 pivot 的元素都在 pivot 的左邊，所有大於 pivot 的元素都在 pivot 的右邊。這個過程稱為「分區」。
3. 遞歸排序：對 pivot 左邊和右邊的子數組分別遞歸進行 Quick Sort。
```=ts
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  // 選擇 pivot
  let pivot = arr[Math.floor(arr.length / 2)];
  let left = [];
  let right = [];

  // 分區
  for (let i = 0; i < arr.length; i++) {
    if (i === Math.floor(arr.length / 2)) continue;
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  // 遞歸排序並合併結果
  return [...quickSort(left), pivot, ...quickSort(right)];
}

// 測試 quickSort
let arr = [3, 6, 8, 10, 1, 2, 1];
console.log(quickSort(arr)); // [1, 1, 2, 3, 6, 8, 10]
```
例子
假設有一個數組 [3, 6, 8, 10, 1, 2, 1]，我們進行 Quick Sort 的過程如下：
1. 選擇 pivot：例如選擇中間的 8。
2. 分區：將數組分成兩部分：
- 左邊部分：[3, 6, 1, 2, 1]
- 右邊部分：[10]
3. 遞歸排序左邊部分和右邊部分：
- 左邊部分的 Quick Sort 結果：[1, 1, 2, 3, 6]
- 右邊部分：[10] 不需要排序
4. 合併結果：[1, 1, 2, 3, 6, 8, 10]

## LeedCode 刷題
### String 字串
- 反轉字串
```=ts
// st = 'olleh'
function rs ( str: string) {
  let res: string = '';
  let arr: string[] = str.split('');

  for(let i: number = arr.length - 1; i >= 0; i--) {
    res = res + arr[i];
    console.log(`result: ${res}`);
  }
  return res; //hello
}

rs('olleh');
```

- 檢查同義字 Valid Anagram
```=ts
function isAnagram( str1: string, str2: string): boolean {
  if(str1.length !== str2.length) return false;

  const s = str1.split('').sort().join();
  const t = str2.split('').sort().join();

  return s === t;
}

const result = isAnagram('anagram','nagaram');
console.log(`result: ${result}`);
```

### Binary Tree 二元樹
- Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
找出一個二元樹的深度
```=ts
var maxDepth = function(root) {
    return find(root); 
    // 遞迴函式
    function find(node){
        // 節點到底
        if(node === null){
            return 0;
        } 

        var deepL = 1;
        var deepR = 1;
        // 有左節點，往下一層找
        if(node.left !== null){
            deepL += find(node.left)
        }
        // 有右節點，往下一層找
        if(node.right !== null){
            deepR += find(node.right)
        }

        // 回傳較大的深度depth，給上一層節點
        return deepL > deepR ?　deepL: deepR;
    }
};
```
### Valid Parentheses 問題
問題描述
給定一個只包括 '('，')'，'{'，'}'，'[' 和 ']' 的字符串 s，判斷字符串是否有效。

有效字符串需滿足：
1. 左括號必須用相同類型的右括號閉合。
2. 左括號必須以正確的順序閉合。

- 解題思路
這道題目可以使用 stack 結構來解決。

當遇到左括號時，將其推入堆棧；
當遇到右括號時，檢查堆棧頂部的左括號是否與其匹配。

如果匹配，彈出堆棧頂部的左括號；
如果不匹配或堆棧為空，則字符串無效。
最後，檢查堆棧是否為空，如果為空，則字符串有效。

- 步驟
1. 初始化一個空的堆棧 stack。
2. 遍歷字符串 s 中的每個字符 char：
- 如果 char 是左括號 (, {, [，則將其推入堆棧。
- 如果 char 是右括號 ), }, ]，檢查堆棧頂部的元素：
    - 如果堆棧為空，返回 false。
    - 如果堆棧頂部元素與當前右括號匹配，彈出堆棧頂部元素。
    - 如果不匹配，返回 false。
3. 遍歷完畢後，檢查堆棧是否為空。如果為空，返回 true；否則，返回 false。
```=ts
function isValid(s) {
  const stack = [];
  const map = {
    '(': ')',
    '{': '}',
    '[': ']'
  };

  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    
    if (map[char]) {
      // char 是左括號
      stack.push(char);
    } else {
      // char 是右括號
      const top = stack.pop();
      
      if (map[top] !== char) {
        return false;
      }
    }
  }

  return stack.length === 0;
}

// 測試 isValid
console.log(isValid("()")); // true
console.log(isValid("()[]{}")); // true
console.log(isValid("(]")); // false
console.log(isValid("([)]")); // false
console.log(isValid("{[]}")); // true
```

- 適用資料結構
1. Stack：用於存儲左括號，幫助匹配相應的右括號。
2. Hash Table：用於存儲左括號與右括號的映射關係，方便檢查匹配。


### Merge Intervals
```=ts
function merge(intervals: number[][]): number[][] {
  if (intervals.length === 0) return [];

  // 排序區間，按起始點排序
  intervals.sort((a, b) => a[0] - b[0]);

  const merged: number[][] = [];
  let current: number[] = intervals[0];

  for (let i = 1; i < intervals.length; i++) {
    const interval = intervals[i];

    if (interval[0] <= current[1]) {
      // 如果有重疊，合併區間
      current[1] = Math.max(current[1], interval[1]);
    } else {
      // 如果沒有重疊，將 current 區間推入結果
      merged.push(current);
      current = interval;
    }
  }

  // 推入最後一個區間
  merged.push(current);

  return merged;
}
```
1. 排序：
- 我們對 intervals 按起始點進行排序，以便我們可以按順序處理區間。
2. 遍歷區間：
- 使用變量 current 來追蹤當前的合併區間。
- 如果新的區間與 current 區間重疊（即新的區間的起始點小於等於 current 的結束點），我們合併它們。
- 如果新的區間不重疊，我們將 current 區間加入結果，並更新 current 為新的區間。
3. 處理最後一個區間：遍歷完成後，將最後一個 current 區間加入結果列表。

- 應用場景
時間區間管理：合併重疊的時間區間，特別是在日曆應用程序中。
資源分配：處理重疊的資源使用情況，例如處理多個工作者的排班表。
###### tags: `study`

