你應該知道的面試基礎和解題技巧

What is an algorithm?

所謂的演算法，就是描述一個計算/操作的過程，
這個過程可以用有限的長度來描述如何解決問題。
或者更簡單的說法：
*演算法，就是解決問題的方法流程。 *

Why do we need to learn algorithms?

先講一下筆者的經歷：筆者當了7年多的工程師，當中有2.5年和Android kernel/HAL/framework相關，2年跟Android App和一般Software有關，後面則是ML/Deep Learning為主，在面試時也分別面過不同的職位，唯獨幾乎萬變不離其宗的，就是白板題。

面試官拿出一道你見過或沒見過的題目，問你該怎麼解，
你思考後給出回答，並且討論可以改進的方式及可能的錯誤，
這應該是所有面試者都會歷經的流程。

那麼，你是否經歷過這樣的狀況？

「這個題目的類型看起來好眼熟，可是不知道從何下手，該怎麼辦 QQ」

白板題的重點，就在於演算法 。掌握好演算法，就跟數學學會公式一樣，
可以將一些複雜的東西簡單化，平常練習的題目多了，
套起公式來自然得心應手，就算題目再怎麼變，也萬變不離其宗。

當然，後面還會衍生出一個問題：一個題目該用哪種演算法比較好？
但這是另一個故事了，我們以後再談XD

Why LeetCode?

那麼，現在網路上可以供作練習的網站相當之多，除了LeetCode外，
你可能還聽過HackerRank及CodeWar等，
那麼為什麼是用LeetCode而不是其他呢？

以筆者的經驗，HackerRank相當適合做為熟悉語言特性使用 ，但不適合目標是熟練解題的人。你可以在其 “LANGUAGE PROFICIENCY”的分類中針對特定的程式語言一路寫到尾，這樣可以對這個語言有一個比較基本的認識。
而雖然它們有”Interview Preparation Kit”的部分，但相對題目較為簡單，涵蓋範圍也較少。舉例來說，在Tree的分類上只有5題，這一點點的量，其實相當不足。同時，HackerRank的題目往往較長，限制也通常較多，(這裡是指Problem Solving分類)，和一般面試會遇到的題目型態較為不同。
但若今天的形式是給你1個半小時解3題 的話，
那麼HackerRank的模式就會很適合你。

Codewar的話，較為偏向打怪(題目)升級的模式，每個題目都會有一個等級，解決題目累積經驗值並提升自己的level會有一種練功的感覺。筆者不推薦的原因在於

1. 網站讀取速度偏慢 
2. 題目沒有編號 ，你會做到不知道哪裡去也不確定自己有沒有準備好XD 
3. Discuss區不像LeetCode傾向於分享整組解法

那LeetCode呢？
當前(2019/06/26)的題目量總共有1096題，Easy佔了當中的319題。
筆者練習的題目總量為348題: Easy 266, Medium 65, Hard 17。

2020/08/18:
當前的的題目量總共有1553題，Easy佔了當中的430題。
筆者練習的題目總量為502題: Easy 288, Medium 179, Hard 35。

以筆者的個人經驗，只要將LeetCode的Easy難度寫過一輪，
搭上少量的Medium和些許的Hard題目，便足以應付絕大多數的白板題。
這當中要求的是盡可能不要去翻別人的答案，自己先兜出解法後，
在能力範圍內去盡力提升這個解的速度，
真的不行或卡超過半小時才去參考別人的解答。

在練習到一般的白板題都不能難倒你後，就可以將注意力集中在你主要經驗相關的領域了。(如筆者找AI職缺，那麼就會偏向ML相關的知識)

What’s the plan?

接下來的系列，將會以LeetCode從第1題開始順序往下，以Easy題目為主，參雜少量Medium題，搭配題目分析及演算法講解，在整理先前自我學習的過程中，希望能對大家有所幫助。解題所用的程式語言會以Java 及Python 為主，但概念基本上不會差多少，若是使用其他語言的朋友應該也可能從中理解思路。使用的解有些可能會因為我看到更好的解法，會使用其他人在Discuss區塊提出來的解，筆者會盡量標明是哪一位LeetCode user所寫的。

除此以外，若文章中有錯字、寫錯或有任何讓人感到疑問的地方，
歡迎留言告訴我！

2020/09/05:
容筆者工商一下， 「從Leetcode學演算法｜進階篇」及 加贈的**「從Leetcode學演算法｜面試篇」已經全數上傳完囉！**

目前只剩下給讀者的進階篇+面試篇(3150) 和全套同捆優惠(3990) 了QQ
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」：
https://bit.ly/leetcodeadv
「從Leetcode學演算法」全套(基礎/進階/面試篇)同捆優惠：
https://bit.ly/leetcodeall

內容介紹：
這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！

PS. 因應建議，將文章目錄連結貼在底下，方便大家查找。
(請使用Ctrl+F輸入想要查找的題目或題型)

從LeetCode學演算法 - 1

1. Two Sum (Easy)

從LeetCode學演算法 - 2
0014. Longest Common Prefix (Easy)

從LeetCode學演算法 - 3 Two Pointers
0015. 3Sum (Medium)

從LeetCode學演算法 - 4 Linked List (1)
0021. Merge Two Sorted Lists (Easy)

從LeetCode學演算法 - 5 In-Place
0026. Remove Duplicates from Sorted Array (Easy)

從LeetCode學演算法 - 6 Binary Search
0035. Search Insert Position (Easy)

從LeetCode學演算法 - 7 Dynamic Programming (1)
0053. Maximum Subarray (Easy)

從LeetCode學演算法 - 8 String Manipulation (1)
0067. Add Binary (Easy)

從LeetCode學演算法 - 9 Dynamic Programming (2)
0070. Climbing Stairs (Easy)

從LeetCode學演算法 - 10 Linked List (2)
0083. Remove Duplicates from Sorted List (Easy)

從LeetCode學演算法 - 11 Bitwise Operation (1) 0089. Gray Code (Medium)

從LeetCode學演算法 - 12 Linked List (3)/ Stack (1)
0092. Reverse Linked List II (Medium)

從LeetCode學演算法 - 13 Tree (1) 0100. Same Tree (Easy)

從LeetCode學演算法 - 14 Tree (2) / Queue (1)
0101. Symmetric Tree (Easy)

從LeetCode學演算法 - 15 Bitwise Operation (2)
0136. Single Number (Easy)

從LeetCode學演算法 - 16 BST (1)
0098. Validate Binary Search Tree (Medium)

從LeetCode學演算法 - 17 Tree (3)
0094. Binary Tree Inorder Traversal (Medium)

從LeetCode學演算法 - 18 Tree (4)
0124. Binary Tree Maximum Path Sum (Hard)

從LeetCode學演算法 - 19 Tree (5)
0111. Minimum Depth of Binary Tree (Easy)

從LeetCode學演算法 - 20 Tree (6)
0110. Balanced Binary Tree (Easy)

從LeetCode學演算法 - 21 Dynamic Programming (3)
0062. Unique Paths (Medium)

從LeetCode學演算法 - 22 Array (1)
0169. Majority Element (Easy)

從LeetCode學演算法 - 23 Array (2)
0229. Majority Element II (Medium)

從LeetCode學演算法 - 24 Dynamic Programming (4)
0063. Unique Paths II (Medium)

從LeetCode學演算法 - 25 Array (3):
0283. Move Zeroes (Easy)

從LeetCode學演算法 - 26 Dynamic Programming (5)
0096. Unique Binary Search Trees (Medium)

從LeetCode學演算法 - 27 Array (4)
0189. Rotate Array (Easy)

從LeetCode學演算法 - 28 Dynamic Programming (6)
0198. House Robber (Easy)

從LeetCode學演算法 - 29 Dynamic Programming (7)
0213. House Robber II (Medium)

從LeetCode學演算法 - 30 Tree (7)
0144. Binary Tree Preorder Traversal (Medium)

從LeetCode學演算法 - 31 Linked List (4)
0141. Linked List Cycle (Easy)

從LeetCode學演算法 - 32 BST (2)
0700. Search in a Binary Search Tree (Easy)

從LeetCode學演算法 - 33 Array (5)
0905. Sort Array By Parity (Easy)

從LeetCode學演算法 - 34 Array (6)
0977. Squares of a Sorted Array (Easy)

從LeetCode學演算法 - 35 BST (3)
0108. Convert Sorted Array to Binary Search Tree (Easy)

從LeetCode學演算法 - 36 Merge Sort (1)
0148. Sort List (Medium)

從LeetCode學演算法 - 37 Dynamic Programming (8)
0121. Best Time to Buy and Sell Stock (Easy)

從LeetCode學演算法 - 38 Array (7)
0088. Merge Sorted Array (Easy)

從LeetCode學演算法 - 39 Array (8) / Hash Table (1)
1160. Find Words That Can Be Formed by Characters (Easy)

從LeetCode學演算法 - 40 Array (9)
0238. Product of Array Except Self (Medium)

從LeetCode學演算法 - 41 Hash Table (2)
0242. Valid Anagram (Easy)

從LeetCode學演算法 - 42 Backtracking (1) / Tree (8)
0257. Binary Tree Paths (Easy)

從LeetCode學演算法 - 43 BFS (1) / Queue (2)
1161. Maximum Level Sum of a Binary Tree (Medium)

從LeetCode學演算法 - 44 Linked List (5)
0160. Intersection of Two Linked Lists (Easy)

從LeetCode學演算法 - 45 DFS (1)
0200. Number of Islands (Medium)

從LeetCode學演算法 - 46 BFS (2) / Queue (3)
0199. Binary Tree Right Side View (Medium)

從LeetCode學演算法 - 47 Array (10)
0204. Count Primes (Easy)

從LeetCode學演算法 - 48 Trie (1)
0819. Most Common Word (Easy)

從LeetCode學演算法 - 49 Hash Table (3)
0217. Contains Duplicate (Easy)

從LeetCode學演算法 - 50 Tree (9)
0226. Invert Binary Tree (Easy)

從LeetCode學演算法 - 51 BST (4)
0235. Lowest Common Ancestor of a Binary Search Tree (Easy)

從LeetCode學演算法 - 52 Array (11)
0268. Missing Number (Easy)

從LeetCode學演算法 - 53 Binary Search (2)
0278. First Bad Version (Easy)

從LeetCode學演算法 - 54 DFS (2)
0114. Flatten Binary Tree to Linked List (Medium)

從LeetCode學演算法 - 55 DFS (3)
0236. Lowest Common Ancestor of a Binary Tree (Medium)

從LeetCode學演算法 - 56 Binary Search (3)
0240. Search a 2D Matrix II (Medium)

從LeetCode學演算法 - 57 Binary Search (4)
0074. Search a 2D Matrix (Medium)

從LeetCode學演算法 - 58 Two Pointer (2)
0075. Sort Colors (Medium)

從LeetCode學演算法 - 59 Backtracking (2) / DFS (4)
0079. Word Search (Medium)

從LeetCode學演算法 - 60 Backtracking (3) / DFS (5)
0078. Subsets (Medium)

從LeetCode學演算法 - 61 Dynamic Programming (9)
1140. Stone Game II (Medium)

從LeetCode學演算法 - 62 Tree (10)
0102. Binary Tree Level Order Traversal (Medium)

從LeetCode學演算法 - 63 Backtracking (4) / DFS (6)
0077. Combinations (Medium)

從LeetCode學演算法 - 64 Array (12) / Two Pointer (3)
0080. Remove Duplicates from Sorted Array II (Medium)

從LeetCode學演算法 - 65 Array (13)
0926. Flip String to Monotone Increasing (Easy)

從LeetCode學演算法 - 66 Bitwise Operation (3)
0190. Reverse Bits (Easy)

從LeetCode學演算法 - 67 Bitwise Operation (4)
0191. Number of 1 Bits (Easy)

從LeetCode學演算法 - 68 Bitwise Operation (5)
0201. Bitwise AND of Numbers Range (Medium)

從LeetCode學演算法 - 69 Hash Set (1)
0202. Happy Number (Easy)

從LeetCode學演算法 - 70 Linked List (6)
0203. Remove Linked List Elements (Easy)

從LeetCode學演算法 - 71 Hash Table (4)
0205. Isomorphic Strings (Easy)

從LeetCode學演算法 - 72 Linked List (7)
0206. Reverse Linked List (Easy)

從LeetCode學演算法 - 74 Linked List (8)
0234. Palindrome Linked List (Easy)

從LeetCode學演算法 - 75 Array (14)
0289. Game of Life (Medium)

從LeetCode學演算法 - 76 Hash Table (5)
0290. Word Pattern (Easy)

從LeetCode學演算法 - 77 String (2)
1071. Greatest Common Divisor of Strings (Easy)

從LeetCode學演算法 - 78 Two Pointer (4) / Binary Search(5)
0392. Is Subsequence (Easy)

從LeetCode學演算法 - 79 Hash Table (6)
0383. Ransom Note (Easy)

從LeetCode學演算法 - 80 Linked List (9)
0082. Remove Duplicates from Sorted List II (Medium)

從LeetCode學演算法 - 81 Backtracking (5) / DFS (7)
0093. Restore IP Addresses (Medium)

從LeetCode學演算法 - 82 Linked List (10)
0086. Partition List (Medium)

從LeetCode學演算法 - 83 Dynamic Programming (10)
0091. Decode Ways (Medium)

從LeetCode學演算法 - 84 Tree (11) / DFS (8)
0116. Populating Next Right Pointers in Each Node (Medium)

從LeetCode學演算法 - 85 String (3)
1332. Remove Palindromic Subsequences (Easy)

從LeetCode學演算法 - 86 Hash Table (7)
1331. Rank Transform of an Array (Easy)

從LeetCode學演算法 - 87 Bitwise Operation (6)
1342. Number of Steps to Reduce a Number to Zero (Easy)

從LeetCode學演算法 - 88 Hash Table (8)
0575. Distribute Candies (Easy)

從LeetCode學演算法 - 89 HashTable (9)
1346. Check If N and Its Double Exist (Easy)

從LeetCode學演算法 - 90 Dynamic Programming (11) / DFS (9)
0576. Out of Boundary Paths (Medium)

從LeetCode學演算法 - 91 String (4)
0678. Valid Parenthesis String (Medium)

從LeetCode學演算法 - 92 String (5)
0680. Valid Palindrome II (Easy)

從LeetCode學演算法 - 93 Tree (12) / DFS (9)
0687. Longest Univalue Path (Easy)

從LeetCode學演算法 - 94 Hash Table (10)
0438. Find All Anagrams in a String (Easy)

從LeetCode學演算法 - 95 Dynamic Programming (12)
1143. Longest Common Subsequence (Medium)

從LeetCode學演算法 - 96 BST (5)
1008. Construct Binary Search Tree from Preorder Traversal (Medium)

從LeetCode學演算法 - 97 Dynamic Programming (13)
0368. Largest Divisible Subset (Medium)

從LeetCode學演算法 - 98 Tree (13) / DFS (10)
0129. Sum Root to Leaf Numbers (Medium)

從LeetCode學演算法 - 99 Tree (14) / DFS (11)
0404. Sum of Left Leaves (Easy)

從LeetCode學演算法 - 100 Dynamic Programming (14)
1510. Stone Game IV (Hard)

從LeetCode學演算法 - 101 String (6)
1529. Bulb Switcher IV (Medium)

從LeetCode學演算法 - 102 Tree (15) / DFS (12)
1530. Number of Good Leaf Nodes Pairs (Medium)

從LeetCode學演算法 - 103 Tree (16) / DFS (13) / BFS (3) / Queue (4)
0112. Path Sum (Easy)

從LeetCode學演算法 - 104 Tree (17) / DFS (14) / Backtracking (6)
0113. Path Sum II (Medium)

從LeetCode學演算法 - 105 Tree (18) / DFS (15) / Backtracking (7)
0437. Path Sum III (Medium)

從LeetCode學演算法 - 106 Tree (19) / DFS (16)
0563. Binary Tree Tilt (Easy)

從LeetCode學演算法 - 107 String (7) / Stack (2)
1544. Make The String Great (Easy)

從LeetCode學演算法 - 108 Tree (20) / DFS (17)
1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree (Medium)

從LeetCode學演算法 - 109 Array (15) / Hash Table (11)
1640. Check Array Formation Through Concatenation (Easy)

從LeetCode學演算法 - 110 Array (16) / Greedy Algorithm (1)
0881. Boats to Save People (Medium)

從LeetCode學演算法 - 111 DFS (18) / Backtracking (8)
0784. Letter Case Permutation (Medium)

從LeetCode學演算法 - 112 Binary Search (6) / Newton’s Method
0367. Valid Perfect Square (Easy)

從LeetCode學演算法 - 113 BFS (4) / Queue (5)
1091. Shortest Path in Binary Matrix (Medium)

從LeetCode學演算法 - 114 Stack (3)
0946. Validate Stack Sequences (Medium)

從LeetCode學演算法 - 115 Graph(1) / Union Find (1)
0684. Redundant Connection (Medium)

從LeetCode學演算法 - 116 Tree (21) / DFS (19)
0814. Binary Tree Pruning (Medium)

從LeetCode學演算法 - 117 Array (17)
0941. Valid Mountain Array (Easy)

從LeetCode學演算法 - 118 DFS (20) /BFS (5) / Queue (6)
0934. Shortest Bridge (Medium)

從LeetCode學演算法 - 119 Graph (2) / DFS (21)
0797. All Paths From Source to Target (Medium)

從LeetCode學演算法-120 (0547. Number of Provinces)
Categories: Graph/Union Find, Level: Medium
English Version: https://desolve.medium.com/51a78df0670c

從LeetCode學演算法-121 (0802. Find Eventual Safe States)
Categories: Graph/DFS, Level: Medium
English Version: https://desolve.medium.com/b3b88410d561