100. Same Tree
递归基础题，需要练
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if p is None and q is None:
return True
if p is None or q is None:
return False
if p.val!=q.val:
return False
return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
101. Symmetric Tree
跟上一个题一模一样
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
def is_symm(left,right):
if left is None and right is None:
return True
if left is None or right is None:
return False
if left.val!=right.val:
return False
return is_symm(left.left,right.right) and is_symm(left.right,right.left)
if root is None:
return True
return is_symm(root.left,root.right)
102. Binary Tree Level Order Traversal
经典的 level order，也就是 BFS
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
queue,res=[root],[]
while queue:
new_queue=[]
res_tmp=[]
for node in queue:
if node is None:
continue
res_tmp.append(node.val)
new_queue.append(node.left)
new_queue.append(node.right)
queue=new_queue
if res_tmp:
res.append(res_tmp)
return res
因为返回值 res[level] 这种格式，因此 DFS 也挺方便
103. Binary Tree Zigzag Level Order Traversal
先 level order ，然后奇数位倒置
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
res=[]
queue=[root]
while queue:
new_queue=[]
res_tmp=[]
for node in queue:
if node is None:
continue
res_tmp.append(node.val)
new_queue.append(node.left)
new_queue.append(node.right)
if res_tmp:
res.append(res_tmp)
queue=new_queue
for i in range(len(res)):
if i%2==1:
res[i]=res[i][::-1]
return res
104. Maximum Depth of Binary Tree
dfs+cache
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
res=[0]
def dfs(node,num):
if node is None:
res[0]=max(res[0],num)
return
dfs(node.left,num+1)
dfs(node.right,num+1)
dfs(root,0)
return res[0]
105～106
- Construct Binary Tree from Preorder and Inorder Traversal
- Construct Binary Tree from Inorder and Postorder Traversal
感觉要背下来
##
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
res=[]
queue=[root]
while queue:
new_queue=[]
res_tmp=[]
for node in queue:
if node is None:
continue
res_tmp.append(node.val)
queue.append(node.left)
queue.append(node.right)
queue=new_queue
if res_tmp:
res.append(res_tmp)
return res[::-1]
108.
108.Convert Sorted Array to Binary Search Tree，基本题目了，不用背也会
class Solution:
def sorted2BST(self, nums):
if not nums:
return None
mid = len(nums) // 2
return TreeNode(val=nums[mid], left=self.sorted2BST(nums[:mid]), right=self.sorted2BST(nums[mid + 1:]))
109.Convert Sorted List to Binary Search Tree
答案也不贴了，用几个基本元素拼起来就行了
110. Balanced Binary Tree
一开始觉得是这样的：把所有节点的深度列出来，然后最大深度和最小深度相差1即可。但这样过不了测试，反例 [1,2,3,4,5,6,null,8] 被判断为否，测试用例应当为 True。
平衡二叉树的正式定义为：左子树和右子树深度相差不超过1，跟上面的理解有些差距
# 错误解法
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
levels=[]
def dfs(node,level):
if node is None:
levels.append(level)
return
dfs(node.left,level+1)
dfs(node.right,level+1)
dfs(root,0)
return max(levels)<=min(levels)+1:
正确解法
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
res=[True]
def dfs(node):
if res[0] is False:
return
if node is None:
return 0
left_depth=dfs(node.left)
# None 代表已经全局判断为 False 了，无须再计算level
if left_depth is None:
return
right_depth=dfs(node.right)
if right_depth is None:
return
if abs(left_depth-right_depth)>1:
res[0]=False
return
else:
return max(left_depth,right_depth)+1
dfs(root)
return res[0]
111. Minimum Depth of Binary Tree
这题也是对定义理解问题，是叶子节点的level
dfs
class Solution:
def minDepth(self, root: TreeNode) -> int:
if root is None:
return 0
res=[100000]
def dfs(node,level):
if node is None:
return
if node.left is None and node.right is None:
res[0]=min(res[0],level)
return
else:
dfs(node.left,level+1)
dfs(node.right,level+1)
dfs(root,1)
return res[0]
112. Path Sum
就dfs
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
res=[]
def dfs(node,path_sum):
if node is None:
return
if node.left is None and node.right is None: # 到达叶子节点
res.append(path_sum+node.val)
dfs(node.left,path_sum+node.val)
dfs(node.right,path_sum+node.val)
dfs(root,0)
return targetSum in res
忘了还能剪枝
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
res=[False]
def dfs(node,path_sum):
if res[0]:
return
if node is None:
return
if node.left is None and node.right is None: # 到达叶子节点
if path_sum+node.val==targetSum:
res[0]=True
dfs(node.left,path_sum+node.val)
dfs(node.right,path_sum+node.val)
dfs(root,0)
return res[0]
113. Path Sum II
还是 dfs
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
res=[]
if root is None:
return res
def dfs(node,path,path_sum):
if node is None:
return
if node.left is None and node.right is None:
if path_sum+node.val==targetSum:
res.append(path+[node.val])
return
dfs(node.left,path+[node.val],path_sum+node.val)
dfs(node.right,path+[node.val],path_sum+node.val)
dfs(root,[],0)
return res
114. Flatten Binary Tree to Linked List
dlr 遍历，之前背的 one liner 不实用，背这个
class Solution:
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
def dlr(node):
if not node:
return
tmp=node.right
node.right=dlr(node.left)
node.left=None
curr=node
while curr.right:
curr=curr.right
curr.right=dlr(tmp)
return node
dlr(root)
116. Populating Next Right Pointers in Each Node
基础的 level order
class Solution:
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
if not root:
return root
queue=[root]
while queue:
new_queue=list()
for idx in range(len(queue)-1):
queue[idx].next=queue[idx+1]
if queue[idx].left:
new_queue.append(queue[idx].left)
if queue[idx].right:
new_queue.append(queue[idx].right)
if queue[-1].left:
new_queue.append(queue[-1].left)
if queue[-1].right:
new_queue.append(queue[-1].right)
queue=new_queue
return root
117. Populating Next Right Pointers in Each Node II
"""
# Definition for a Node.
class Node:
def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return root
queue=[root]
while queue:
new_queue=list()
last_node=None
for node in queue:
if last_node is not None:
last_node.next=node
if node.left:
new_queue.append(node.left)
if node.right:
new_queue.append(node.right)
last_node=node
queue=new_queue
return root
118. Pascal’s Triangle
level order
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
res=[]
level=[1]
for i in range(numRows):
res.append(level)
next_level=[]
for i in range(len(level)-1):
next_level.append(level[i]+level[i+1])
level=[1]+next_level+[1]
return res
119. Pascal’s Triangle II
level order
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
res=[1]
for i in range(rowIndex):
new_res=[]
for idx in range(len(res)-1):
new_res.append(res[idx]+res[idx+1])
res=[1]+new_res+[1]
return res
120. Triangle
比较大小的，一般用 bfs 而不是 dfs，也就是 level order
class Solution:
def minimumTotal(self, triangle) -> int:
queue = triangle[0]
for line in triangle:
if len(line) == 1:
continue
new_queue = []
for idx in range(len(queue) - 1):
new_queue.append(line[idx+1] + min(queue[idx], queue[idx + 1]))
queue = [queue[0] + line[0]] + new_queue + [queue[-1] + line[-1]]
return min(queue)
121. Best Time to Buy and Sell Stock
思路1（抄的）：站在每一天，看之前哪天买最合适
class Solution:
def maxProfit(self, prices) -> int:
min_price = 100000
res = 0
for p in prices:
if p < min_price:
min_price = p
else:
res = max(res, p - min_price)
return res
思路2（想的）
- 有点儿像接水的那个题
- 自然想到双指针
- 左边追求最小，右边追求最大。如果 left<right，就都移动；否则，分裂为2种情况，用递归
- （不好想），因为两边追求的是两个方向，因此都从左边出发，向同一个方向走。代码和上一个思路一样了
122. Best Time to Buy and Sell Stock II
简单，每天都买卖一次
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0
for idx in range(len(prices) - 1):
if prices[idx + 1] > prices[idx]:
profit += (prices[idx + 1] - prices[idx])
return profit
125. Valid Palindrome
class Solution:
def isPalindrome(self, s: str) -> bool:
s=[i for i in s.lower() if 97<=ord(i)<=122 or 48<=ord(i)<=57]
return s==s[::-1]
129. Sum Root to Leaf Numbers
！！！这题不是公式里面的 dfs/bfs 类题目，而是更基本的树上的递归问题
class Solution:
def sumNumbers(self, root: TreeNode) -> int:
def myfunc(node,sum_):
if node is None:
return 0
sum_+=node.val
if node.left is None and node.right is None:
return sum_
return myfunc(node.left,10*sum_)+myfunc(node.right,10*sum_)
return myfunc(root,0)
131. Palindrome Partitioning
dfs+cache，不过效率好差，双击败5%
class Solution:
def partition(self, s: str):
cache = dict()
def dfs(string):
if string in cache:
return cache[string]
if len(string) == 1:
res = {(string,)}
else:
res = set()
if string == string[::-1]:
res.add((string,))
for i in range(1, len(string)):
res.update({part1 + part2 for part1 in dfs(string[:i]) for part2 in dfs(string[i:])})
cache[string] = res
return res
tmp = dfs(s)
return [list(i) for i in tmp]
133. Clone Graph
作弊
copy.deepcopy(node)
显然 dfs+cache
- graph 要注意回环的情况，否则会 max recursion
- 回环后，不要直接new一个node，而是查看是否已有（在cache中）
class Solution:
def cloneGraph(self, node) :
if node is None:
return None
root_old = node
root_new = Node(val=node.val)
cache = dict()
def dfs(node, node_new):
if node.val in cache:
return
cache[node.val]=node_new
for neighbor in node.neighbors:
neighbor_new=cache.get(neighbor.val,Node(neighbor.val))
node_new.neighbors.append(neighbor_new)
dfs(neighbor, neighbor_new)
dfs(root_old, root_new)
return root_new
134. Gas Station
- gas=gas-cost，然后只在gas上面判断即可。
- 暴力循环超时
# 超时
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
for idx in range(len(gas)):
gas[idx]-=cost[idx]
def is_good(nums):
residu=0
for num in nums:
residu+=num
if residu<0:
return False
return True
for idx in range(len(gas)):
if gas[idx]<0:
continue
if is_good(gas[idx:]+gas[:idx]):
return idx
return -1
剪枝：
gas[idx]<0一定不成立- 如果
gas[idx]不成立，并且gas[idx+1]>0，那么idx+1也不成立，直到遇到gas[idx+n]<0 - 注意处理0的情况
class Solution:
def canCompleteCircuit(self, gas, cost) -> int:
for idx in range(len(gas)):
gas[idx] -= cost[idx]
if sum(gas) < 0:
return -1
def is_good(nums):
residu = 0
for num in nums:
residu += num
if residu < 0:
return False
return True
skip = False
for idx in range(len(gas)):
if skip:
if gas[idx] >= 0:
continue
else:
skip = False
continue
if gas[idx] < 0:
continue
if is_good(gas[idx:] + gas[:idx]):
return idx
else:
skip = True
return -1
139. Word Break
递归+cache，beat98%&95%
这个题 其实应该用 Trie 进一步优化，不过这次没这么做
class Solution:
def wordBreak(self, s: str, wordDict) -> bool:
cache = dict()
max_len = max(len(i) for i in wordDict)
def dfs(idx):
if idx in cache:
return cache[idx]
res = False
if s[:idx + 1] in wordDict:
res = True
else:
for i in range(max(idx - max_len, 0), idx):
if dfs(i) and s[i + 1:idx + 1] in wordDict:
res = True
break
cache[idx] = res
return res
dfs(len(s) - 1)
return cache[len(s) - 1]
140. Word Break II
和上一个题思路一样。
与上一个题一样，都是调 idx 调了好半天
class Solution:
def wordBreak(self, s: str, wordDict):
cache = dict()
max_len = max(len(i) for i in wordDict)
def dfs(idx):
if idx in cache:
return cache[idx]
res = []
if idx == 0:
res = [[]]
else:
for i in range(max(0, idx - max_len - 1), idx):
if s[i:idx] in wordDict:
for item in dfs(i):
res.append(item + [s[i:idx]])
cache[idx] = res
return res
dfs(len(s))
return [' '.join(i) for i in cache[len(s)]]
141. Linked List Cycle
快慢指针
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
pointer1,pointer2=head,head
while pointer1 and pointer2 and pointer2.next:
pointer1=pointer1.next
pointer2=pointer2.next.next
if pointer1 is pointer2:
return True
return False
142. Linked List Cycle II
快慢指针太技巧了，用hash表存一下即可
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
cache,curr,pos=set(),head,0
while curr:
if curr in cache:
return curr
cache.add(curr)
curr=curr.next
return None
143. Reorder List
思路
- 做成两个LinkedList，
- 其中一个按题目要求反转
- 然后合并
???
146. LRU Cache
借助队列，判断哪些是最近未访问过的
class Queue:
def __init__(self,capacity):
self.capacity=capacity
self.queue=list()
def visit(self,key):
if key in self.queue:
self.queue.remove(key)
self.queue.append(key)
droped=None
if len(self.queue)>self.capacity:
droped=self.queue[0]
self.queue=self.queue[1:]
return droped
class LRUCache:
def __init__(self, capacity: int):
self.cache=dict()
self.queue=Queue(capacity)
def get(self, key: int) -> int:
if key in self.cache:
self.queue.visit(key)
return self.cache[key]
else:
return -1
def put(self, key: int, value: int) -> None:
droped=self.queue.visit(key)
if droped is not None:
del self.cache[droped]
self.cache[key]=value
用 OrderedDict，简直是量身定做
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.capacity=capacity
self.cache=OrderedDict()
def get(self, key: int) -> int:
if key in self.cache:
self.cache.move_to_end(key=key)
return self.cache[key]
return -1
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache[key]=value
self.cache.move_to_end(key)
else:
self.cache[key]=value
if len(self.cache)>self.capacity:
self.cache.popitem(last=False)
151. Reverse Words in a String
return ' '.join(i for i in s.split(' ')[::-1] if i)
160. 相交链表
简单
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
cache=set()
while headA:
cache.add(headA)
headA=headA.next
while headB:
if headB in cache:
return headB
headB=headB.next
return None
165. Compare Version Numbers
class Solution:
def compareVersion(self, version1: str, version2: str) -> int:
version1=[int(i) for i in version1.split('.')]
version2=[int(i) for i in version2.split('.')]
while len(version1)>1 and version1[-1]==0:
version1.pop()
while len(version2)>1 and version2[-1]==0:
version2.pop()
if version1>version2:
return 1
elif version1<version2:
return -1
else:
return 0
167. Two Sum II - Input Array Is Sorted
二分法。 边界条件有些烦人
class Solution:
def twoSum(self, numbers, target: int):
curr, left, right = 0, 1, len(numbers) - 1
while curr < right:
target_1 = target - numbers[curr]
while left < right:
# print(curr, left, right)
mid = (left + right) // 2
if numbers[mid] < target_1:
left = mid + 1
elif numbers[mid] > target_1:
right = mid - 1
else:
return curr + 1, mid + 1
if numbers[left] == target_1:
return curr + 1, left + 1
curr += 1
left = curr + 1
return -1
168. Excel Sheet Column Title
恶心的边界条件
class Solution:
def convertToTitle(self, columnNumber: int) -> str:
dictionary = {i: chr(i + 65) for i in range(26)}
res = ''
while columnNumber:
columnNumber -= 1
columnNumber, tmp1 = divmod(columnNumber, 26)
res = dictionary[tmp1]+res
return res
171. Excel Sheet Column Number
class Solution:
def titleToNumber(self, columnTitle: str) -> int:
dictionay={chr(i+65):i for i in range(26)}
res=0
for i in columnTitle:
res*=26
res+=(dictionay[i]+1)
return res
169. Majority Element
import collections
class Solution:
def majorityElement(self, nums: List[int]) -> int:
counter = collections.Counter(nums)
return counter.most_common(1)[0][0]
172. Factorial Trailing Zeroes
思路：
- 0的数量取决于2和5的数量
- 无论什么情况下，2的数量肯定是够的。因此只需要计算5的数量
- 对于k，用k%5 来计算5的数量
class Solution:
def trailingZeroes(self, n: int) -> int:
def get_5(i):
num_5 = 0
while i:
i, k2 = divmod(i, 5)
if k2:
return num_5
num_5 += 1
res = 0
for i in range(1, n + 1):
res += get_5(i)
return res
187. Repeated DNA Sequences
class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
res=set()
tmp=set()
for i in range(len(s)-9):
if s[i:i+10] in tmp:
res.add(s[i:i+10])
else:
tmp.add(s[i:i+10])
return list(res)
190. Reverse Bits
class Solution:
def reverseBits(self, n: int) -> int:
n_str=bin(n)[2:]
n_str='0'*(32-len(n_str))+n_str
return int(n_str[::-1],2)
这题还有更高级的方案：
- 本质上是循环把n的低位放到res的高位
res, i = 0, 32
while i:
res <<= 1
res += (n & 1)
n >>= 1
i -= 1
res
191. Number of 1 Bits
cnt = 0
while n:
n = n & (n - 1)
cnt += 1
192-195 bash题
192. Word Frequency
cat words.txt| tr -s ' ' '\n' | sort | uniq -c | sort -r | awk '{print $2, $1}'
193. Valid Phone Numbers
grep -P '^([0-9]{3}-|\([0-9]{3}\) )[0-9]{3}-[0-9]{4}$' file.txt
python3 -c "
a = [i.split() for i in open('file.txt', 'r')]
print('\n'.join(' '.join(i) for i in zip(*a)))
"
python3 -c "
with open('file.txt', 'r') as f:
for i in range(9):
f.readline()
print(f.readline().replace('\n', ''))
"
198. House Robber
dfs+cache 套公式
class Solution:
def rob(self, nums: List[int]) -> int:
len_num=len(nums)
cache=dict()
def dfs(idx):
if idx in cache:
return cache[idx]
res=None
if idx==len_num-1:
res=nums[idx]
elif idx==len_num-2:
res=nums[idx]
else:
res= nums[idx]+max([dfs(i) for i in range(idx+2,len_num)])
cache[idx]=res
return res
return max([dfs(i) for i in range(len_num)])
199. Binary Tree Right Side View
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
res=[]
if not root:
return res
queue=[root]
while queue:
res.append(queue[-1].val)
new_queue=list()
for node in queue:
if node.left:
new_queue.append(node.left)
if node.right:
new_queue.append(node.right)
queue=new_queue
return res
