1. Two Sum
考点
- 限制加和等于n。不要每一步都判断x+y=n，而是判断n-x=y
- 两次遍历。考虑不写2个for，而是1次遍历，把元素放到hashtable中
def twoSum(self, nums: List[int], target: int) -> List[int]:
tmp_dict = dict()
for i, j in enumerate(nums):
if j in tmp_dict:
return [tmp_dict[j], i]
tmp_dict[target - j] = i
2. Add Two Numbers
考点
- 对于链表，
curr.next指针向下走，这个不多说 curr1=curr1.next if curr1 else curr1这个操作，让遍历到尾部后，值保持curr1=None，好处是少些几行代码。作为配合，在其它行，可以用if curr1来判断是否到尾部- 链表还有个好处，如本例，
l3是含一个空的头的，返回l3.next即可
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
carry=0
l3=ListNode(None)
curr1,curr2,curr3=l1,l2,l3
while curr1 or curr2 or carry:
value=(curr1.val if curr1 else 0)+(curr2.val if curr2 else 0)+carry
carry,val=divmod(value,10)
curr3.next=ListNode(val)
curr1=curr1.next if curr1 else curr1
curr2=curr2.next if curr2 else curr2
curr3=curr3.next
return l3.next
3. Longest Substring Without Repeating Characters
考点：
- 2 sum 那道题里面写过，这种貌似需要两次遍历的题目。都可以想一下能不能用 hashTable 存下历史遍历，从而变成一次遍历。
def lengthOfLongestSubstring(self, s: str) -> int:
used = dict()
start = 0
res = 0
for i, c in enumerate(s):
if c in used and start <= used[c]:
start = used[c] + 1
else:
res = max(res, i - start + 1)
used[c] = i
return res
4. Median of Two Sorted Arrays
这个题目其实可以 cheat，俩列表加一起，然后用Python自代的sort，代码就不写了。
套路详解：https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2481/Share-my-O(log(min(mn)))-solution-with-explanation
考点：
- 中位数的定义：中位数两边的数量相等。
- 因此，num1 的分割和num2的分割存在一个恒等关系，len(left1)+len(left2)=len(right1)+len(right2)
- 这也就意味着，给定num1的分割，就立即能计算出num2的分割
- 本质上还是把两次遍历变成一次
- 如果if情况过多，考虑换一下两个变量，减少代码量。
(代码还是好难写，奇偶之类的)
def median(A, B):
m, n = len(A), len(B)
if m > n:
A, B, m, n = B, A, n, m
imin, imax, half_len = 0, m, (m + n + 1) / 2
while imin <= imax:
i = (imin + imax) / 2
j = half_len - i
if i < m and B[j-1] > A[i]:
# i is too small, must increase it
imin = i + 1
elif i > 0 and A[i-1] > B[j]:
# i is too big, must decrease it
imax = i - 1
else:
# i is perfect
if i == 0: max_of_left = B[j-1]
elif j == 0: max_of_left = A[i-1]
else: max_of_left = max(A[i-1], B[j-1])
if (m + n) % 2 == 1:
return max_of_left
if i == m: min_of_right = B[j]
elif j == n: min_of_right = A[i]
else: min_of_right = min(A[i], B[j])
return (max_of_left + min_of_right) / 2.0
5. Longest Palindromic Substring
没有套路。中间往外拓，平方级复杂度。
6. ZigZag Conversion
没有套路。按照ZigZag的字面意思，在s上做遍历。
（其实还可以先算出每个值所在的位置，不过有点儿费草稿纸）
class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows==1 or (len(s)<numRows):
return s
res_list = [''] * numRows
location, direction = 0, -1 # 假想开头前面也迭代过程中，所以初始是负号
for i in s:
res_list[location] = res_list[location] + i
if location == 0 or location == numRows - 1:
direction = -direction
location += direction
return ''.join(res_list)
7. Reverse Integer
没有套路。
按位数颠倒一个整数。考虑负号和零。Python用字符串反转就行了。
class Solution:
def reverse(self, x: int) -> int:
sign = 1 if x >= 0 else -1
y=sign*int(str(sign*x)[::-1])
if y>2**31-1 or y<-2**31:
return 0
return y
简洁的写法
class Solution:
def reverse(self, x: int) -> int:
sign = (x > 0) - (x < 0)
r = int(str(sign*x)[::-1])
return sign*r * (r < 2**31)
8. String to Integer (atoi)
实在无聊的题，就是各种边界条件。不用看了
9.
无聊
10. Regular Expression Matching
好题！
套路：
- 递归（不是很容易想出）
- 递归的某些节点被反复调用。考虑存下来。（下面代码里面没有体现）
https://leetcode.com/problems/regular-expression-matching/solution/
def isMatch(text, pattern):
if not pattern:
return not text
first_match= text and pattern[0] in {text[0],'.'}
if len(pattern)>=2 and pattern[1]=='*':
return isMatch(text,pattern[2:]) or first_match and isMatch(text[1:],pattern)
else:
return first_match and isMatch(text[1:],pattern[1:])
需要再过一遍：DP也能很好的解这个题。
11. Container With Most Water
好题！
- 像 2-sum 那个题目，看起来需要2次遍历，立即想到暂存历史计算，减少计算量。
- 先看看哪些情况是“不可能”的，把它们排除出去。左挡板从左向右遍历，如果后一个比前一个还短，那么这个不可能是 candidate，右挡板同样的道理。
- （到上面这一步已经可以写代码了，最坏平方级复杂度）还可以继续优化（这个看答案才想出来）。我们上一步把不可能的情况删掉后得到了递增的左挡板，和递增（从右往左看）的右挡板。如果左挡板低于右挡板，那么右挡板向左移动就不可能是 candidate，于是又排除了很多情况，变成 O(n) 复杂度。
a=[1,8,6,2,5,4,8,3,7]
i,j=0,len(a)-1
weight=0
while i<j:
weight=max(weight,(j-i)*min(a[i],a[j]))
if a[i]<a[j]:
i+=1
else:
j-=1
weight
12. Integer to Roman
无聊的题
all_symbols = [
['', 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX']
,['', 'X', 'XX', 'XXX','XL', 'L', 'LX', 'LXX', 'LXXX', 'XC']
, ['', 'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM']
,['', 'M', 'MM', 'MMM']
]
''.join([all_symbols[i][num//(10**i)%10] for i in range(3,-1,-1)])
13~15 无聊的题目
16. 3Sum Closest
n-Sum 两种思路：
- 复用2sum，加一层遍历。2sum复杂度是n，3sum复杂度是O(n^2)
- 2sum还有另一种解法，先排序，然后使用
Container With Most Water的思路，找解复杂度是 O(n),但排序的复杂度是 O(nlgn)，所以2sum复杂度是 O(nlgn),3sum复杂度 O(n^2+nlgn)=O(n^2) - 所以2sum和3sum都可以用这个思路，复杂度一样
- 但3Sum Closest显然不能用1了，但可以用2
nums=[0,-4,1,-5]
target=0
nums.sort()
def sum2_cloeset(nums,n):
i,j=0,len(nums)-1
res=nums[i]+nums[j]
diff=abs(res-n)
while i<j:
sum2=nums[i]+nums[j]
if sum2==n:
return sum2
diff_tmp=abs(sum2-n)
if diff_tmp<diff:
diff=diff_tmp
res=sum2
if sum2>n:
j-=1
else:
i+=1
return res
# nums=[1,2,3,4,5]
# sum2_cloeset(nums,5)
diff=abs(sum(nums[:3])-target)
res=sum(nums[:3])
for i in range(len(nums)-2):
tmp=sum2_cloeset(nums[i+1:],target-nums[i])
if abs(tmp+nums[i]-target)<diff:
print(tmp,nums[i])
res=tmp+nums[i]
diff=abs(tmp+nums[i]-target)
res
17. Letter Combinations of a Phone Number
基础题，可以以此题为例子，把几种解法练熟了，甚至背下来。
- 利用 itertools
import itertools def letterCombinations(self, digits: str) -> List[str]: if len(digits)==0:return [] all_char=['','','abc','edf','ghi','jkl','mno','pqrs','tuv','wxyz'] candidate=[list(all_char[int(button)]) for button in digits] return [''.join(i) for i in itertools.product(*candidate)] - 递归。这个递归方法要求返回所有遍历到叶节点的路径。而不是成功访问1个叶节点就返回。这两种递归都要非常熟悉。
all_char=['','','abc','edf','ghi','jkl','mno','pqrs','tuv','wxyz'] def letter_comb(digits): if len(digits)==0: return [] if len(digits)==1: return list(all_char[int(digits[0])]) prev=letter_comb(digits[:-1]) lst=all_char[int(digits[-1])] return [s+l for s in prev for l in lst] letter_comb(digits) - 递归（从前往后），另外，如果不考虑空的特殊情况，代码还可以再省一些
all_char=['','','abc','edf','ghi','jkl','mno','pqrs','tuv','wxyz'] def letter_comb(digits): if len(digits)==0: return [''] prev=all_char[int(digits[0])] lst=letter_comb(digits[1:]) return [p+l for p in prev for l in lst] - 遇到笛卡尔积问题，优先使用这个套路。递归太容易写错，还是for循环好一些。
all_char=['','','abc','edf','ghi','jkl','mno','pqrs','tuv','wxyz'] def letter_comb(digits): digits=[int(i) for i in digits] res=[''] for digit in digits: res=[i+j for i in res for j in all_char[digit]] return res - 事实证明，太多骚操作，复用就不方便。简简单单的for循环。（22题复用此代码） ```python all_char=[’’,’’,’abc’,’edf’,’ghi’,’jkl’,’mno’,’pqrs’,’tuv’,’wxyz’]
digits=[int(i) for i in digits] def letter_comb(digits): res=[’’] for digit in digits: tmp=list() for i in res: for j in all_char[digit]: tmp.append(i+j) res=tmp return res
### 18. 4Sum
用递归，nSUM都能做出来
```python
def find_2sum(nums,target):
i,j=0,len(nums)-1
res=[]
while i<j:
sum2=nums[i]+nums[j]
if sum2==target:
res.append([nums[i],nums[j]])
i+=1
elif sum2>target:
j-=1
else:
i+=1
return res
def find_Nsum(nums,target,N):
if N==2:
return find_2sum(nums,target)
res=[]
for i in range(len(nums)-N+1):
tmp=find_Nsum(nums[i+1:],target-nums[i],N-1)
if len(tmp)>0:
res.extend([[nums[i]]+t for t in tmp])
return res
nums=[1,0,-1,0,-2,2]
target=0
nums.sort()
find_Nsum(nums,target,N=4)
19. Remove Nth Node From End of List
考点：
- 凡是链表上的遍历问题，一律先想想能否使用单指针/双指针/多指针
- 如果处理的链表是不含空的头节点那种，一律加上空的头节点。这样往往可以减少很多处理边界条件的代码量。
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy=ListNode('')
dummy.next=head
curr1=dummy
for i in range(n):
curr1=curr1.next
curr2=dummy
while curr1.next:
curr1=curr1.next
curr2=curr2.next
curr2.next=curr2.next.next
return dummy.next
20. Valid Parentheses
好题目，用堆栈做，没什么难度
def isValid(self, s: str) -> bool:
stack=list()
pairs={'(':')','[':']','{':'}'}
pairs2={')':'(',']':'[','}':'{'}
for i in s:
if i in pairs:
stack.append(i)
elif i in pairs2:
if len(stack)==0:
return False
elif stack[-1]==pairs2[i]:
stack.pop()
else:
return False
return len(stack)==0
21. Merge Two Sorted Lists
基础题，
- 遇到链表，第一想到指针
- 处理链表，一律先转化成带空头节点的链表。可以减少一些边界条件的代码量，减少错误。
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 is None :
return l2
if l2 is None:
return l1
dummy1,dummy2=ListNode(),ListNode()
dummy1.next,dummy2.next=l1,l2
curr1,curr2=dummy1,dummy2.next
while curr2 and curr1.next:
if curr1.next.val>curr2.val:
tmp1,tmp2=curr1.next,curr2.next
curr1.next=curr2
curr2.next=tmp1
curr2=tmp2
curr1=curr1.next
else:
curr1=curr1.next
while curr1.next:
curr1=curr1.next
curr1.next=curr2
return dummy1.next
22. Generate Parentheses
先把左括号全写出来，然后插入右括号。想到套路:
- 抽屉插空问题
- 解决抽屉插空问题，需要罗列笛卡尔积。用17题的方法，最土的for循环。
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
cases=[[[0],0]] # seq&cumsum
for i in range(1,n):
tmp=[]
for case in cases:
seq,cumsum=case
for k in range(i-cumsum+1):
tmp.append([seq+[k],cumsum+k])
cases=tmp
res=[]
for case in cases:
seq,cumsum=case[0],case[1]
one_case=''
for i in seq:
one_case+=')'*i
one_case+='('
one_case+=(')'*(n-cumsum))
res.append(one_case)
return set(res)
23. Merge k Sorted Lists
复用merge2
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if len(lists)==0:return None
if len(lists)==1:return lists[0]
def merge2(l1,l2):
if l1 is None :
return l2
if l2 is None:
return l1
dummy1,dummy2=ListNode(),ListNode()
dummy1.next,dummy2.next=l1,l2
curr1,curr2=dummy1,dummy2.next
while curr2 and curr1.next:
if curr1.next.val>curr2.val:
tmp1,tmp2=curr1.next,curr2.next
curr1.next=curr2
curr2.next=tmp1
curr2=tmp2
curr1=curr1.next
else:
curr1=curr1.next
while curr1.next:
curr1=curr1.next
curr1.next=curr2
return dummy1.next
l1=lists[0]
for i in range(1,len(lists)):
l1=merge2(l1,lists[i])
return l1
24. Swap Nodes in Pairs
考点都是在前面出现过的，必须都玩熟了：
- 遇到链表，无脑转成带空头节点的链表
- 用
curr.next and curr.next.next来规避curr.next是None的情况
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if head is None:
return head
node=ListNode()
node.next=head
curr=node
while curr.next and curr.next.next:
tmp1,tmp2=curr.next,curr.next.next
tmp1.next=tmp2.next
tmp2.next=tmp1
curr.next=tmp2
curr=tmp1
return node.next
25. Reverse Nodes in k-Group
这个题就是两个逻辑的合并：取接下来的n个node，链表反转。
- 链表反转是一个基础考点。可以每次把最前面的节点放到后面。也可以每次把最后面的节点放到前面。
- 链表上的遍历，立即想到指针。
- 链表无脑转为带空头节点的链表
- 实际上可以一边向下遍历，一边反转，但这种解法与“不玩儿骚操作”的理念不符。作为替代，把“遍历找到下面k个”和“链表反转”作为两个部分分开写（尽管运行速度会慢一些）
