1. Two Sum
難度: Easy
思路：用空間復(fù)雜度換取時間復(fù)雜度，字典
#for循環(huán)，從i+1開始
for j in range(i+1, len(nums)): # 不要忘記加冒號
#可以直接返回數(shù)組，循環(huán)中執(zhí)行到return語句則跳出循環(huán)
return [i, j]
# enumerate() 函數(shù)用于將一個可遍歷的數(shù)據(jù)對象組合為一個索引序列，同時列出數(shù)據(jù)和數(shù)據(jù)下標(biāo)，一般用在 for 循環(huán)當(dāng)中。
for i, num in enumerate(nums):
#新建字典
look_up = {}
#給字典添加元素
look_up[num] = i #{num: i}
2. Add Two Numbers
難度: 中等
思路：使用遞歸，每次計算一位相加
# 如果l1為Falsely則執(zhí)行
if not l1:
# 將val1數(shù)組中的元素逆序合并成一個字符串
num1 = ''.join([str(i) for i in val1[::-1]])
#將字符串形式的數(shù)字相加，然后逆序組成新的字符串
tmp = str(int(num1) + int(num2))[::-1]
3. Longest Substring Without Repeating Characters
難度: Medium
猜想：從第一個字符開始計算它往后不重復(fù)相連字符的數(shù)量，更新這個最大值
思路：1. 貪婪算法; 2. slide window 全家桶
# 返回字典中指定鍵的值，如果值不在字典中返回默認(rèn)值-1。
maps.get(s[i], -1)
# 獲取最大值
max(a, b)
5. Longest Palindromic Substring
難度: Medium
猜想：找子字符串+回文的判定條件
思路：Manacher algorithm，馬拉車算法，時間復(fù)雜度為o（n）
# S = "abba", T = "^#a#b#b#a#$"
T = '#'.join('^{}$'.format(s))
class Solution:
#Manacher algorithm
def longestPalindrome(self, s):
# Transform S into T.
# For example, S = "abba", T = "^#a#b#b#a#$".
# ^ and $ signs are sentinels appended to each end to avoid bounds checking
T = '#'.join('^{}$'.format(s))
n = len(T)
P = [0] * n
C = R = 0
for i in range (1, n-1):
P[i] = (R > i) and min(R - i, P[2*C - i]) # equals to i' = C - (i-C)
# Attempt to expand palindrome centered at i
while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
P[i] += 1
# If palindrome centered at i expand past R,
# adjust center based on expanded palindrome.
if i + P[i] > R:
C, R = i, i + P[i]
# Find the maximum element in P.
maxLen, centerIndex = max((n, i) for i, n in enumerate(P))
return s[(centerIndex - maxLen)//2: (centerIndex + maxLen)//2]
6. ZigZag Conversion
難度: 中等
思路：縱向思維考慮，index從0開始，我們要一直自增直到numRows-1，此后又一直自減到0，重復(fù)執(zhí)行。分別往4個子字符串里面添加字母，最后再合并成一個字符串
# 把列表合成字符串
''.join(res)
#創(chuàng)建n維空列表
res = [''] * numRows
7. Reverse Integer 反轉(zhuǎn)整數(shù)
難度: Easy
思路：取絕對值，逆序
# 除去這行文本的最后一個字符
line[:-1]
8. String to Integer (atoi)
難度: Medium
# 移除字符串頭尾指定的字符序列
str.strip()
# 返回對應(yīng)的 ASCII 數(shù)值，或者 Unicode 數(shù)值
ord()
11. Container With Most Water
難度: Medium
由于ai和aj (i<j) 組成的container的面積：S(i,j) = min(ai, aj) * (j-i)
當(dāng)height[left] < height[right]時，對任何left < j < right來說
1. min(height[left], height[j]) <= height[left] = min(height[left], height[right])
2. j - left < right - left
所以S(left, right) = min(height[left], height[right]) * (right-left) > S(left, j) = min(height[left], height[j]) * (j-left)
12. Integer to Roman
難度: Medium
# 第一個參數(shù)傳給第二個參數(shù)“鍵-鍵值”
# 第二個參數(shù)取出其中的鍵([0])或鍵值(1])
sorted(lookup.items(), key = lambda t: t[1])
15. 3Sum
難度: Medium
- 排序
- 固定左邊，如果左邊重復(fù)，繼續(xù)
- 左右弄邊界，去重，針對不同的左右邊界情況處理
# 給數(shù)組排序，升序
nums.sort()
sorted(nums)
16. 3Sum Closest
難度: Medium
float('inf') #浮點(diǎn)數(shù)最大值
abs() #python自帶的絕對值函數(shù)，不需要numpy
while i > 0 and nums[i] == nums[i-1]:
continue
# 錯誤操作
# 在while循環(huán)內(nèi)部必須要接能夠使#得條件不滿足的語句，不然會死循環(huán)
# 如果有continue，則該語句必須在continue前面
17. Letter Combinations of a Phone Number
難度: Medium
思路：定義一個迭代函數(shù)
## 字典中每一組鍵值對后面用逗號隔開
lookup = {
'2' : ['a', 'b', 'c'],
'3' : ['d', 'e', 'f'],
'4' : ['g', 'h', 'i'],
'5' : ['j', 'k', 'l'],
'6' : ['m', 'n', 'o'],
'7' : ['p', 'q', 'r', 's'],
'8' : ['t', 'u', 'v'],
'9' : ['w', 'x', 'y', 'z']
}
18. 4Sum
難度: Medium
思路： 迭代，可推廣至NSum問題
def findNsum(nums, target, N, result, results):
if len(nums) < N or N < 2 or target < nums[0]*N or target > nums[-1]*N: # early termination
return
if N == 2: # two pointers solve sorted 2-sum problem
l,r = 0,len(nums)-1
while l < r:
s = nums[l] + nums[r]
if s == target:
results.append(result + [nums[l], nums[r]])
l += 1
while l < r and nums[l] == nums[l-1]:
l += 1
elif s < target:
l += 1
else:
r -= 1
else: # recursively reduce N
for i in range(len(nums)-N+1):
if i == 0 or (i > 0 and nums[i-1] != nums[i]):
findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results) #往數(shù)組里面添加數(shù)組
results = []
findNsum(sorted(nums), target, 4, [], results)
return results
