Reverse Linked List II
Reverse Linked List II Problem DescriptionGiven the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list. IntuitionWe split three part by this linked list, head, body and tail. As Problem Description, we need to reverse body. And Combine head, body and tail. Algorithm12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849class Solut...
Sliding Windows
Sliding Windows 演算法主要用來處理連續子序列的問題，觀察 window 內部的元素，以及調整 window 的大小以及位置，來讓 window 可以符合所需要的條件。 核心作法sliding window 會有兩個指標 left 跟 right 來定義這個 window 的範圍 right 的目的是為了讓 window 來探索更多的元素來達到所需要的條件。left 的目的則是為了收縮 window 的大小，排除不必要的元素。 適用情景 從序列中尋找包含所需的連續子序列 求最大/最小長度、總和等優化問題 具有單調性：擴展窗口會改變某個狀態，收縮窗口可以恢復 常見題型 找最長/最短的子字串 找固定條件下的子陣列(如總和等於 k) 找不包含重複字母的子字串 找包含特定字母的最小子字串 時間複雜度 暴力解法: $O(n^2)$ ~ $O(n^3)$ Sliding Window: $O(n)$ - 每個元素最多被訪問兩次
Csharp Middleware
Middleware 是被組裝到 app pipeline 中的軟體，用於處理 request 和 response，每一個 component 可以： 決定是否要將 request 往下傳到 pipeline 的下一個 component。 在 pipeline 中的下一個 component 執行前後進行作業。 Request delegates 被用來建置 request pipeline，Request delegates 處理每一個 request。 Request delegates 使用 Run, Map 以及 Use 擴展方法來設定。每一個 Request delegates 可以是特定 in-line 像是 anonymous method (又稱 in-line middleware)，或者它可以被定義成可複用的類別。這些可被複用的類別以及 in-line anonymous method，我們也稱之 middleware component。Request pipeline 中的每個 middleware component 負責呼叫 pipeline ...
dotnet DI life cycle
在 ASP.NET Core 開發中，DI (dependency injection) 是最核心的設計模式之一，AddTransient(), AddScoped(), AddSingleton() 三種生命週期的差異能達到的目標截然不同，本文希望釐清當中的目的以及誤解。 核心概念三種生命週期的定義 生命週期 實例建立時機 使用場景 Transient 每次注入時都建立新實例 輕量級、無狀態的服務 Scoped 每個 HTTP Request 內共用同一實例 DbContext、需要在單一請求內保持狀態的服務 Singleton 整個應用程式生命週期只建立一次 設定檔、快取、共用資源 常見誤解Scoped 以及 Transient 常會被人誤解 Scoped：每一次的 Request 是共用同一個 Service InstanceTransient：每一次的 Request，每次使用 Service 都會建立一個的 Instance 範例12345678910111213141516171819202122232425262728293031323334...
Heap Sort
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253public class HeapSort{ public static void Sort(int[] arr) { int n = arr.Length; // 建立最大堆 for (int i = n / 2 - 1; i >= 0; i--) { Heapify(arr, n, i); } // 逐個從堆中取出最大值 for (int i = n - 1; i > 0; i--) { // 將當前最大值（根節點）移到數組末尾 int temp = arr[0]; arr[0] = arr[i]; ...
Quick Sort
做法 Quick Sort 與 Merge Sort 雖然利用同樣的概念，但是作法上差異很大，它會先從陣列中選擇一個「樞紐」（pivot），然後將所有小於樞紐的值都移到它的左邊、將所有大於樞紐的值都移到它的右邊。移動的過程我們並沒有去做排序，我們只是先將它們移到某一邊。ps. 結束時，只有 pivot 會在它最後正確的位置上（也就是只有樞紐是在排好序的位置）。 當樞紐完成以後，我們對左半部分再次進行同樣的處理（找到 pivot、移動位置），再處理右半部分。 時間複雜度分析： 最壞情況(Worst Case): O(n²) 當基準值總是選到最大或最小元素時 當數組已經排序或逆序時 分割非常不平衡時 最好情況(Best Case): O(n log n) 當每次分割都能將數組平均分成兩半時 遞迴樹的深度為 log n 每層需要 O(n) 的操作 平均情況(Average Case): O(n log n) 在隨機數據下，通常能達到這個效率 這也是實際應用中最常見的情況 1234567891011121314151617181920212223242526272829...
Insertion Sort
演算法原理： 將數組分為已排序和未排序兩部分 從未排序部分取出一個元素 在已排序部分找到適當的位置插入 重複步驟2-3，直到所有元素都排序完成 時間複雜度分析： 最壞情況(Worst Case): O(n²) 當數組完全逆序時 每個元素都需要移到最前面 比較和移動次數最多 最好情況(Best Case): O(n) 當數組已經排序時 每個元素只需要比較一次 不需要移動元素 平均情況(Average Case): O(n²) 對於隨機排列的數組 平均需要移動和比較 n²/4 次 空間複雜度： O(1)，只需要一個臨時變量存儲 key 123456789101112131415161718192021222324static void InsertionSort(int[] arr){ int n = arr.Length; // 從第二個元素開始，因為第一個元素可以視為已排序 for (int i = 1; i < n; i++) { // 保存當前要插入的元素 int ...
Selection Sort
演算法原理： 將數組分為已排序區域和未排序區域 在未排序區域中找到最小元素 將找到的最小元素與未排序區域的第一個元素交換 重複步驟2-3，直到所有元素都排序完成 時間複雜度分析： 最壞情況(Worst Case): O(n²) 外層循環執行 n-1 次 內層循環第一次執行 n-1 次，第二次 n-2 次，依此類推 比較次數：(n-1) + (n-2) + … + 1 = n(n-1)/2 交換次數：最多 n-1 次 最好情況(Best Case): O(n²) 即使數組已經排序 仍然需要執行所有的比較操作 只是交換次數可能減少 平均情況(Average Case): O(n²) 與最壞情況相同 選擇排序的特點是比較次數固定 空間複雜度： O(1)，只需要一個臨時變量來進行交換 選擇排序的特點： 優點： 實現簡單 交換次數少（最多 n-1 次） 對於小規模數據較為高效 缺點： 時間複雜度固定為 O(n²) 對於大規模數據效率低 不穩定排序（相同值的相對順序可能改變）
Bubble Sort
由後而前依序將兩兩相鄰的值互相比較，直到所有的值都被排到正確的位置為止。 最壞情況 (Worst Case): O(n²) 當數組完全逆序時（如 [5,4,3,2,1]） 外層循環需要執行 n-1 次 內層循環每次需要執行 n-i-1 次 總比較次數：(n-1) + (n-2) + … + 1 = n(n-1)/2 所以是 O(n²) 最好情況 (Best Case): O(n) 當數組已經排好序時（如 [1,2,3,4,5]） 只需要執行一次外層循環 內層循環執行 n-1 次比較 由於沒有發生交換，會提前退出 所以是 O(n) 平均情況 (Average Case): O(n²) 在隨機數據的情況下 仍然需要進行大量的比較和交換 複雜度接近最壞情況 圖示現假設有一陣列 [6,5,4,9,1]，要透過氣泡排序將陣列由小排到大的過程如下： 1234567891011121314151617181920212223242526272829static void BubbleSort(int[] arr){ int n = arr....
Binary Search Tree
定義: 若一顆二元樹滿足以下兩點:a. 左子節點的值小於節點的值 b. 右子節點的值大於節點的值 即可稱為二元搜尋樹 12345 2 6 / \ / \1 3 5 8 <-----像這樣, 這兩棵都是BST / / \ 3 7 9 二元搜尋樹的查詢, 插入, 走訪, 查詢最大最小值和刪除操作 提示: 刪除節點有兩個子節點的時候, 要用它的中序後繼來代替該節點, 演算法為: 找到被刪除節點的右子節點, 然後查詢此右子節點下的最後一個左子節點, 即此顆子樹的最小值節點, 這就是被刪除節點的中序後繼節點. 何謂前序, 中序, 後序? 以上圖右邊的三層樹為例, 看1~2層的子樹: preorder 前序: 6 -> 5 -> 8 inorder 中序: 5 -> 6 -> 8 postorder 後序: 5 -> 8 -> 6 若看整顆: 中序: 3 -> 5 -> 6 -> 7 -> 8 -&g...
