# 鳥仔 ê 名 - 鳥仔 ê 形體外觀 [![GitHub](https://img.shields.io/badge/GitHub-black?logo=github)](https://github.com/siansiansu/tsiau-a-e-mia) [![hackmd-github-sync-badge](https://hackmd.io/jF7KDGz8Qg-AZ8O-r2n4OQ/badge)](https://hackmd.io/jF7KDGz8Qg-AZ8O-r2n4OQ) :::warning [< 轉去頭頁](https://hackmd.io/@siansiansu/Hy4VzNvha) ::: :::success 🙇‍♂️ 因為上班無閒，圖不一定改著上新的詞，請參照 [鳥仔 ê 名 - 鳥仔名詞對照表](/RhvbOM99SUKSTCF74DUPDw)。 ::: ## 雀 tshiok ![image](https://github.com/siansiansu/tsiau-a-e-mia/assets/33391637/2b0e845b-7141-44a3-9131-9156ab12eebc) 圖：[The Sibley Field Guide by David Allen Sibley](https://www.audubon.org/marketplace/sibley-field-guides) ## 頭 thâu ![image](https://github.com/siansiansu/tsiau-a-e-mia/assets/33391637/78b2f185-8e40-42b5-9c7d-34995646bba3) 圖：[The Sibley Field Guide by David Allen Sibley](https://www.audubon.org/marketplace/sibley-field-guides) ## 身軀 sin-khu ![image](https://github.com/siansiansu/tsiau-a-e-mia/assets/33391637/de37e5ae-c2cc-4d47-be7b-6678e81b847d) 圖：[The Sibley Field Guide by David Allen Sibley](https://www.audubon.org/marketplace/sibley-field-guides) ![image](https://github.com/siansiansu/tsiau-a-e-mia/assets/33391637/107fe2d7-3fba-4328-b68c-e5b5ed512890) 圖：[The Sibley Field Guide by David Allen Sibley](https://www.audubon.org/marketplace/sibley-field-guides) ## 翼 si̍t ![image](https://github.com/siansiansu/tsiau-a-e-mia/assets/33391637/c03c6f72-ab52-4841-a986-78e8509ee28a) 圖：[The Sibley Field Guide by David Allen Sibley](https://www.audubon.org/marketplace/sibley-field-guides) ![image](https://github.com/siansiansu/tsiau-a-e-mia/assets/33391637/595f1685-7f40-4138-8cd9-489f35a31df5) 圖：[The Sibley Field Guide by David Allen Sibley](https://www.audubon.org/marketplace/sibley-field-guides) ![image](https://github.com/siansiansu/tsiau-a-e-mia/assets/33391637/a0dc440a-b08d-435c-ab0f-119035488736) 圖：[The Sibley Field Guide by David Allen Sibley](https://www.audubon.org/marketplace/sibley-field-guides) ## 鷸鴴 u̍t-hîng ![image](https://github.com/siansiansu/tsiau-a-e-mia/assets/33391637/0686808b-ba16-4fec-9c46-82bf0b92bfd7) 圖：[The Sibley Field Guide by David Allen Sibley](https://www.audubon.org/marketplace/sibley-field-guides) ![image](https://github.com/siansiansu/tsiau-a-e-mia/assets/33391637/56f43dcf-3c13-45d6-bd0b-937c87564e46) 圖：[The Sibley Field Guide by David Allen Sibley](https://www.audubon.org/marketplace/sibley-field-guides) ## 鴨 ah ![image](https://github.com/siansiansu/tsiau-a-e-mia/assets/33391637/afc358f7-8e74-45a4-b653-164b311ecec5) 圖：[The Sibley Field Guide by David Allen Sibley](https://www.audubon.org/marketplace/sibley-field-guides) ## 鷗 oo ![image](https://github.com/siansiansu/tsiau-a-e-mia/assets/33391637/e291c5a3-2c65-4aa1-82bc-5092a4553eca) 圖：[The Sibley Field Guide by David Allen Sibley](https://www.audubon.org/marketplace/sibley-field-guides) ![image](https://github.com/siansiansu/tsiau-a-e-mia/assets/33391637/cf73f1f8-89a1-48cc-8e90-763ac963561e) 圖：[The Sibley Field Guide by David Allen Sibley](https://www.audubon.org/marketplace/sibley-field-guides) ![image](https://github.com/siansiansu/tsiau-a-e-mia/assets/33391637/bf030ada-7827-4b38-829c-e82d2d5ea9e4) 圖：[The Sibley Field Guide by David Allen Sibley](https://www.audubon.org/marketplace/sibley-field-guides)
Last changed by  
 
Soo Bîn-hiân
我是一名軟體工程師，也是一名賞鳥人。 如果您喜歡我的賞鳥筆記、台語文的推廣，歡迎小額贊助 https://p.ecpay.com.tw/5256DCE 請我喝咖啡。
166

Read more

55. Jump Game

時間複雜度：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
[軟體面試筆記] Dynamic Programming 動態規劃

求如何可以用最少花費、最少路徑達到目標的問題

5/15/2024
647. Palindromic Substrings

時間複雜度：O()

5/15/2024
Read more from Soo Bîn-hiân
Published on HackMD