從LeetCode學演算法

# 從LeetCode學演算法 Chihyu Lin  Slide: https://hackmd.io/@Desolve/SJi7bBjXH --- We will have some practices on LeetCode. Please prepare your laptop and register LeetCode account first. --- ## Who am I? - Senior Software Engineer at ASUS (2013.03-2019.07) - AI Engineer at Libgirl (Now) - Have a cat :cat: - Write a series of [從LeetCode學演算法](https://medium.com/@desolution/%E5%BE%9Eleetcode%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-0-6c121bd8b579) to share algorithms from LeetCode --- ## Introduction --- ### Why do we need to learn algorithms? - 你/妳有以下的「症頭」嗎? -- 明明有準備，面對白板腦袋卻一片空白？ -- 題目類型好眼熟，但我該從哪裡開始下手QQ -- 明明說是問經歷怎麼開始問演算法？ - 所有程式類面試幾乎都會問白板題 - 而白板題的重點就在於演算法 -- 就像數學學會公式一樣 -- 練習的題目多了，套公式就能得心應手！ --- ### Why LeetCode? - 其實有很多可以練習Coding的網站 -- HackerRank -> 熟悉語言，題目較長 -- CodeWar -> 偏向打怪升級 - LeetCode的編號較明確，每個題目的討論區也很踴躍 -- Easy難度寫過一輪 -- 搭配少量Medium和Hard，足以應付絕大多數的白板題 - Don't fail at interviews first, then realize the whiteboard part is important. --- ### How to practice? - 自己先嘗試兜出解法 - 能力範圍內盡力提升這個解法的執行速度 - 真的不行或卡超過半小時才參考別人的解答 - 練習到一定程度後即可將注意力集中在目標相關的領域 --- ### Before we start, something you need to know - Time/Space Complexity (時間/空間複雜度) -- 使用O()表示法 (Big-O) -- 只考慮最高項 -- 通常會假設輸入的長度為N，其耗費的時間/空間複雜度來表示 -- 來嘗試看看一些例子吧！ -- 註: 下面的範例均假定N大於0 --- - 請問下列程式碼的時間複雜度為何？ ``` Python def forLoop(N): sum = 0 for i in range(N): sum += i*i return sum ``` --- - 請問下列程式碼的時間複雜度為何？ ``` Python def forLoop(N): sum = 0 for i in range(N): if i > 5: break else: sum += i*i return sum ``` --- - 請問下列程式碼的時間複雜度為何？ ``` Python def nestedForLoop(N): sum = 0 for i in range(N): for j in range(i, N): sum += i * j return sum ``` --- ### Let's start! - https://leetcode.com/ - Remember to login/register first - Let's go for first example: [0001 Two Sum](https://leetcode.com/problems/two-sum/) --- ## Examples --- ### Example 1: [0001. Two Sum (Easy)](https://leetcode.com/problems/two-sum/) (Dictionary/HashMap) --- ![](https://i.imgur.com/9xq86I8.png) --- - Brute Force: O(N^2) -- 每次固定一個值 -- 拿其他的值和它相加，檢查結果 --- - Dictionary/HashMap -- key, value兩兩相對 -- 單一key值只會對應到一個value --- - Using Dictionary -- 檢查key值: O(1) -- 將值放入: O(1) -- 最多放入N-1對 -> 所以總複雜度為O(N) --- - Problem Solving -- 依序檢查target-nums[i]有沒有在dict中 -- 有的話取出對應indices回傳 -- 沒有的話將(nums[i], i)放進dict裡 --- - Try it! --- {%gist Desolve/e936fe7cbad8aa7810eeffacebadda41%} --- - 備註: -- dict.__ contains __的寫法，也可以改用key in dict的方式 - 思考一下 -- 如果題目要求找出所有的解呢？ --- ### Example 2: [0035. Search Insert Position](https://leetcode.com/problems/search-insert-position/) (Binary Search) --- ![](https://i.imgur.com/08qtrJs.png) --- - Brute Force: O(N) -- 從頭開始找，當target比nums[i]大就繼續往下 -- 當target比nums[i]小就進行回傳 -- 當target和nums[i]相等也進行回傳 -- 如果走到尾端的話，代表應該插入在尾端 --- - Binary Search(二元搜尋法) -- 利用陣列已排序的特性 -- 將邊界設定成lo = 0, up = l-1 (l是nums的長度) -- 先取中間點mi=(lo+up)//2，比較nums[mi]和target的大小 -- 若兩者相等 -> 找到正確值了，回傳mi --- - Binary Search(二元搜尋法) -- 若nums[mi] > target -> 表示目標應該在lo和mi之間(不含mi) -- 若nums[mi] < target -> 表示目標應該在mi和up之間(不含mi) -- 反覆調整直到相等或兩者交錯(此時插入的位置應在lo處) -- 每次都要將lo或up其中之一更新，從而改變mi --- - Try it! --- {%gist Desolve/97cea741906acfed250c644a263524df%} --- - 思考一下 -- 時間複雜度是多少呢？ - (相似題: [0704. Binary Search(Easy)](https://leetcode.com/problems/binary-search/)) --- ### Example 3: [0100. Same Tree (Easy)](https://leetcode.com/problems/same-tree/) (Binary Tree) --- ![](https://i.imgur.com/vMjMz4F.png) --- - Binary Tree (二元樹) -- root/left/right node -- NIL(None/null) -- Each node contains a value -- Each node has its left node and right node - 兩棵樹相同? -- 結構一樣(沒有多長，也沒有少長) -- 相同位置的值也一樣 --- - 遞迴(recursion) -- 透過不斷呼叫相同的函式，將問題化簡最終得到答案的方法。 -- 要有確定狀況的條件及前後連結的關係 -- 例如: n+(n-1)+(n-2)+...+1? ``` Python def sumN(n): if n == 1: # 確定狀況的條件，不然會一直往下減下去 return 1 else: return n + sumN(n-1) ``` --- - 對一棵二元樹而言 -- 左節點及其下面的所有節點可構成一棵二元樹 -- 同理右節點也可以構成一棵二元樹 - 比較兩棵二元樹是否相等，等同於比較： 1. root是否同時存在或同時不存在，同時存在的話，值必須相等 2. 同時存在且值相等的話，其左子樹和右子樹再各自進行比較 3. 左右子樹也都分別相等的話，則二棵二元樹相等 --- - Try it! ``` Python # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None ``` --- {%gist Desolve/47039932c601895037c316bc7bec1842%} --- - 思考一下 -- 時間複雜度是多少呢？ -- 如果換成想檢查兩棵樹是否互相為彼此的鏡像該怎麼解? - (相似題: [0101. Symmetric Tree](https://leetcode.com/problems/symmetric-tree/)) --- ### Example 4: [0070. Climbing Stairs (Easy)](https://leetcode.com/problems/climbing-stairs/) (Dynamic Programming) --- ![](https://i.imgur.com/VwNnUKx.png) --- - 動態規劃 (Dynamic Programming) -- 目標不容易直接透過簡單計算處理 -- 但走到第n階的結果，可能可以用走到n-1, n-2階的結果來表達 -- 且第1階/第2階的結果可以直接得到 -- 透過迴圈一路走上來 --- - 走到第1階的方法數？ 1種 (0->1) - 走到第2階的方法數？ 2種 (0->1->2 or 0->2) - 走到第n階的方法數？等於走到第n-2階的方法數+走到第n-1階的方法數 --- - Try it! --- {%gist Desolve/36f7e5bd29cd65347e68e9617b6c8b30%} --- - 思考一下 -- 時間複雜度是多少呢？ -- 它的結果其實跟一個很著名的數列一致XD --- ### Example 5: [0198. House Robber (Easy)](https://leetcode.com/problems/house-robber/) (Dynamic Programming) --- ![](https://i.imgur.com/7O8pIyF.png) --- - 相鄰房子不能被偷 -- 要偷第i-1棟房子的話，就不能偷第i棟 -- 如果設定偷到第i棟的最大收益是rob[i]的話 -- rob[i], rob[i-1], rob[i-2], nums[i]之間有何關係？ --- - 兩個狀況選其一時，按題目條件要取比較大的 -- rob[i] = max(nums[i] + rob[i-2], rob[i-1]) - 起始條件？ -- rob[0] = nums[0] -- rob[1] = ? --- - Try it! --- {%gist Desolve/d83c7c68910e5e456a511e45fa32f743%} --- - 思考一下 -- 時間複雜度是多少呢？空間複雜度又是多少？ -- 空間複雜度能化簡嗎？ -- 如果今天房子被建造成圓形分布，也就是第一棟跟最後一棟相鄰呢？ - (延伸題: [0213. House Robber II](https://leetcode.com/problems/house-robber-ii/)) --- ### Wrap up - Practice your coding basic skill first - Try to solve problems and understand the algorithm you use - Don't be afraid of asking - Polish up your domain skill - Happy coding! --- ### Thank you! :tada: - You can find me on -- [Medium](https://medium.com/@desolution) -- [Python Taiwan](https://www.facebook.com/groups/pythontw/) (I'll share my articles there) -- or [email me](mailto:fp60403+happy.coding@gmail.com) - If you're interested in MLOps solution for AI -- Come and try our platform [dong](https://dong.libgirl.com/)! - Q&A