GitHubhackmd-github-sync-badge
5/16/2024時間複雜度:O()
5/15/2024演算法Recursive把問題切成相同的小題目。Tree Traversal分為pre-order, in-order,post-order和level-order,可以使用DFS或BFS.Depth-First-Search/Breadth-First-Search依深度或是廣度瀏覽所有的資料Dynamic Programming通常是求maximal或是minimal或是幾種方法的時候會用到。Divide and Conquer將題目分成一樣的小題目,最後將結果合併起來。Binary Search在排序過的資料中,尋找目標值。用二分法找效率為O(logN)。Two-pointers Binary Search在排序過的1D或是2D vector中尋找想要的值。Two Pointers通常為array中,使用前後兩個pointer來比較資料。Fast Slow Pointers在linked-list中使用快慢pointer來解決問題。Combination在所有的組合中,找出最佳的答案。Sliding Window需要找出連續資料的關聯性。ex. substring, subarray.BacktrackingSort algorithmSelection/Bubble/Insertion/Heap sortBucket Sort把數字分成一個一個的區段,ex: [0] : 0~9, [1] : 10~19, [2] : 20~29Counting/Radix SortGreedy + heap如果問題是詢問max或是min,最直覺的解法就是依序把最大或是最小的數值相加,但是有時候必須刪減就是用heap提供的數值。Greedy每次都把目前的狀態update到最有利的狀態。資料結構Set只能儲存value,必把value當成key。Map把資料做成key-value的對應,可以快速找到key對應的value。或是使用客製的key來對資料做統計。stack [後進先出]利用後進先出的特性,可以解決pair的問題或是反轉的效果。兩個stack也可以組成不同的特性。Queue先進先出,可以用在BFS。使用BFS通常可以解決最小數量的問題。Double-end Queue(deque)一般的queue,只能pop_front和push_back,但是double-end queue可以pop_front/back和push_front/back。兩頭都可以做pop/push。monotonic stack一樣是stack,但是stack的內容有照一定的順序排列。遞增或遞減。找出前後比自己大或小的element。或是往左看往右看的最大值。Binary Search Tree(BST)他是一個binary tree,但是準守著左邊的node小於root, 右邊的node大於root。Graph有向圖和無向圖。Disjoint set/Union Find使用root array來紀錄每個vertex的root或是parent nodeMinimal spinning tree最小weight和,可以把全部的node連起來的tree,通常使用greedy演算法,每次都從最小的weight開始選,如果沒在graph裡面就加進來。Single Source Shortest Path AlgorithmDijkstra類似BFS,但是使用priority_queue來取最小weight路徑。Shortest Path Faster Algorithm(SPFA)使用vector和queue來記錄從source到每個node的最短路徑。可用在negative weight。Floyd Warshall AlgorithmTopological sorting走訪有相依性的圖。Trie統計字串或是數字的bitPriority_queue統計最大最小值的出現。Binary Index Tree(BIT)計算range sum可以達到 update是O(logN),getSum也是O(logN)使用prefix sum只能達到 update是O(N), getSum是O(1)使用array sum 只能達到 update是O(1), getSum是O(N)Segment Tree和Binary Index Tree一樣,可以用來計算range sum。除此之外還可以計算range maximum/minimum,或是有效率的update一個區間的elements。其他Brute Force暴力破解走訪所有的可能性,來找出最佳解。通常是面試時提出的第一個解法。從這邊也許可以延伸出sub-optimal或是optimal的解法。Math數學解法有些時候分析完題目,發現用數學解反而更精簡。Randomized選取element並且每個的機率都一樣。Bit Manipulation對bit做處理。加法器設計prefix sumprefix_sum[i] = sum(nums[0:i - 1]); 前i個的和,適合用來解區段sum的題目。subset sum把一個數列分成若2個subset,求出兩個subset的特殊 關係。例如sum(s1) = sum(s2) 或是 sum(s1) - sum(s2) = target等等。Interval使用[start, end)來表示一個區間。Line Sweep依序掃描x或是y,來得到答案。Binary Lifting尋找第k個parent的技巧。two pass題目的解答和前後都有關係。
5/15/2024求如何可以用最少花費、最少路徑達到目標的問題
5/15/2024or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up