Introduction ref : Bucket Sort form GeeksforGeeks ref : Bucket Sort from Leetcode 把目標數字分散在幾個桶子裡面，對每個桶子進行排序，最後依序取出數字，即為排序後的結果。 BUCKET_SORT 如果有負數的情況，可以分成兩個vector(正數和負數)，分別對兩個vector做bucket sort，最後再合併成一個。負數一定比較小，所以先取負數。 ref : Bucket Sort To Sort an Array with Negative Numbers 使用情況

Introduct vector<int> nums = {1, 5, -2, 7, 4, 3, 6, 2}; 如果要求 range sum，例如 sum(1, 5) = 17 有兩種operation，1. 求某個range的和，2. update每個一值。 如果使用vector，和prefix sum，分別的time complexity如下: update getSum vector

lee215在leetcode論壇上，有關題目的post。 Prefix Problems Problems 心得 2281. Sum of Total Strength of Wizards 1074. Number of Submatrices That Sum to Target 怎麼利用prefix sum把$O(N^4)$變成$O(N^3)$。解法

教學 參考leetcode官方的Exlort card。強力推薦。 Detailed Explanation of Graph 使用時機 union-find是==用來判斷node之間，是否有相連在一起。== 。可以根據root的相同與否來判斷。 只要問題是判斷連通問題，都可以使用union-find。 有些變形的題目是會限制連通路徑的條件。 Code Snippets

Introduce keyword : maximum, minimum 排序，這樣才可以從最小或是最大開始取。(sort) 判斷取這個之後符不符合條件 再取下一個 (Greedy) 把取過的結果丟進heap裡面，因為如果以後需要可以拿出來用。(從過去的數值中，選一個最大/最小的數值出來)(heap) heap: 走訪過的資料中，可以快速取出最大/最小的數值。

Introduction ref : Tree Traversals (Inorder, Preorder and Postorder) binary tree pre-order 順序 : parent -> left -> right, 從top -> bottom ==適用於要先決定好parent才可以決定child。== 1->2->4->5->3 in-order

Introduction 可以從前一個狀態推展到目前的狀態? 起始狀態是什麼? Problems 123. Best Time to Buy and Sell Stock III 一開始我使用暴力破解，但是時間效率不是很好。 class Solution { enum st{buy, sell};

C++ Container ref : https://srhuang.github.io/c++/2019/11/15/cplusplus-004.html Name Brief Iterators Capacity Element Access Modifiers Others

Useful references 面試準備 軟體工程師求職 (1)履歷撰寫 軟體工程師求職 (2)公告於市 軟體工程師求職 (3)面試準備 軟體工程師求職 (4)面試工具篇 分享技術部落格: 酷殼 中年找工作心得 軟體職缺準備心得

簡介 stack中保持著一定的順序，例如遞增或是遞減。 如果要新增的element比top還大/小。就把top pop出去。然後繼續往下比，直到保持一定的遞增或是遞減的順序。通常是找序列中比自己後面，但是值比自己還大/小的題目。 使用時機? 1. 需要==往前或是往後==尋找，==下一個比自己大或比自己小==的元素就可以使用monotonic stack PLE(Previous Less Element) Good reference : Sum of Subarray Minimums 找出之前比自己還小的值。

Introduction sliding window 定義 right定義為sliding window裡面的最右邊。 left定義為sliding window裡面的最左邊。 根據上面的定義，slding window的長度為 ==right - left + 1== left前進條件 結束條件 通常會有兩種結束條件的寫法。

Why Topological Sorting? 有向圖。 先處理indegree為0的node 當indegree不為0，表示還有其他路徑還沒到達這個node。 ==如果有cycle，處理過的node個數就不會等於總數。== 因為可以從相依性為0的node開始，一層一層像剝洋蔥一樣，把圖剝開來，讓問題有個好的解決順序。 Introduction Topological sort是針對有向圖，從indegree為零的點開始，因為indegree = 0表示沒有相依性。

Reference Segment Tree Introduction Segment Tree是一種data structure，可以有效的update, query某個區域的elements。通常是$O(logN)$。 特性 Segment Tree為binary tree，leaf node為array element。 內部node，為某個區間的特性。例如:某個區間的和，或是某個區間的最大值/最小值。

19. Remove Nth Node From End of List(Mediam) 移除singly linked list中從後面數來第N個node。 :::success 通常需要修改linked list第一個node的話，可以新增一個dummy head來改。 ::: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode *dummy_head = new ListNode(-1, head); ListNode *slow = dummy_head; ListNode *fast = dummy_head;

Introduction binary search的精隨就是在一個排序過的數列裡面，找出所要的值。因為每次都切半，所以可以時間複雜度達到O(logN)。相較於暴力破解法，例如答案在1~N之內，==如果測試函數可以讓你知道數字是往更大或更小的方向，就可以用binary search。== remove special case(答案不在可能的範圍內) 因為繼續使用binary search，如果答案比範圍內的還大，會得到left = sz。(還可以判斷) 如果答案比範圍內的還小，會得到left = 0。(無法判斷) 定義出答案可能出現的範圍left和right。 因為計算mid的方法，right必須是範圍最大值+1。 決定中間點，mid = left + (righ - left) / 2; 避免有overflow的問題。

Intrudoction Line Sweep顧名思義，就是針對x或是y軸依序掃描過去。 例如下圖，針對不同的interval，對x軸掃描。從最左邊掃到最右邊。 Line Sweep 因為，需要從最小掃到最大。所以interval必須要拆成起點和終點，分別給不同的flag，放進一個vector之後==遞增排序==。 Code Snippet 給你一個vector<vector<int>> intervals來代表區間，vector<int> queries來查詢在x = queries[i] 的時候有多少個重複interval，使用interval和queries來建立line sweep的準備資料。

Introudction 通常題目內會有一些keyword，這些keyword可能會定應某些解法，只是參考用，不一定每次都是這樣。當看到題目沒有思緒的時候可以往這邊想。 Keyword 題目出現的keyword keyword possible related topic ps

DFS 自己呼叫自己達到DFS的效果。可以分成兩種形式。 TOP-BOTTOM 從上到下 void dfs(node *root) { // 先做運算 ... // 最後在呼叫自己 dfs(root->next);

Introduction 通常答案和前後有關聯，所以必須先前後掃描才可以得出答案。 Problems 238. Product of Array Except Self 給你一個vector<int> nums，輸出所有vector的乘積除了自己。 因為每個答案和除了自己之外，前後的乘積，所以使用two-pass。 先計算出自己以外的forward和backward，最後把兩個vector乘起來就是答案。

Code Snippet 把left most的1切換成0 val = val & (val - 1); 把left mode的1取出來 mask = val & -val; Problems 137. Single Number II(Medium) 給你一個數列vector<int> nums，其中每個數都會出現3次，只有一個數出現一次。找出出現一次的數字。