---
# System prepended metadata

title: linked-list

---

- [ ] linked list
- [ ] binary tree
- [ ] selection sort
- [ ] quick sort
- [ ] bubble sort
- [ ] dynamic problem

# linked-list

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

```
class LinkedList {
    constructor(){
        this.length = 0;
        this.head = null;
    }
}

class Node {
    constructor(item) {
        this.item = item;
        this.next = null;
    }
}
```


# Mysql

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

- 連接層：最上層是一些客戶端和連接服務。主要完成一些類似於連接處理、授權認證、及相關的安全方案。在該層上引入了線程池的概念，為通過認證安全接入的客戶端提供線程。同樣在該層上可以實現基於SSL的安全鏈接。服務器也會為安全接入的每個客戶端驗證它所具有的操作權限。
- 服務層：第二層服務層，主要完成大部分的核心服務功能， 包括查詢解析、分析、優化、緩存、以及所有的內置函數，所有跨存儲引擎的功能也都在這一層實現，包括觸發器、存儲過程、視圖等
- 引擎層：第三層存儲引擎層，存儲引擎真正的負責了MySQL中數據的存儲和提取，服務器通過API與存儲引擎進行通信。不同的存儲引擎具有的功能不同，這樣我們可以根據自己的實際需要進行選取
- 存儲層：第四層為數據存儲層，主要是將數據存儲在運行於該設備的文件系統之上，並完成與存儲引擎的交互

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


char是固定長度，varchar長度可變：

char(n) 和varchar(n) 中括號中n 代表字符的個數，並不代表字節個數，比如CHAR(30) 就可以存儲30 個字符。

存儲時，前者不管實際存儲數據的長度，直接按char 規定的長度分配存儲空間；而後者會根據實際存儲的數據分配最終的存儲空間

相同點：

char(n)，varchar(n)中的n都代表字符的個數
超過char，varchar最大長度n的限制後，字符串會被截斷。
不同點：

char不論實際存儲的字符數都會佔用n個字符的空間，而varchar只會佔用實際字符應該佔用的字節空間加1（實際長度length，0<=length<255）或加2（length>255）。因為varchar保存數據時除了要保存字符串之外還會加一個字節來記錄長度（如果列聲明長度大於255則使用兩個字節來保存長度）。
能存儲的最大空間限制不一樣：char的存儲上限為255字節。
char在存儲時會截斷尾部的空格，而varchar不會。
char是適合存儲很短的、一般固定長度的字符串。例如，char非常適合存儲密碼的MD5值，因為這是一個定長的值。對於非常短的列，char比varchar在存儲空間上也更有效率。
————————————————
版权声明：本文为CSDN博主「90后小伙追梦之路」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_67322837/article/details/123852019

mysql index

優勢
提高數據檢索效率，降低數據庫IO成本
降低數據排序的成本，降低CPU的消耗
劣勢
索引也是一張表，保存了主鍵和索引字段，並指向實體表的記錄，所以也需要佔用內存
雖然索引大大提高了查詢速度，同時卻會降低更新表的速度，如對錶進行INSERT、UPDATE和DELETE。因為更新表時，MySQL不僅要保存數據，還要保存一下索引文件每次更新添加了索引列的字段， 都會調整因為更新所帶來的鍵值變化後的索引信息
————————————————
版权声明：本文为CSDN博主「90后小伙追梦之路」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_67322837/article/details/123852019

# Bubble Sort

氣泡排序法(Bubble Sort)又稱交換排序法，原理是從第一筆資料開始，逐一比較相鄰兩筆資料，如果兩筆大小順序有誤則做交換，反之則不動，接者再進行下一筆資料比較，所有資料比較完第1回合後，可以確保最後一筆資料是正確的位置。

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

n=5
第1回合比較了4次，n-1次
第2回合比較了3次，n-2次
第3回合比較了2次，n-3次
第4回合比較了1次，n-4次
總共比較了4回合，n-1回合

(n-1) + (n-2) + .... + 1 = n(n-1) / 2
平均時間複雜度為: O(n²)

```
js: 

let arr = [8, 5, 4, 7, 9];

const n = arr.length;

// 一共要跑 n 輪
for (let i = 0; i < n; i++) {

    // 從第一個元素開始，不斷跑到第 n - 1 - i 個
    // 原本是 n - 1，會再加上 - i 是因為最後 i 個元素已經排好了
    // 所以沒必要跟那些排好的元素比較
    for (let j = 0; j < n - 1 - i; j++) {
        if (arr[j] > arr[j + 1]) {
            [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        }
    }
}

// 補充 js陣列內元素快速交換位置:

// target a[3]
a = [0,1,2,3,4,5]

// 向前交換
[a[3], a[3 - 1]] = [a[3 - 1], a[3]]
// result: [0,1,3,2,4,5]

// 1跟4交換
[a[1], a[4]] = [a[4], a[1]]
// result: [0,4,2,3,1,5]

go:


```

# Selection Sort
當你第一輪跑完之後，你就找到整個陣列的最小值了，然後你把尋找範圍從 0 ~ n-1 變成 1 ~ n-1，重複做一樣的事情就可以了。或是，你也可以想成是：找到最小值，第二小值，第三小值...第 n 小值。

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


```
let data = [8,6,10,5,3,9,2,7,4,1]

for (let i = 0; i < data.length; i++) {
    let minValue = data[i];
    let minIndex = i;
    for (let j = i; j < data.length; j++) {
        // 小於最小值
        if (data[j] < minValue) {
            minValue = data[j];
            minIndex = j;
        }
    }
    // ES6 的用法，交換兩個數值
    [data[minIndex], data[i]] = [data[i], data[minIndex]];
}

```

# Insertion Sort


# 1. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

```

思路用HashMap把目標存起來

func twoSum(nums []int, target int) []int {

	valueMap := make(map[int]int)

	for k, v := range nums {
		idx, ok := valueMap[target-v]
		if ok {
			return []int{idx, k}
		}
		valueMap[v] = k
	}

	return nil
}
```

# 2. Final Value of Variable After Performing Operations


There is a programming language with only four operations and one variable X:

++X and X++ increments the value of the variable X by 1.
--X and X-- decrements the value of the variable X by 1.
Initially, the value of X is 0.

Given an array of strings operations containing a list of operations, return the final value of X after performing all the operations.

```
func finalValueAfterOperations(operations []string) int {
    plus := 0
	minus := 0
	for _, value := range operations {
		if value == "++X" || value == "X++" {
			plus++
		}

		if value == "--X" || value == "X--" {
			minus++
		}
	}

	return plus - minus
}
```

# Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

 

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"
Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

```
func longestCommonPrefix(strs []string) string {
    
    if len(strs) == 0 {
		return ""
	}

	res := ""
	for i, v := range strs[0] {
		c := byte(v)
		for _, s := range strs {
			if len(s) < i+1 || s[i] != c {
				return res
			}
		}
		res += string(c)
	}

	return res
}
```

# Check for Balanced Brackets in an expression (well-formedness) using Stack

Given an expression string exp, write a program to examine whether the pairs and the orders of “{“, “}”, “(“, “)”, “[“, “]” are correct in the given expression.

Example: 

Input: exp = “[()]{}{[()()]()}” 
Output: Balanced
Explanation: all the brackets are well-formed

Input: exp = “[(])” 
Output: Not Balanced 
Explanation: 1 and 4 brackets are not balanced because 
there is a closing ‘]’ before the closing ‘(‘

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

```
function areBracketsBalanced(expr)
{
     
    // Using ArrayDeque is faster
    // than using Stack class
    let stack = [];
 
    // Traversing the Expression
    for(let i = 0; i < expr.length; i++)
    {
        let x = expr[i];
 
        if (x == '(' || x == '[' || x == '{')
        {
             
            // Push the element in the stack
            stack.push(x);
            continue;
        }
 
        // If current character is not opening
        // bracket, then it must be closing.
        // So stack cannot be empty at this point.
        if (stack.length == 0)
            return false;
             
        let check;
        switch (x){
        case ')':
            check = stack.pop();
            if (check == '{' || check == '[')
                return false;
            break;
 
        case '}':
            check = stack.pop();
            if (check == '(' || check == '[')
                return false;
            break;
 
        case ']':
            check = stack.pop();
            if (check == '(' || check == '{')
                return false;
            break;
        }
    }
 
    // Check Empty Stack
    return (stack.length == 0);
}
```

https://www.youtube.com/watch?v=mQJOr-_pR_4
```
```