- LeetCode刷题记录
- Array
- Primary
- #27 Remove Element
- #26 Remove Duplicates from Sorted Array
- #80 Remove Duplicates from Sorted Array II
- #189 Rotate Array
- #41 First Missing Positive
- #299 Bulls and Cows
- #134 Gas Station
- #274 H-Index
- #275 H-Index II
- #243 Shortest Word Distance
- #244 Shortest Word Distance II
- #245 Shortest Word Distance III
- #217 Contains Duplicate
- #55 Jump Game
- #45 Jump Game II
- #121 Best Time to Buy and Sell Stock
- #122 Best Time to Buy and Sell Stock II
- #123 Best Time to Buy and Sell Stock III
- #188 Best Time to Buy and Sell Stock IV
- #309 Best Time to Buy and Sell Stock with Cooldown
- #11 Container With Most Water
- #42 Trapping Rain Water
- #334 Increasing Triplet Subsequence
- #128 Longest Consecutive Sequence
- #164 Maximum Gap
- #287 Find the Duplicate Number
- Medium
- Counter
- Primary
- String
- Primary
- #28 Implement strStr()
- #14 Longest Common Prefix
- #58 Length of Last Word
- #387 First Unique Character in a String
- #383 Ransom Note
- #344 Reverse String
- #151 Reverse Words in a String
- #186 Reverse Words in a String II
- #345 Reverse Vowels of a String
- #205 Isomorphic Strings
- #293 Flip Game
- #294 Flip Game II
- #290 Word Pattern
- #242 Valid Anagram
- #49 Group Anagrams
- #249 Group Shifted Strings
- #87 Scramble String
- #179 Largest Number
- #6 ZigZag Conversion
- #161 One Edit Distance
- #38 Count and Say
- #358 Rearrange String k Distance Apart
- #316 Remove Duplicate Letters
- #271 Encode and Decode Strings
- #168 Excel Sheet Column Title
- #171 Excel Sheet Column Title
- #13 Roman to Integer
- #12 Integer to Roman
- #273 Integer to English Words
- #246 Strobogrammatic Number
- #247 Strobogrammatic Number II
- #248 Strobogrammatic Number III
- Medium
- Parentheses
- Primary
- Math
- Tree
- Linked List
- Dynamic Programming
- Array
按照网上给出的分类和刷题建议整理。
#27 Remove Element
# -*- coding: utf-8 -*-
def removeElement(nums,val):
#ERROR:修改遍历的列表
for x in nums[:]:
if x == val:
nums.remove(x)
return len(nums)容易出现的问题就是：
for x in nums:我们通常尽量避免修改一个正在进行遍历的列表，可以使用切片操作克隆这个list来避免这个问题（浅拷贝）
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
i = 0
while i+1 < len(nums):
if nums[i] == nums[i+1]:
nums.pop(i)
else:
i += 1
return len(nums)因为都是有序数列所以和上一题思路一样
def removeDuplicates(nums):
dupnums = [x for x in nums]
i = 0
for x in dupnums[:]:
if x in dupnums[i+2:]:
nums.remove(x)
i = i+1
if i == len(dupnums)-2:
return nums#189 Rotate Array
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
k = k % len(nums)
if k <= 0 or len(nums) <= 1:
return
nums.reverse()
nums[:k] = nums[k-1::-1]
nums[k:] = nums[:k-1:-1]要注意的是，reverse()不能反转部分数组，要想反转部分可以使用切片。
# O(NLogN)
def firstMissingPositive(self, nums: List[int]) -> int:
if not nums:
return 1
nums.sort()
res = 1
for i in nums:
if i > 0:
if i > res:
return res
if i == res:
res += 1
return res
# O(N)
def firstMissingPositive(self, nums: List[int]) -> int:
index = [0 for i in range(len(nums))]
for i in nums:
if i > 0 and i <= len(index):
index[i-1] += 1
for i in range(len(index)):
if index[i] == 0:
return i+1
return len(nums)+1#299 Bulls and Cows
def getHint2(secret,guess):
num_a = sum([i == j for (i, j) in zip(secret, guess)])
num_b = 0
if num_a == len(secret) - 1:
return str(num_a) + 'A' + str(num_b) + 'B'
count_s = collections.Counter(secret)
count_g = collections.Counter(guess)
num_a = sum([i == j for (i, j) in zip(secret, guess)])
for i in count_s:
num_b += min(count_s.get(i, 0), count_g.get(i, 0))
num_b -= num_a
return str(num_a) + 'A' + str(num_b) + 'B'在高票答案里发现了一个很pythonic的写法
from collections import Counter
def getHint(secret,guess):
'''
use Counter to count guess and secret and sum their overlap.
use zip to counter bulls
'''
s,g=Counter(secret),Counter(guess) #return a dict
bull = sum(i == j for i,j in zip(secret,guess))
cow = sum((s & g).values()) - bull
return '%sA%sB' %(bull,cow)
print(getHint1('1123','0111'))#134 Gas Station
def canCompleteCircuit(gas,cost):
remain = [i-j for i,j in zip(gas,cost)]
if sum(remain) < 0:
return -1
res = sum_remain = 0
for i in range(len(remain)):
sum_remain += remain[i]
if sum_remain < 0:
sum_remain = 0
res = i+1
return res内存占用更少的解法：
def canComplateCircuit1(gas,cost):
start,overall,accumulate = 0,0,0
for i in range(gas):
accumulate += gas[i]-cost[i]
overall += gas[i]-cost[i]
if accumulater < 0:
start,accumulate = i+1,0
return start if overall>0 else -1#274 H-Index
关于h指数的定义，先看了百度百科：
被引次数从高到低排列，直到某篇论文的序号大于该论文被引次数，那个序号减去1就是h
按照这个思路：
def hIndex(citaions):
citations = sorted(citations, reverse=True)
for index,num in enumerate(citations):
if index >= num:
return index
return len(citations)#275 H-Index II
与上一题一样，只是因为需要对数时间复杂度，因此用了二分查找，需要注意等号的位置
def hIndex(self, citations: List[int]) -> int:
small, big = 0, len(citations)-1
while small <= big:
res = (big + small) // 2
if len(citations) - res <= citations[res]:
big = res - 1
else:
small = res + 1
return len(citations) - small暴力求解
def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
index1, index2 = [], []
for i, word in enumerate(wordsDict):
if word == word1:
index1.append(i)
if word == word2:
index2.append(i)
res = len(wordsDict)
for i in index1:
res = min(min([abs(i-x) for x in index2]), res)
return resO(N) 解法
def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
index1 = index2 = -1
res = len(wordsDict)
for i, word in enumerate(wordsDict):
if word == word1:
index1 = i
if word2 == word:
index2 = i
if index1 >= 0 and index2 >= 0:
res = min(res, abs(index1 - index2))
return res与上一题相比，因为要处理多组数据，所以构造字典来提高运算速度，否则会有超时错误：
class WordDistance:
def __init__(self, wordsDict: List[str]):
self.wordsDict = wordsDict
self.locations = {}
for i,word in enumerate(wordsDict):
if word in self.locations:
self.locations[word].append(i)
else:
self.locations[word] = [i]
def shortest(self, word1: str, word2: str) -> int:
index1 = index2 = 0
location1 = self.locations[word1]
location2 = self.locations[word2]
res = len(self.wordsDict)
while index1 < len(location1) and index2 < len(location2):
res = min(res, abs(location1[index1] - location2[index2]))
if location1[index1] < location2[index2]:
index1 += 1
else:
index2 += 1
return res 但暴力解法的实际运算速度比上一种方法快，且节省内存：
class WordDistance:
def __init__(self, wordsDict: List[str]):
self.dict = defaultdict(list)
for i, word in enumerate(wordsDict):
self.dict[word].append(i)
def shortest(self, word1: str, word2: str) -> int:
return min(abs(p1 - p2) for p1 in self.dict[word1] for p2 in self.dict[word2])def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
res = len(wordsDict)
index1 = -1
if word1 == word2:
for i, word in enumerate(wordsDict):
if word == word1:
if index1 >= 0:
res = min(res, i - index1)
index1 = i
return res
index2 = -1
for i, word in enumerate(wordsDict):
if word == word1:
index1 = i
if word == word2:
index2 = i
if index1 >= 0 and index2 >= 0:
res = min(res, abs(index2-index1))
return res #217 Contains Duplicate
用Counter
def containsDuplicate(self, nums: List[int]) -> bool:
counts = collections.Counter(nums)
for i in counts:
if counts[i] > 1:
return True
return False看到一个很棒的解答：
def containDuplicate1(nums):
return len(set(nums)) != len(nums)#55 Jump Game
广度优先搜索BFS(breadth-first search) 适用于解决“最短路径问题”(shortest-path problem)。解决这类问题：
-
使用图来建立问题模型
-
使用广度优先搜索解决问题
广度优先搜索算法可帮助回答两类问题：
-
从节点A出发，有前往节点B的路径吗？
-
从节点A出发，前往节点B哪条路径最短？
这道题就是路径存在与否问题，可以依据当前最远到达距离与下一节点标号作对比。我一开始想得太过复杂了。
def canJump(self, nums: List[int]) -> bool:
max_length = nums[0]
for i in range(1, len(nums)):
if i > max_length:
return False
max_length = max(max_length, i+nums[i])
return True#45 Jump Game II
这道题就是最短路径问题，就用到了BFS，将当前能到达的点作为第一维度的图，由第一维度才能到达的为第二维度等等以此划分，最少节点到达的路径即为最短路径。
最开始的解答：
def jump(self, nums: List[int]) -> int:
if len(nums) <= 1:
return 0
max_length = nums[0]
if max_length >= len(nums)-1: return 1
start_node = 0
steps = 1
while start_node < len(nums) -1:
nodes = start_node
for i in range(nodes+1, nodes+1+nums[nodes]):
if i+nums[i] >= len(nums) - 1:
return steps+1
if i+nums[i] >= max_length:
start_node = i
max_length = i + nums[i]
steps += 1
return steps官方提供的O(N)解答（有修改）
def jump(self, nums: List[int]) -> int:
max_length, steps, farest_node = 0,0,0
for i in range(len(nums)-1):
if i <= max_length:
max_length = max(max_length, nums[i]+i)
if max_length >= len(nums) - 1:
return steps+1
# 如果超过了当前可到达节点，则更新下一跳可到达最远节点
if i == farest_node:
steps += 1
farest_node = max_length
return stepsdef maxProfit(self, prices: List[int]) -> int:
buy = prices[0]
profit = 0
for i in prices[1:]:
if i < buy:
buy = i
if i > buy:
profit = max(profit, i - buy)
return profit贪心算法
def maxProfit(self, prices: List[int]) -> int:
buy, profit = prices[0], 0
for i in prices[1:]:
if i < buy:
buy = i
else:
profit += i-buy
buy = i
return profit还有比较简单的写法：
def maxProfit(prices):
return sum(x[0]-x[1] for x in zip(prices[1:],prices[:-1]) if x[0]>x[1] )开始写得很复杂，用了两层循环，超出了时间限制：
def maxProfit(self, prices: List[int]) -> int:
buy1 = buy2 = prices[0]
profit1 = 0
max_profit = 0
for i in range(1, len(prices)):
if prices[i] < buy1:
buy1 = prices[i]
if prices[i] > buy1:
profit1 = prices[i] - buy1
profit2 = 0
if i < len(prices) - 2:
buy2 = prices[i+1]
for j in prices[i+2:]:
if j < buy2:
buy2 = j
if j > buy2:
profit2 = max(profit2, j-buy2)
max_profit = max(max_profit, profit2+profit1)
return max_profit后来看到了用前后遍历的算法的简单解法，豁然开朗：
def maxProfit(self, prices: List[int]) -> int:
buy1 = prices[0]
n = len(prices)
profit1, profit2 = [0]*n, [0]*n
max_profit = 0
for i in range(1, n):
buy1 = min(prices[i], buy1)
profit1[i] = max(profit1[i-1], prices[i]-buy1)
sell2 = prices[-1]
for i in range(n-2, 1, -1):
sell2 = max(sell2, prices[i])
profit2[i] = max(profit2[i+1], sell2-prices[i])
max_profit = max([i+j for (i,j) in zip(profit1, profit2)])
return max_profit动态规划DP(Dynamic programming),是一种将问题分成子问题，先解决子问题的方法。
这道题我看了各种解法，都不甚明白，后来在discuss里选了速度最快，占用内存最少的一种仔细研究，明白些许。hold[k]是k-1次操作后持有的股票收益减去买股票的金额，profit[k]是完成k次交易后得到的收益。
def maxProfit(k,prices):
n = len(prices)
if k >= n/2:
return sum(x-y for x,y in zip(prices[1:],prices[:-1]) if x>y)
profit, hold = [0]*(k+1),[float('-inf')]*(k+1)
for p in prices:
for i in range(1,k+1):
profit[i] = max(profit[i], hold[i]+p)
hold[i] = max(hold[i], profit[i-1]-p)
return profit[k]
按着上一题的思路，开始的解法如下：
def maxprofit(prices):
n = len(prices)
if n < 2:
return 0
buy,profit = [float('-inf')]*n,[0]*n
buy[0],buy[1] = -prices[0],max(buy[0],prices[1])
profit[1] = max(0,prices[1]-prices[0])
for i in range(2,n):
buy[i] = max(buy[i-1],profit[i-2]-prices[i])
profit[i] = max(profit[i-1],buy[i]+prices[i])
return profit[-1]
20ms，10.9MB
从两头开始向中间扫描
def maxArea(height):
n = len(height)
if n < 2:
return 0
start,end,water = 0,n-1,0
while start < end:
h_start,h_end = height[start],height[end]
if height[start] < height[end]:
water = max(water,height[start]*(end-start))
while height[start] <= h_start and start < end:
start += 1
else:
water = max(water,height[end]*(end-start))
while height[end] <= h_end and start < end:
end -= 1
return water
依旧用相向型双指针算法，要找到左边最高和右边最高。
def trap(height):
if len(height) < 3:
return 0
start,end,water = 0,len(height)-1,0
s_max,e_max = height[start], height[end]
while start <= end:
if s_max < e_max:
s_max = max(s_max, height[start])
water += s_max - height[start]
start += 1
else:
e_max = max(e_max, height[end])
water += e_max - height[end]
end -= 1
return water
我自己的解法是20ms，11MB
def increasingTriple(nums):
n = len(nums)
if n < 3: return False
i,j,k = 0,1,2
while k < n:
if nums[i] < nums[j] and nums[j]<nums[k]:
return True
while nums[i] >= nums[j]:
i = j
j = i + 1
k = i + 2
if k > n-1:
return False
while nums[j] >= nums[k]:
k += 1
if k > n -1:
j,k = j+1, j+2
break
return False
Discuss里有一写法更为简单，思路相同：
def increasingTriplet1(nums):
first = second = float('inf')
for n in nums:
if n <= first:
first = n
elif n <= second:
second = n
else:
return True
return False
16ms，11.2MB
比较简单，第一次就20ms，11.2MB
def longestConsecutive(nums):
if not nums: return 0
length,length_max = 0,[]
nums.sort()
start = nums[0]
for n in nums[1:]:
if n == start + 1:
length += 1
start += 1
elif n > start+1:
length_max.append(length)
start = n
length = 1
length_max.append(length)
return max(length_max)
#164 Maximum Gap
用的和上一题一样的思路，第一次就20ms，11.3MB
def maximumGap(nums):
if len(nums) < 2: return 0
nums.sort()
gap,maxGap,prev = 0,[],0
for n in nums:
if n-prev > gap:
gap = n-prev
maxGap.append(gap)
prev = n
else: prev = n
maxGap.append(gap)
return max(maxGap)
这题考察的似乎是 桶排序(Bucket sort)/基数排序（Radix sort) 算法,参考了最高票的Discuss，108ms，算法复杂度是O(32n)如下：
def radixSort(nums):
for i in range(31):
onebucket = []
zerobucket = []
needle = 1 << i
for j in range(len(nums)):
if nums[j] & neddle != 0:
onebucket.append(nums[j])
else:
zerobucket.append(nums[j])
nums = []
nums += zerobucket
nums += onebucket
return nums
def maxgap(nums):
if len(nums) < 2: return 0
nums = radixSort(nums)
res = 0
for i in range(1,len(num)):
res = max(nums[i]-nums[i-1],res)
return res
这道题先是要证明，这很简单，根据抽屉原理n个抽屉分配n+1个数，必有两个数分配在同一抽屉。接下来要找出这个重复的数我就用了Counter，算法复杂度是o(n)：
from collections import Counter
def findDup(nums):
n = Counter(nums)
for i in nums:
if n[i]>1:
return i
实际上，这道题据说花费了Don Knuth 24h才解出来。而且第二问存在四个约束条件。
解决本题的主要技巧就是要注意到：重复元素对应于一对下标i != j满足f(i) == f(j).我们的任务就变成寻找一对(i, j). 寻找这个重复值的问题就变成计算机科学界一个广为人知的“环检测”(cycle detection or cycle finding)问题。给定一个p型序列，在线性时间，只使用常数空间寻找环的起点，这个算法是由Robert Floyd提出的“龟兔”算法(Floyd's tortoise and the hare algorithm) 。算法的美妙之处在于只用o(1)的额外存储空间来记录slow指针和fast指针（第一部分），以及finder指针（第二部分）。运行时间复杂度为o(n)
- 第一步，让fast指针前进的速度是slow指针的倍数，当它们第一次相遇时，停下。设环起点距离列表起点为m，环的长度为n，它们相遇时距离环起点的距离为k，则slow走过的距离 i = m+a* n+k, fast走过的距离为2i = m+b* n+k, 距离相减可以得到 i = (b-a)* n, 说明slow和fast走过的距离都是环长的倍数；
- 第二步，让一个指针不动，另一指针移动到列表起点，两者同步移动，则相遇点即为环起点。如slow不动，fast移动到列表起点，更名为finder。当finder到达环起点，即移动m距离时，slow移动了m+i，而i为环长的倍数，也就是说slow也在环起点，所以slow和finder相遇点即为环起点。
def findDup1(nums):
slow = fast = 0
# keep advancing "slow" by one step and "fast" by two steps
# until they meet inside the loop
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# Start up another pointer from the end of the array and march
# it forward until it hits the pointer inside the array
finder = 0
while True:
slow = nums[slow]
finder = nums[finder]
# If the two hit, the intersection index is the duplicate element
if slow == finder:
return finder
参考了Discuss关于中位数的思考：
def findMedianSortedArrays(nums1,nums2):
m,n = len(nums1),len(nums2)
# Ensure j is non-negative
if m > n:
m,n,nums1,nums2 = n,m,nums2,nums1
imin, imax = 0,m
while imin<=imax:
# Ensure len(left)==len(right)
i = (imin+imax)/2
j = (m+n+1)/2 - i
# If i is too small
if i < m and nums1[i] < nums2[j-1]:
imin += 1
# If i is too big
elif i > 0 and nums1[i-1] > nums2[j]:
imax -= 1
else:
# i is perfect
if i==0 : max_of_left = nums2[j-1]
elif j == 0: max_of_left = nums1[i-1]
else: max_of_left = max(nums1[i-1],nums2[j-1])
# (m+n) is odd
if (m+n) % 2 == 1: return max_of_left
# (m+n) is even
if i == m: min_of_right = nums2[j]
elif j == n: min_of_right = nums1[i]
else: min_of_right = min(nums1[i],nums2[j])
return (max_of_left + min_of_right) / 2.0
#327 Count of Range Sum
#289 Game of Life
取两个数组的交集，其一可以使用计数的方式，利用collections.Counter的哈希对象计数：
from collections import Counter
def solutions(nums1, nums2):
if not (nums1 and nums2):
return []
counts1 = Counter(nums1)
res = []
for i in nums2:
if counts1[i] > 0:
res.append(i)
counts1[i] -= 1
return res其二可以使用双指针对于排序后的数组取交集，即对应元素较小的指针向后移一位：
def solution(nums1, nums2):
if not (nums1 and nums2):
return []
p1, p2, res = 0, 0, []
while p1<len(nums1) and p2<len(nums2):
if nums1[p1] == nums2[p2]:
res.append(nums1[p1])
p1 += 1
p2 += 1
elif nums1[p1] < nums2[p2]:
p1 += 1
else:
p2 += 1
return res将第一个字符串初始化为公共前缀，利用re.match与其他字符串进行比较，若匹配失败则将公共前缀的最后一个字符去掉，直到公共前缀为空或者全部match。注意，当只有一个元素时，公共前缀为该元素而不是"":
import re
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
if len(strs) == 1:
return strs[0]
res = strs[0]
for i in strs[1:]:
while re.match(res, i) == None:
res = res[:-1]
if not res:
return ""
return res或者用单指针在第一个字符串上移动，若当前元素与每个字符串对应位置元素相同，则公共前缀纳入该元素，出现不同则直接停止返回当前最大公共前缀：
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
res = min(strs,key=len)
for i,s in enumerate(res):
for string in strs:
if s != string[i]:
return res[:i]
return res还有一个避免了双循环的很机智的解法：
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
s1 = min(strs)
s2 = max(strs)
for i,s in enumerate(s1):
if s != s2[i]:
return s1[:i]
return s1#383 Ransom Note
#344 Reverse String
#205 Isomorphic Strings
#293 Flip Game
#294 Flip Game II
#290 Word Pattern
#242 Valid Anagram
#49 Group Anagrams
#87 Scramble String
#179 Largest Number
主要是找规律，然后利用字典按规律存储结果。
class Solution:
def convert(self, s: str, numRows: int) -> str:
if len(s) <= numRows or numRows <= 1:
return s
res = {}
for i in range(len(s)):
m = i % (2*numRows-2)
if m <= numRows-1:
if m in res:
res[m] += s[i]
else:
res[m] = s[i]
else:
m = (2*numRows-2) - m
res[m] += s[i]
s = ""
for i in res:
s += res[i]
return s同样的**，更简洁的写法：
class Solution(object):
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
if numRows == 1 or numRows >= len(s):
return s
L = [''] * numRows
index, step = 0, 1
for x in s:
L[index] += x
if index == 0:
step = 1
elif index == numRows -1:
step = -1
index += step
return ''.join(L)#161 One Edit Distance
#38 Count and Say
贪心算法，从最多的字母开始一个一个摆：
class Solution:
def rearrangeString(self, s: str, k: int) -> str:
if not s:
return ""
count = Counter(s)
count = sorted([[key, value] for key, value in count.items()], key=lambda x:x[1], reverse=True)
if k == 0 or count[0][1] == 1:
return s
res = ""
while count:
i = 0
for _ in range(k):
if i >= len(count):
return ""
res += count[i][0]
count[i][1] -= 1
if count[i][1] == 0:
count.pop(i)
i -= 1
i += 1
if len(res) == len(s):
return res
count = sorted(count,key=lambda x:x[1], reverse=True)#13 Roman to Integer
#12 Integer to Roman
#65 Valid Number
# 维护一个最大长度的窗口
def chracterReplacement(s, k):
max_len = res = 0
counts = collections.Counter()
for i in range(len(s)):
counts[s[i]] += 1
max_len = max(max_len, counts[s[i]])
if res - max_len < k:
res += 1
else:
counts[s[i - res]] -= 1 # 移动窗口
return res用堆栈来解决
DFS，剪枝
#66 Plus One
转换成整数加一
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
if not digits:
return digits
num = ''.join([str(i) for i in digits])
num = int(num) + 1
digits = [int(i) for i in str(num)]
return digits#258 Add Digits
#67 Add Binary
#43 Multiply Strings
#69 Sqrt(x)
#50 Pow(x, n)
#367 Valid Perfect Square
#204 Count Primes
#1 Two Sum
将数组利用字典存储，快速访问下标：
def twoSum(nums, target):
d = {}
for i,n in enumerate(nums):
if target-n in d:
return sorted([i, d[target-n]])
d[n] = i#15 3Sum
重点在于要先对数组进行排序，然后利用指针的**解决问题。
class Solution:
def threeSum(self, nums):
if len(nums) <= 2:
return []
nums = sorted(nums)
res = []
for i in range(len(nums)-2):
if i>0 and nums[i] == nums[i - 1]:
continue
if nums[i] > 0:
return res
left = i + 1
right = len(nums) - 1
while left < right:
n = nums[i] + nums[left] + nums[right]
if n == 0:
res.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif n > 0:
right -= 1
else:
left += 1
return res#16 3Sum Closest
#259 3Sum Smaller
#18 4Sum
#100 Same Tree
#101 Symmetric Tree
#226 Invert Binary Tree
#257 Binary Tree Paths
#112 Path Sum
#113 Path Sum II
#110 Balanced Binary Tree
#337 House Robber III
#206 Reverse Linked List
反转链表是最常考的题目，思维简单直接，主要考代码实现。
class Solution:
def reverseList(self, head):
cur, prev = head, None
while cur:
cur.next, prev, cur = prev, cur, cur.next
return prev#141 Linked List Cycle
#70 Climbing Stairs
动态规划问题主要是找对状态的定义以及DP状态转移方程，从结果开始递推：
class Solution:
def climbStairs(self, n: int) -> int:
res = {}
res[1] = 1
res[2] = 2
if n > 2:
for i in range(3, n+1):
res[i] = res[i-1] + res[i-2]
return res[n]利用python语言特点，可简化为：
class Solution:
def climbStairs(self, n: int) -> int:
prev, cur = 1, 1
for _ in range(1, n):
prev, cur = cur, cur+prev
return cur#62 Unique Paths
从终点倒推，每个位置的路径数等于下方路径数与右方路径数之和，利用两层循环：
def uniquePaths(self, m: int, n: int) -> int:
dp = [[1 for j in range(n)] for i in range(m)]
for i in range(m-2,-1,-1):
for j in range(n-2,-1,-1):
dp[i][j] = dp[i+1][j] + dp[i][j+1]
return dp[0][0]这道题没有路障，也可以直接使用组合数据来计算，路径总和等于从m+n-2次移动中选择m-1次向下移动（或n-1次向右移动）的方案数：
def uniquePaths(self, m: int, n: int) -> int:
return comb(m + n - 2, n - 1)#63 Unique Paths II
有路障，要注意考虑“无路可走”的特殊情况，所以比起上一道题，初始状态的设计要特别注意。
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
if obstacleGrid[-1][-1] == 1: return 0
m = len(obstacleGrid)
n = len(obstacleGrid[0])
dp = [[1-obstacleGrid[i][j] for j in range(n)]for i in range(m)]
for i in range(m-2,-1,-1):
dp[i][-1] = min(dp[i+1][-1], dp[i][-1])
for j in range(n-2, -1, -1):
dp[-1][j] = min(dp[-1][j], dp[-1][j+1])
for i in range(m-2,-1,-1):
for j in range(n-2,-1,-1):
dp[i][j] = 0
if obstacleGrid[i][j] == 0:
dp[i][j] = dp[i+1][j] + dp[i][j+1]
return dp[0][0]#53 Maximum Subarray
可以很简单发现一条策略：如果当前和小于0，则子序列重新开始，在此过程中记录最大和：
def maxSubArray(self, nums: List[int]) -> int:
max_sum, cur_sum = nums[0], nums[0]
for i in nums[1:]:
if cur_sum < 0:
cur_sum = i
else:
cur_sum += i
max_sum = max(max_sum, cur_sum)
return max_sum这道题很容易找到状态转移方程：$opt(n) = max(opt(n-1) + nums[n], nums[n]) $,但关键在于最终返回的不是opt(n)，而是$max(opt(1), opt(2), ..., opt(n))$
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max_sum = [nums[0]] * len(nums)
for i in range(1, len(nums)):
if max_sum[i-1] < 0:
max_sum[i] = nums[i]
else:
max_sum[i] = max_sum[i-1] + nums[i]
return max(max_sum)进一步，可以简化为（用max()比条件判断更占用内存）：
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
cur_sum = max_sum = nums[0]
for i in nums[1:]:
cur_sum = max(i, cur_sum + i)
max_sum = max(max_sum, cur_sum)
return max_sum#120 Triangle
- 递归（回溯），时间复杂度是$O(2^N)$
- 贪心会陷入局部最优，可能会错过全局最优
- DP：
- 定义状态：dp[i,j]表示从最底层走到(i,j)位置路径和的最小值，则本题的结果存在dp[0,0]中
- DP方程：$dp[i,j] = min(dp[i+1, j], dp[i+1, j+1]) + triangle(i,j)$,
- 初始状态：$dp[m-1,j] = triangle(m-1,j)$
- 结果：$dp[0][0]$
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
if len(triangle) == 1:
return triangle[0][0]
m = len(triangle)
dp = [[triangle[i][j] for j in range(len(triangle[i]))] for i in range(m)]
for i in range(m-2,-1,-1):
for j in range(len(triangle[i])):
dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]
return dp[0][0]用二维数组浪费空间，实际每次只需要存储一层的结果即可：
# 从底向上算
def minimumTotal(self, triangle: List[List[int]]) -> int:
if len(triangle) == 1:
return triangle[0][0]
dp = triangle[-1]
for i in range(len(triangle)-2,-1,-1):
for j in range(len(triangle[i])):
dp[j] = min(dp[j], dp[j+1]) + triangle[i][j]
return dp[0]
# 从上向下算
def minimumTotal(self, triangle: List[List[int]]) -> int:
if len(triangle) == 1: return triangle[0][0]
per = [triangle[0][0]]
for i in range(1,len(triangle)):
cur = triangle[i]
for j in range(i+1):
if j == 0:
cur[j] += per[j]
elif j == i:
cur[j] += per[j-1]
else:
cur[j] += min(per[j-1], per[j])
per = cur[:]
return min(cur)#322 Coin Change
经典的硬币找零问题，暴力求解太耗时，贪心算法容易陷入局部最优，因此还是用动态规划解决：
状态转移方程：$dp[n] = min(dp[n-coins[j]])+1$
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [amount+1] * (amount+1)
dp[0] = 0
for i in range(1, amount+1):
for j in coins:
if j <= i:
dp[i] = min(dp[i], dp[i-j]+1)
return dp[amount] if dp[amount] < amount+1 else -1#279 Perfect Squares
DP不熟悉的时候很容易将该题的状态定义为1d数组，然后状态转移方程定义为$dp[i] = dp[i-1] * nums[i]$时就会发现对于$nums[i]$为正/负数的情况无法区分，因为$nums[i]$为正时应与max_product相乘，而$nums[i]$为负时应与最小值相乘。因此状态应具备存储max_product & min_product的能力。
-
定义状态：$dp[i][2]$；$dp[i][0]$表示第i位时的最大乘积，$dp[i][1]$表示i位的最小乘积
-
DP方程：$dp[i][0] = dp[i-1][0] * nums[i], if(nums[i]>=0)$
$dp[i][0] = dp[i-1][1] * nums[i], if (nums[i]<0)$
$dp[i][1] = dp[i-1][1] * nums[i], if (nums[i]>=0)$
$dp[i][1] = dp[i-1][0] * nums[i], if (nums[i]<0)$ -
初始状态：$dp[0][0] =nums[0], dp[1][1] = nums[0]$
-
结果：$max(dp[i][0])$
为了减少内存使用，不需要用一个数组去存储结果，只需要保存当前最大乘积、最小乘积和全局最大乘积即可：
class Solution:
def maxProduct(self, nums: List[int]) -> int:
res = min_prod = max_prod = nums[0]
for i in nums[1:]:
if i >= 0:
max_prod = max(max_prod * i, i)
min_prod = min_prod * i
else:
max_prod, min_prod = min_prod * i, min(max_prod * i, i)
res = max(max_prod, res)
return res-
定义状态：dp[i]
-
DP方程：$dp[i] = max(dp[j]) + 1, 0<i<n, 0<=j<i$
-
初始状态：$dp[0] = 1$
-
结果：$max(dp[i])$
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
dp = [1]
for i in range(1, len(nums)):
dp.append(1)
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[j] + 1, dp[i])
return max(dp)算法时间度是$O(N)$，主要问题在第二个循环，考虑用二分查找来替代。巧妙之处在于将nums[i]插入nums[:i-1]中的维护的LIS中，是替换比nums[i]大的第一个数，这样保证当前LIS的长度是正确的。
import math
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
lis = [nums[0]]
for i in range(1, len(nums)):
if nums[i] > lis[-1]:
lis.append(nums[i])
elif nums[i] <= lis[0]:
lis[0] = nums[i]
else:
begin, end = 0, len(lis)-1
while begin <= end:
mid = math.ceil((begin + end) / 2)
if nums[i] == lis[mid]:
break
elif nums[i] < lis[mid]:
end = mid - 1
else:
begin = mid + 1
mid = math.ceil((begin + end) / 2)
lis[mid] = nums[i]
return len(lis) #64 Minimum Path Sum
- 状态：$dp[i][j]$, 从终点到当前位置最小的路径和
- DP方程：$dp[i][j] = min(dp[i+1][j], dp[i][j+1])$
- 初始状态：$dp[-1][-1] = nums[-1][-1]$
- 结果：$dp[0][0]$
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
dp = [[0 for j in range(n)] for i in range(m)]
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
if i == m - 1 and j == n - 1:
dp[i][j] = grid[i][j]
elif i == m - 1 and j < n - 1:
dp[i][j] = dp[i][j + 1] + grid[i][j]
elif j == n - 1 and i < m - 1:
dp[i][j] = dp[i + 1][j] + grid[i][j]
else:
dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) + grid[i][j]
return dp[0][0]#198 House Robber
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums) <= 2:
return max(nums)
dp = [nums[0], nums[1]]
for i in range(2, len(nums)):
dp.append(max(dp[:i-1]) + nums[i])
return max(dp)
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent