# 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在資料量小才會用
## 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
## Algorithm Design
### Linear Search
漸進式搜尋, sequentially check each element
- 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
- 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 交集
找出兩個陣列中重複的元素
- 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)==
- 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==
- 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
- 讓==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解
- 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解
- 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
Max Sum
Min Sum
- 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
- 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
- 最簡單的演算法，現實生活中幾乎是沒有被應用
```=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
```=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
```=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]。
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"
#### 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 都是最大的
## Heap Sort
- uses ==Max Heap== to sort
- 用max heap做heap sort
- heap sort是用root和最後一個值互換,然後把root的值拿出來到新的array, 最後一個到root位置,一路比大小,重複動作
實做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`
Sign in with Wallet
Connect another wallet