先做Easy級別的題目吧~（由于剛開始刷還沒規(guī)劃好递鹉，這篇里面先夾雜了兩道中等難度的題）
1-兩數(shù)之和
要求
給定一個整數(shù)數(shù)組 nums 和一個目標(biāo)值 target啼止，請你在該數(shù)組中找出和為目標(biāo)值的 兩個 整數(shù)门岔。
你可以假設(shè)每種輸入只會對應(yīng)一個答案羞延。但是横辆，你不能重復(fù)利用這個數(shù)組中同樣的元素各墨。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
分析
最笨辦法是O(n^2)，可以借助哈希表（字典）進(jìn)行優(yōu)化瘩绒。遍歷一遍元素猴抹，并將元素的值作為key下標(biāo)作為value插入哈希表中。注意锁荔，遍歷的同時蟀给，對于當(dāng)前元素，拿目標(biāo)值減去當(dāng)前值阳堕，然后去哈希表里找是否存在跋理，如果存在則說明找到了一對兒，直接返回即可恬总。
代碼
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
mem = {}
for index, val in enumerate(nums):
if (target - val) in mem.keys():
return [mem[target-val], index]
mem[val] = index
return []
2-兩數(shù)相加 （中等難度）
題目
給出兩個 非空 的鏈表用來表示兩個非負(fù)的整數(shù)薪介。其中，它們各自的位數(shù)是按照 逆序 的方式存儲的越驻，并且它們的每個節(jié)點只能存儲 一位 數(shù)字汁政。
如果，我們將這兩個數(shù)相加起來缀旁，則會返回一個新的鏈表來表示它們的和记劈。
您可以假設(shè)除了數(shù)字 0 之外，這兩個數(shù)都不會以 0 開頭并巍。
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807
思路
兩個鏈表一起讀取目木，相加進(jìn)位。這個題難點在于有很多特殊情況懊渡，不容易考慮周全刽射。
比如以下特殊用例
[5] # 需要考慮進(jìn)位
[5]
[9,8] # 需要考慮長度不均等
[1]
[1] # 需要考慮長度不均等和進(jìn)位
[9,9]
代碼
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
head = ListNode(0)
head.next = l1
carry = 0
while l1 and l2: # 兩個列表長度相同的部分
s = l1.val + l2.val + carry
val, carry = s % 10, s // 10
l1.val = val
prev, l1, l2 = l1, l1.next, l2.next
l = l1 or l2 # 處理l1或l2余下的部分
prev.next = l
while l and carry:
s = l.val + carry
val, carry = s%10, s//10
l.val = val
prev, l = l, l.next
if carry: # 最后千萬記得要處理進(jìn)位
prev.next = ListNode(1)
return head.next
3-無重復(fù)字符的最長子串 （中等難度）
問題
給定一個字符串军拟，請你找出其中不含有重復(fù)字符的 最長子串 的長度。
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是 "abc"誓禁，所以其長度為 3懈息。
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因為無重復(fù)字符的最長子串是 "b"，所以其長度為 1摹恰。
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因為無重復(fù)字符的最長子串是 "wke"辫继，所以其長度為 3。
請注意俗慈，你的答案必須是 子串 的長度姑宽，"pwke" 是一個子序列，不是子串闺阱。
思路
滑動窗口來解決炮车，左右兩個索引ij，用哈希表記錄當(dāng)前窗口中的元素酣溃。當(dāng)讀到j(luò)時如果不重復(fù)示血，則j繼續(xù)讀，如果重復(fù)救拉，則記下窗口的長度，然后從哈希表中讀取重復(fù)元素所在的位置瘫拣，并將i移動到它的下一個位置亿絮，繼續(xù)滑動窗口，最后得到最長的長度麸拄。
代碼
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
ans = 0
mem = {}
i = 0
for j in range(0, len(s)):
if s[j] in mem.keys():
i = max(mem[s[j]], i)
ans = max(ans, j - i + 1)
mem[s[j]] = j + 1
return ans
上面是參照官方解答寫的python代碼派昧，非常簡潔。而且本來我認(rèn)為當(dāng)遇到重復(fù)值之后拢切，挪動i之后應(yīng)該清空mem蒂萎，mem只記住當(dāng)前窗口中出現(xiàn)的元素，但這個代碼里面并沒有清空mem淮椰，而是接著用了mem五慈，玄機在于 i = max(mem[s[j]], i)這句，這句實現(xiàn)了：如果當(dāng)前元素出現(xiàn)在mem中主穗，并不意味著在當(dāng)前窗口中一定遇到重復(fù)值泻拦，而是判斷一下，如果重復(fù)元素的位置小于i則不是當(dāng)前窗口中出現(xiàn)了重復(fù)值忽媒，不更新i争拐，如果大于i則是出現(xiàn)了重復(fù)值，更新i晦雨。
寥寥幾句就把很多情況和判斷都給涵蓋了架曹，真是簡潔啊隘冲。
7-整數(shù)反轉(zhuǎn)
問題
給出一個 32 位的有符號整數(shù)，你需要將這個整數(shù)中每位上的數(shù)字進(jìn)行反轉(zhuǎn)绑雄。
示例 1:
輸入: 123
輸出: 321
示例 2:
輸入: -123
輸出: -321
示例 3:
輸入: 120
輸出: 21
注意:
假設(shè)我們的環(huán)境只能存儲得下 32 位的有符號整數(shù)展辞，則其數(shù)值范圍為 [?231, 231 ? 1]。請根據(jù)這個假設(shè)绳慎，如果反轉(zhuǎn)后整數(shù)溢出那么就返回 0纵竖。
思路
可以借助棧，123 % 10 = 3杏愤， 12 % 10 = 2靡砌， 1 % 10 = 1， 然后彈棧珊楼， 1 x 1 = 1通殃， 1 + 2 x 10 = 21， 21 + 3 x 100 = 321厕宗，完成計算画舌。
其實也可以在不借助棧的情況下完成，先彈出 123 % 10 = 3已慢， 123 // 10 = 12曲聂，將3存放到另一個數(shù)字變量ans中。然后 12 % 10 = 2, 12 // 10 = 1佑惠，對于ans朋腋，有 3 * 10 + 2 = 32。繼續(xù)膜楷，1 % 10 = 1, 1 // 10 = 0旭咽，對于ans有 32 * 10 + 1 = 321。不借助外部存儲完成了反轉(zhuǎn)赌厅。
代碼
class Solution:
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
minus = 1
if x < 0:
minus = -1
x *= minus
ans = 0
while x != 0:
pop = x % 10
x = x // 10
ans = ans * 10 + pop
ans *= minus
# 由于leetcode要求溢出時返回0穷绵，而python寫的時候該溢出的用例未溢出，所以判斷一下溢出
if - 2 ** 31 < ans < 2 ** 31 - 1:
return ans
else:
return 0
9- 回文數(shù)
問題
判斷一個整數(shù)是否是回文數(shù)特愿≈倌回文數(shù)是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數(shù)。
例如揍障， 121 是回文數(shù)宗收， -121 不是回文數(shù)， 10 不是回文數(shù)亚兄。
思路
轉(zhuǎn)為字符串混稽，兩端讀取判斷是否回文。
不轉(zhuǎn)為字符串的話，就通過除10和取余將數(shù)字反轉(zhuǎn)匈勋，然后判斷反轉(zhuǎn)前后的兩個整數(shù)是否相等礼旅。
優(yōu)化：例如，1221洽洁，是否可以加快速度呢痘系？其實只要將后一半數(shù)字反轉(zhuǎn)，與剩下的前一半數(shù)字比較饿自，即可判斷是否回文汰翠。(這個只反轉(zhuǎn)一半的代碼略)
代碼
轉(zhuǎn)換為字符串的解法：
class Solution:
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
if x < 0:
return False
data = str(x)
i, j = 0, len(data) - 1
while i < j:
if data[i] != data[j]:
return False
i += 1
j -= 1
return True
巧妙利用 python 語法：
class Solution:
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
if x >= 0 and str(x) == str(x)[::-1]:
a = True
else :
a = False
return a
反轉(zhuǎn)整個數(shù)字的解法：
class Solution:
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
if x < 0:
return False
remainder = x % 10
devision = x // 10
reverse = remainder
while devision != 0:
remainder = devision % 10
devision = devision // 10
reverse = reverse * 10 + remainder
return x == reverse
13-羅馬數(shù)字轉(zhuǎn)整數(shù)
問題
羅馬數(shù)字包含以下七種字符: I， V昭雌， X复唤， L，C烛卧，D 和 M佛纫。
字符 數(shù)值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 羅馬數(shù)字 2 寫做 II 总放，即為兩個并列的 1呈宇。12 寫做 XII ，即為 X + II 局雄。 27 寫做 XXVII, 即為 XX + V + II 甥啄。
通常情況下，羅馬數(shù)字中小的數(shù)字在大的數(shù)字的右邊炬搭。但也存在特例蜈漓，例如 4 不寫做 IIII，而是 IV尚蝌。數(shù)字 1 在數(shù)字 5 的左邊，所表示的數(shù)等于大數(shù) 5 減小數(shù) 1 得到的數(shù)值 4 充尉。同樣地飘言，數(shù)字 9 表示為 IX。這個特殊的規(guī)則只適用于以下六種情況：
I 可以放在 V (5) 和 X (10) 的左邊驼侠，來表示 4 和 9姿鸿。
X 可以放在 L (50) 和 C (100) 的左邊，來表示 40 和 90倒源。
C 可以放在 D (500) 和 M (1000) 的左邊苛预，來表示 400 和 900。
給定一個羅馬數(shù)字笋熬，將其轉(zhuǎn)換成整數(shù)热某。輸入確保在 1 到 3999 的范圍內(nèi)。
示例 1:
輸入: "III"
輸出: 3
示例 2:
輸入: "IV"
輸出: 4
示例 3:
輸入: "IX"
輸出: 9
示例 4:
輸入: "LVIII"
輸出: 58
解釋: L = 50, V= 5, III = 3.
示例 5:
輸入: "MCMXCIV"
輸出: 1994
解釋: M = 1000, CM = 900, XC = 90, IV = 4.
思路
最主要是想清楚思路，不要陷入很多if else里面昔馋。
建立一個字符和值的對應(yīng)筹吐，從左往右讀取，如果當(dāng)前字符代表的數(shù)字比下一個字符的大秘遏，則在總結(jié)果里加上丘薛，如果小，則減去邦危。
上面思路雖然看起簡單洋侨，在本題的前提下——輸入的羅馬數(shù)字一定是正確的——是沒有問題的。
代碼
class Solution:
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
num = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000,
}
score = 0
for i in range(0, len(s)):
if i < len(s) - 1 and num[s[i+1]] > num[s[i]]:
score -= num[s[i]]
else:
score += num[s[i]]
return score
14- 最長公共前綴
問題
編寫一個函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴倦蚪。
如果不存在公共前綴希坚，返回空字符串 ""。
示例 1:
輸入: ["flower","flow","flight"]
輸出: "fl"
示例 2:
輸入: ["dog","racecar","car"]
輸出: ""
解釋: 輸入不存在公共前綴审丘。
說明:
所有輸入只包含小寫字母 a-z 吏够。
思路
縱向掃描：從下標(biāo)0開始，判斷每一個字符串的下標(biāo)0滩报，判斷是否全部相同锅知。直到遇到不全部相同的下標(biāo)。時間性能為O(n*m)脓钾。
橫向掃描：前兩個字符串找公共子串碗降，將其結(jié)果和第三個字符串找公共子串……直到最后一個串。時間性能為O(n*m)捞慌。
借助trie字典樹甘凭。將這些字符串存儲到trie樹中。那么trie樹的第一個分叉口之前的單分支樹的就是所求握截。（這個思路也挺好的飞崖，而且用到了高級一點的方法）
代碼
# 縱向掃描
class Solution:
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if not strs:
return ''
if len(strs) == 1:
return strs[0]
cursor = -1
ok = True
while ok:
cursor += 1
if cursor == len(strs[0]): # 首個串已走完
cursor -= 1
break
current_char = strs[0][cursor]
for st in strs[1:]:
if cursor == len(st) or st[cursor] != current_char: # 串走完或不匹配
cursor -= 1
ok = False
break
return strs[0][:cursor+1]
