8. String to Integer (atoi)
-
ls = list(str.strip())先去除字符串兩端的空格荧飞，并把它存放到數組里。 - 檢查字符串首位是正號還是負號搭综，檢查完并給sign賦值后垢箕，將字符串首位刪掉
- 初始化res和循環(huán)變量i，
while i<len(ls) and ls[i].isdigit(), 注意判斷的條件兑巾。判斷的是數組的長度条获，已經不再是字符串的長度了。還有就是要對數組每一位判斷是否為數字蒋歌。
-res = res*10 + ord(ls[i]) - ord('0') - return
max(-2**31, min(2**31-1, res*sign))這里是注意數組越界情況
12. Integer to Roman
運用/和%運算來取得四位數的第1,2,3,4個數字帅掘，然后將這個數字作為索引去相應的list里找羅馬數字。
羅馬數字個位數：Q = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
十位數：W = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
百位數：E = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
千位數： R = ["", "M", "MM", "MMM"]
注意第一個元素應該是空堂油，這樣可以使下標與數字對應起來修档。
13. Roman to Integer
初始化一個dict，里邊存放所有的羅馬字符和他們相對應的數字：
roman = {'M':1000, 'D':500, 'C':100, 'L':50, 'X':10, 'V':5, 'I':1}
羅馬數字的計算規(guī)則：
- 相同的數字連寫府框，所表示的數等于這些數字相加得到的數吱窝，例如：III = 3
- 小的數字在大的數字右邊，所表示的數等于這些數字相加得到的數，例如：VIII = 8
- 小的數字院峡，限于（I兴使、X和C）在大的數字左邊，所表示的數等于大數減去小數所得的數照激，例如：IV = 4
- 正常使用時发魄，連續(xù)的數字重復不得超過三次
- 在一個數的上面畫橫線，表示這個數擴大1000倍（本題只考慮3999以內的數俩垃，所以用不到這條規(guī)則）
python中string可以直接以List的形式訪問励幼。
所以當roman[s[i]] < roman[s[i+1]]時，就將res -= roman[s[i]]口柳，否則res += roman[s[i]], res初始化為0.
**需要注意的是苹粟，最后一個羅馬字符永遠是加上去的，不符合上述規(guī)律啄清，所有要返回return res + roman[s[-1]]
14. Longest Common Prefix
運行時間為O(m*n), m為字符串最小長度六水，n為字符串個數
找每個string的公共最長prefix，舉例說明：
- {"a","a","b"} should give "" as there is nothing common in all the 3 strings.
- {"a", "a"} should give "a" as a is longest common prefix in all the strings.
- {"abca", "abcd"} as abc
- {"ac", "ac", "a", "a"} as a.
先找出最短的string辣卒，以它作為標準掷贾。min()函數可以添加key = len屬性，來找到最短長度的元素: shortest = min(strs, key = len)
然后針對shortest中的每一個字符荣茫，檢查strs中的其他字符串相對應的位置是不是該字符想帅，若不是，則返回shortest[:i]啡莉，對shortest遍歷時用enumerate比較方便港准。最后若都存在，就返回shortest
17. Letter Combinations of a Phone Number
Iterative:
思路在于要維護一個last數組咧欣，存放針對當前未組合的一個string浅缸，已經組合好的上一組string集合。有點類似于backtracking.
所以last一開始是為空的魄咕，取得第一個字符對應的string后衩椒，將string里的每個字符與last數組里的每一個string進行連接，append到一個新的數組里哮兰。最后再將新的數組作為last進行下一輪循環(huán)毛萌。需要注意的是，為什么要存在這個中間數組喝滞，以及什么時候對它進行初始化阁将。
還是要想清楚這道題的思路，最后的結果數組右遭，也就是我們的last數組做盅，是在不斷被替換更新的缤削。它不可以直接append進新的字符串，因為老的字符串依然存在吹榴，但我們以及不需要了僻他。所以我們需要一個中間數組來存放新一輪的結果，每次循環(huán)結束再將它賦值給last腊尚。并且這個中間數組要每次外層循環(huán)都更新為空。
- 還有重要的一點就是满哪，注意字符連接順序婿斥。要使last中的字符再前，新加的字符在后哨鸭。
Recursive
backtracking思想民宿，不斷傳遞除了最后一個字符的數字符串進去，總會有某一次像鸡，傳進去的數字符串長度為1. 當數字符串長度為1時活鹰，返回list形式的相對應的string。
if len(digits)==1: return list(dic[digits[0]])
然后將數字符串最后一個數字符所對應的string取出來只估，最后將迭代的結果志群，和最后一個字符串對應的string相加。
last = self.letterCombinations(digits[:-1])
first = dic[digits[-1]]
return [ele + char for ele in last for char in first]
20. Valid Parentheses
- 先說一種比較投機取巧的方法蛔钙，用字符串中的replace函數锌云。
while '()' in s or '[]' in s or '{}' in s:
s = s.replace('()', '').replace('{}', '').replace('[]', '')
if len(s) == 0:
return True
else:
return False
- 另外一種方法用到了stack和hash，將右括號作為key吁脱，左括號作為value存到哈希表中桑涎。然后對s中的每個字符進行遍歷，如果char在value里
if char in dic.values()兼贡，就將這個char append到stack中攻冷，如果char在Keyif char in dic.keys()里，就從stack里Pop出來一個元素與char在dic里所對應的value比較遍希，如果不相等等曼，就證明Invalid。這里要注意pop之前應該先判斷stack是否為空孵班。最后返回stack是否為空可岂，因為每針對一個右括號，我們都會pop出來一個左括號棺蛛，所以最后stack是空的瓮增。
因為如果是valid的，我們就總是先遇到左括號虱饿，所以將左括號作為value拥诡，并加入到stack里触趴。 - 如果s的長度為奇數，就一定不是valid, 可以直接返回false渴肉，但注意當s長度為0時冗懦，我們認為他是valid的，返回true仇祭。
28. Implement strStr()
在一個字符串中找到另一個字符串第一次出現(xiàn)的位置披蕉。trick的點在于對大字符串進行for循環(huán)遍歷時，range的范圍是for i in range(len(str1) - len(str2) + 1):, 因為如果str2的長度是3乌奇，那在str1中就要3個3個的進行比較没讲，所以在str1只剩最后三個字符時就要停止比較，所以將len(str2)減去礁苗，加1是因為range取不到最后一位爬凑，為了取到，就多加上一個试伙。
if str1[i : i + len(str2)] == str2: return i 這就是上述3個3個的比較的實現(xiàn)嘁信，注意這里就不用再加1了。因為i + len(str2)本來就比實際長度多了一個疏叨。
22. Generate Parentheses
- 先對left,right,list初始化潘靖，
left, right, list = n, n, [] - 調用dfs函數，
self.dfs(left, right, list, '')考廉，最后一個空字符串是用來存放valid排列的 - 當左右都不存在的時候秘豹，將此時的string append到list里去，并且注意一定要返回昌粤！因為valid排列不只一個
- 如果沒有
if right < left: return, 就會出現(xiàn)很多‘)(’這種組合既绕，因為valid排列總是先左后右的，所以做這種檢查涮坐，不然就會先右后左 - 動態(tài)規(guī)劃解法：
https://discuss.leetcode.com/topic/28374/clean-python-dp-solution
38. Count and Say
題目說的實在是太不明白了凄贩。。袱讹。
解釋一下就是疲扎，輸入n，那么我就打出第n行的字符串捷雕。
怎么確定第n行字符串呢椒丧？他的這個是有規(guī)律的。
n = 1時救巷，打印一個1壶熏。
n = 2時，看n=1那一行浦译，念：1個1棒假，所以打铀葜啊：11。
n = 3時帽哑，看n=2那一行谜酒，念：2個1，所以打悠拚怼：21僻族。
n = 4時，看n=3那一行屡谐，念：一個2一個1鹰贵，所以打印：1211康嘉。
以此類推。(注意這里n是從1開始的）
所以構建當前行的字符串要依據上一行的字符串籽前⊥ふ洌“小陷阱就是跑完循環(huán)之后記得把最后一個字符也加上，因為之前只是計數而已枝哄∫蘩妫”
其實就是對上一個字符串進行統(tǒng)計計數，需要注意的地方有：
- 要將temp, pivot, count的初始化寫字for循環(huán)里邊挠锥，for循環(huán)總共循環(huán)n-1次众羡，因為當n=1時，res = '1'. temp應該定義為空字符串蓖租，而不是空數組
- 共兩個for循環(huán)粱侣，外層控制循環(huán)次數，內層控制遍歷統(tǒng)計上一個字符串的字符蓖宦。當
char != pivot時齐婴，我們已經完成了對char的計數，就將temp += str(count) + pivot添加到字符串里稠茂，并對pivot進行更新柠偶，同時將新的count設置為1. - 當內層for循環(huán)結束后，還要將統(tǒng)計結果再一次添加到temp中
temp += str(count) + pivot睬关，這是因為內層循環(huán)結束后最后一個字符還尚未添加進去 - 在每次內層循環(huán)結束后诱担，更新res
res = temp
43. Multiply Strings
- 先初始化一個用來存放結果數字的數組，數組的長度為
res = [0]*(len(num1) + len(num2)), 兩個數組相乘的位數是小于他們的位數之和的电爹，注意是位數之和蔫仙，而不是相加后的位數。 - 內層for循環(huán)結束后藐不，digit要減1匀哄，這是因為計算相乘時秦效，將分別相乘的和加起來時，是要向后錯位的涎嚼，自己在紙上寫一下計算過程就知道了阱州。
- 每次內層循環(huán)也要cur - 1，也是因為每單次計算結果時也是從后往前得出結果的
- for 循環(huán)時法梯，一定要是
for int1 in reversed(num1)苔货，reversed很重要，千萬不能忘 - 內層for循環(huán)立哑，在計算兩個數的真正成績夜惭，和進位數字的時候，一定要是'+='铛绰，
res[inner] += int(int1) * int(int2),
res[inner - 1] = res[inner] / 10. 相乘時不要忘了類型轉換 - 最后要將res數組前邊的0pop掉诈茧，然后當res數組不為空時，返回join結果捂掰，如果為空敢会，就返回‘0’
-
' '.join(map(str, res)): map(str, res)是將List數組中的每個元素轉換為str類型，并去掉list結構这嚣。' ' .join()就是將他們連接起來成為一個字符串
67. Add Binary
用到的和43題類似的方法鸥昏，初始化一個數組，然后一位一位的相加姐帚，最后將數組再轉換為字符串吏垮。需要注意幾個地方：
- 執(zhí)行完
a.zfill(l2)等語句之后，要將之后用到的len更新罐旗，不能再使用舊的lenth符號 - 相乘那道題用的是兩層for循環(huán)膳汪，這道題只需要一個while循環(huán)，因為相加是每位都對照的
- 最后也要檢查res數組在
res.pop(0)之后是否長度為0九秀，若為0 就直接返回‘0’旅敷， 若不為0，再用join, map方法將數組轉換為字符串輸出
71. Simplify Path
費了半天力氣颤霎，原來根本沒有理解透題意媳谁，因為對Unix的路徑含義不是很清楚。簡單來說就是友酱，.意味著當前文件夾晴音，..意味著parent folder
對于每一個塊（以‘/’作為分界）進行分析，如果遇到‘../’則表示要上一層缔杉，那么就是進行出棧操作锤躁，如果遇到‘./’則是停留當前，直接跳過或详，其他文件路徑則直接進棧即可
- 先將path以'/'字符進行split系羞，此時得到的是數組形式的結果郭计，然后對數組進行解析，將值為空或者為
.的元素去掉椒振。然后初始化一個空數組stack - 對數組中的每個元素進行遍歷昭伸，如果元素值為
..，就意味著要返回上一層澎迎，我們就從stack中pop出來一個元素庐杨，注意要檢查stack是否為空 - 若元素值不為
..，我們就將元素append到stack中夹供。 - 最后返回
'/' + '/'.join(stack), 不要忘了最頭端的'/'灵份， 并且再用'/'把stack中的元素連接起來
93. Restore IP Addresses
實現(xiàn)中需要一個判斷數字是否為合法ip地址的一項的函數，首先要在0-255之間哮洽，其次前面字符不能是0填渠。
