YouChen's Blog

3sumProblem DescriptionGiven an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. IntuitionWe can break down this problem by fixing one element and converting it into a 2Sum problem: Fix one element as the first number Solve for the remaining elements using the 2Sum approach Time Complexity: $O(n^2)$Space Complexity: $O(n)$ for s...

Binary Tree Level Order TraversalProblem DescriptionGiven the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level). IntuitionDFSWe use layer to track current node’s depth. We insert values from top to bottom and from left to right by visiting left subtree before right subtree. BFSWe use a queue to track all nodes at the current level. For each level, we process all nodes in the queue: extract their values and add their childr...

105. Construct Binary Tree from Preorder and Inorder TraversalProblem DescriptionGiven two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree. IntuitionThe front element of preorder traversal is the tree’s root node(the middle of inorder traversal). We use it to determine which elements belong the left subtree and the right subtree, and keep comparing the preo...

Container With Most WaterProblem DescriptionYou are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the $i^{th}$ line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store. Notice that you may not slant the container. IntuitionThe area of water a container is determined by two factors: heig...

Program (程式)Program 意旨軟體工程師在 IDE、editor 等所寫的程式碼(code)，也就是說還尚未 load 入記憶體的 code，我們稱之為 Program。• 相同 Program 所建立的 Process 可以多個同時存在。 Process (行程，亦可稱作處理程序、進程)Process 是正在執行中的 Program 實例，點開應用程式就是讓 OS 從硬碟中載入到 Memory 中，分配必要的系統資源，建立一個 Process 來執行它。 以下條列幾點 Process 的觀念 Process 是電腦中已執行 Program 的 Instance。 每一個 Process 是互相獨立的。 Process 本身不是基本執行單位，而是 Thread 的資源管理和執行環境。 Process 需要一些資源才能完成工作，如 CPU、記憶體、檔案以及 I/O 裝置。 在多功作業系統(Multitasking Operating System)中，可以同時執行數個 Process ，然而一個 CPU 一次只能執行一個 Process，而 Process...

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 演算法主要用來處理連續子序列的問題，觀察 window 內部的元素，以及調整 window 的大小以及位置，來讓 window 可以符合所需要的條件。 核心作法sliding window 會有兩個指標 left 跟 right 來定義這個 window 的範圍 right 的目的是為了讓 window 來探索更多的元素來達到所需要的條件。left 的目的則是為了收縮 window 的大小，排除不必要的元素。 適用情景 從序列中尋找包含所需的連續子序列 求最大/最小長度、總和等優化問題 具有單調性：擴展窗口會改變某個狀態，收縮窗口可以恢復 常見題型 找最長/最短的子字串 找固定條件下的子陣列(如總和等於 k) 找不包含重複字母的子字串 找包含特定字母的最小子字串 時間複雜度 暴力解法: $O(n^2)$ ~ $O(n^3)$ Sliding Window: $O(n)$ - 每個元素最多被訪問兩次

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 ...

在 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...

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]; ...