# 鳥仔 ê 名 - 鷦眉科 tsiau-bî-kho [![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/ZXkoNmA4TzCtPwOztqW69Q/badge)](https://hackmd.io/ZXkoNmA4TzCtPwOztqW69Q) :::warning [< 轉去頭頁](https://hackmd.io/@siansiansu/Hy4VzNvha) ::: :::success ### 📖 名詞註記 #### 📎 詞源 - [台]：依據台灣本土的台語俗稱。 - [日]：外來語，依據日本名。 - [英]：外來語，依據英文名。 - [華]：外來語，依據台灣使用的華語名。 - [中]：外來語，依據中國使用的華語名。 #### 🎏 特有亞種 - [台亞]：台灣亞種。 - [日亞]：日本亞種。 #### 🐦 其他註記 - 🎯：考慮分類學、本土俗名佮台語詞的用法，推薦做為這个唯一物種的台語俗名。 - ✳️：統稱，有兩個以上的物種攏會使叫這个名。 ::: ## [台灣鷦眉 タイワンサザイチメドリ Taiwan Cupwing](https://ebird.org/species/taiwrb1) ![](https://inaturalist-open-data.s3.amazonaws.com/photos/89046451/medium.jpg) <br/> (c) 洪廷維, some rights reserved (CC BY-NC) - 🎯 台灣鷦眉 tâi-uân-tsiau-bî
Last changed by  
 
Soo Bîn-hiân
我是一名軟體工程師，也是一名賞鳥人。 如果您喜歡我的賞鳥筆記、台語文的推廣，歡迎小額贊助 https://p.ecpay.com.tw/5256DCE 請我喝咖啡。
41

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