小李飛刀：刷題第三彈！
摘要：
刷題第三天
正式刷題第三天。
之前看了個說法，挺認可的。
就是不要太在意一天的能呈現的價值，但是要在意累計的價值。
之前很多時候我會對今天一天沒有完成的計劃而沮喪，事實上，演算法的實踐，統計學的學習這些都是需要時間去積累去吃透。
所以，持之以恆的學習更為重要。
現在的目...
刷題第三天
正式刷題第三天。
之前看了個說法，挺認可的。
就是不要太在意一天的能呈現的價值，但是要在意累計的價值。
之前很多時候我會對今天一天沒有完成的計劃而沮喪，事實上，演算法的實踐，統計學的學習這些都是需要時間去積累去吃透。
所以，持之以恆的學習更為重要。
現在的目標是每天2題，當適合的時候就提高每天的題量！
第一題
20. 有效的括號
難度：簡單
型別：堆疊
給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字串，判斷字串是否有效。
有效字串需滿足：
左括號必須用相同型別的右括號閉合。
左括號必須以正確的順序閉合。
注意空字串可被認為是有效字串。
我的解答程式碼：
class Solution:
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
dic = {'(':')',')':'(','{':'}','}':'{','[':']',']':'['}
if len(s) < 2:
return (len(s)==0)
stack.append(s[0])
for i in s[1:]:
if len(stack) == 0:
stack.append(i)
elif i != dic[stack[-1]]:
stack.append(i)
else:
stack.pop()
return (len(stack)==0)
用了堆疊的方法和字典的方法，字典查詢速度會比較快。
然後對比當前字元和對應的堆疊裡的最末字元對應的另一半。
錯誤的一次是因為沒有考慮空字串，當存在為 "" 的時候，結果應該為true。
相對而言效率還是是可以的。
本題主要關鍵點
- 使用dictionary地圖的方式，類似掃描來確認對應的關係。
第二題
66. 加一
難度：簡單
型別：??
給定一個由整陣列成的非空陣列所表示的非負整數，在該數的基礎上加一。
最高位數字存放在陣列的首位， 陣列中每個元素只儲存一個數字。
你可以假設除了整數 0 之外，這個整數不會以零開頭。
我的解題程式碼是：
class Solution: def plusOne(self, digits): """ :type digits: List[int] :rtype: List[int] """ a = -1 for i in digits[::-1]: if i != 9 : digits[a] = i+1 return digits else: digits[a] = 0 if (a + len(digits)) == 0: digits.insert(0,1) return digits a = a - 1
用的辦法比較土。
簡單來說就是逆序遍歷，因為十進位制下，逢9進位，所以我們逆向計算有存在9的情況。
emmm.....感覺這個方法也很適合用遞迴來做。
效率上居然還可以的，錯誤過一次，主要原因是因為在資料例子為 [9] 的時候，輸出結果應該為 [1,0] ，所以重新進行了調整。
本題主要關鍵點
insert(位置點，數值)
總結
很多python的方法其實都非常的便捷，簡單的程式碼就可以完成演算法的實現。
還是要多學習方法，比如今天的逆序遍歷，以及左側插入等。
實踐出真知，古人誠不我欺。