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  

Python的資料夾比較

最近在寫讓自己合code愈來愈省時間的小工具，畢竟我不是一個非常細心的人，常常會漏東漏西，每漏一次就會覺得自己更是應該早點把這個東西弄出來。（握拳）

要合併程式碼就一定會有廠商來的A跟自己改過的A+還有廠商來的新版B三個資料夾。
這時候就會覺得python的dircmp很好用，在這邊可以看到最下方有這幾行範例讓程式去子資料夾然後顯示出檔案跟路徑。

>>> from filecmp import dircmp
>>> def print_diff_files(dcmp):
...     for name in dcmp.diff_files:
...         print "diff_file %s found in %s and %s" % (name, dcmp.left,
...               dcmp.right)
...     for sub_dcmp in dcmp.subdirs.values():
...         print_diff_files(sub_dcmp)
...
>>> dcmp = dircmp('dir1', 'dir2') 
>>> print_diff_files(dcmp) 

像我這種腦袋不好的人最討厭看到遞迴了，到底是要怎麼把找到的檔案跟路徑傳出來讓我找資料找了好一陣子。因為傳值就會扯上call by value，call by reference有的沒的問題。

用谷歌搜尋call by reference python可以看到這位大大的部落格是第二個搜尋結果！

所以我就研究了一下，這篇提到了Immutable Object and Mutable Object （不變物件與可變物件），但說實在裡面的範例我看得不是很懂，所以自己寫了程式碼看看結果。

 def LOL(mutable, immutable):  
   print  
   print "LOL start"  
   print "mutable id in LOL is %s"%(id(mutable))  
   print "immutable id in LOL is %s"%(id(immutable))  
   
   mutable.append('xyz')  
   print "mutable modifed in LOL is ",  
   print mutable  
   print "mutable id in LOL is %s"%(id(mutable))  
   
   immutable += 1  
   print "immutable plus 1 in LOL is %s"%(immutable)  
   print "immutable id in LOL is %s"%(id(immutable))  
   
   mutable = ['MMM']  
   print "mutable assigned in LOL is ",  
   print mutable  
   print "mutable id in LOL is %s"%(id(mutable))  
   
   imumutable = 5  
   print "immutable assigned by 5 in LOL is %s"%(immutable)  
   print "immutable id in LOL is %s"%(id(immutable))  
   print "LOL end"  
   print  
   
 mutable = ['abc']  
 immutable = 0  
 print "mutable id is %s"%(id(mutable))  
 print "immutable id is %s"%(id(immutable))  
   
 LOL(mutable, immutable)  
   
 print "mutable id is %s"%(id(mutable))  
 print "immutable id is %s"%(id(immutable))  
 print "mutable is ",  
 print mutable  
 print "immutable is %s"%(immutable)

基本上就是numbers, booleans, strings, tuples, frozensets這五種型態的變數都是不變物件，其餘的資料型態都是可變物件，而自己建立的類別（class）為可變物件。（參考這邊）

跑出來的結果在這邊：

 mutable id is 139901048634112  
 immutable id is 21690320  
   
 LOL start  
 mutable id in LOL is 139901048634112  
 immutable id in LOL is 21690320  
 mutable modifed in LOL is ['abc', 'xyz']
 mutable id in LOL is 139901048634112    ->可變物件傳進函式之後可做運算，但物件不變
 immutable plus 1 in LOL is 1  
 immutable id in LOL is 21690296         ->不可變物件傳進函式之後可做運算，並且物件改變
 mutable assigned in LOL is ['MMM']
 mutable id in LOL is 139901048690160    ->可變物件傳進函式之後被賦值後為新物件
 immutable assigned by 5 in LOL is 1  
 immutable id in LOL is 21690296         ->不可變物件傳進函式之後不可被賦值
 LOL end  
   
 mutable id is 139901048634112  
 immutable id is 21690320  
 mutable is ['abc', 'xyz']               ->可變物件在函式中的運算會直接影響該物件
 immutable is 0                          ->不可變物件在函式中的運算不會影響該物件

從上面的執行結果（可變物件傳進函式之後可做運算，但物件不變）拿來運用在一開始的資料夾遞迴比較上，我們可以丟一個串列（list）進去存找到的檔案以及左右路徑，即可拿到我們要的結果。

 from filecmp import dircmp  
   
 def print_diff_files(dcmp, result):  
   for name in dcmp.diff_files:  
     print "diff_file %s found in %s and %s" % (name, dcmp.left, dcmp.right)  
     temp = [name, dcmp.left, dcmp.right]  
     result.append(temp)  
   for sub_dcmp in dcmp.subdirs.values():  
     print_diff_files(sub_dcmp)  
   
 result = []  
 dcmp = dircmp('dir1', 'dir2')   
 print_diff_files(dcmp, result)   

是不是很簡單呢？（才怪）

Python Class錯誤的init

今天試寫了Python的類別功能，但跑出來的結果有些問題。

 class Test:  
    def __init__(self, path):  
      Test.data = os.path.join(path, 'data')  
   
 def Function:  
    A = Test('/home/gg/a/')  
    B = Test('/home/gg/b/')  
    C = Test('/home/gg/c/')  
    print A.data  
    print B.data  
    print C.data  

這樣寫的話執行Function結果如下

 /home/gg/c/data  
 /home/gg/c/data  
 /home/gg/c/data  

想了一下子才發現應該要這樣寫才對

 class Test:  
    def __init__(self, path):  
      self.data = os.path.join(path, 'data')  

這樣才會正確的印出

 /home/gg/a/data  
 /home/gg/b/data  
 /home/gg/c/data  

超不專業的我Orz