LeetCode Algorithms Problems by Python

這兩天剛開始玩，重點是［Run］的時候只會給一組測試資料，［Submit Solution］會跑不只一組測試資料，所以沒考慮到所有的Case就會遇到［Run］沒問題，但［Submit Solution］卻一直過不了的情況。

這邊大概只會列一下重點，就是沒搞清楚會卡住的點。

1. Two Sum

用一個list來存找到兩個數的index。

2. Add Two Numbers

輸入會是兩個linked list，每個node的值會是非負的整數，把值相加之後取個位數，進位則加到下一個node的值裡。

 Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)  
 Output: 7 -> 0 -> 8  

所以第三個node的運算結果才會是8。

題目沒講的還有一點，就是如果輸入改為

 Input: (2 -> 4 -> 3) + (5 -> 6 -> 7)  

那輸出會是

 Output: 7 -> 0 -> 1 -> 1  

4+6進位1再加進3+7為11，要再取餘數，然後把進位存到下一個node裡。

小提示：要先建一個head = ListNode(0)，再進迴圈去把l1.val跟l2.val做運算存起來，所以回傳的時候是回傳head.next。

3. Longest Substring Without Repeating Characters

用for迴圈去產生字串然後做運算的話會很難寫，這個題目我是利用python的字典型態(dict type)去記錄已經遇過的英文字母。
最困難的部分應該是遇到重複的字母時該如何去重新計算目前字串的長度，我在這個部分卡了很久。

5. Longest Palindromic Substring

首先要知道什麼是迴文（Palindromic），簡單說就是從中間切開，頭尾對應位置的字相同的句子。

 aabaa  
 aabb  
 gabcbag  

像是上面三個例子，分為有中間字與無中間字的兩種類型。

這題真的是花了我很多時間也想了很久，我沒有使用動態規劃（dynamic programming），而是從頭以每個字母為中心向外延伸找出最大迴文。全部跑完會有超過時間的問題，所以我有加了一些判斷去縮減執行次數。因為寫不出來一次就能同時判斷有中間字跟無中間字所以我還爬了兩次字串，希望之後能想出只跑整個字串一次的寫法。

226. Invert Binary Tree

會開始寫LeetCode主要是看到這篇文章＂雖然我們公司 90%的工程師都用你開發的工具，但我們還是不聘用你＂，這件事告訴我們演算法是很重要的，就算你開發了很棒的軟體，演算法很差還是進不了Google！所以才出現了這個反轉二元數的題目。

用迴圈來做的話可以用root.pop(0)來一個一個取出node，把找到的左右node用root.append(node)加到queue裡面。
用遞迴來做就是一直往下層找，找到盡頭之後再回上一層去另一邊鑽然後把左右值交換。
兩種都會用得到下面這個運算，可以直接換值。

 root.right, root.left = root.left, root.right