Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.
Format The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
Example 1:
Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/ \
2 3
return [1]
Example 2:
Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
return [3, 4]
Note:
(1) According to the definition of tree on Wikipedia): “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”
(2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
deffindMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]: ifnot edges: return [0] # remember graph = collections.defaultdict(list) in_degree = [0] * n for li in edges: graph[li[0]].append(li[1]) graph[li[1]].append(li[0]) in_degree[li[0]] += 1 in_degree[li[1]] += 1 queue = collections.deque([i for i in range(len(in_degree)) if in_degree[i] == 1]) res = list(queue) # remember while queue: for _ in range(len(queue)): node = queue.popleft() for neighbor in graph[node]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 1: queue.append(neighbor) if queue: # remember res = list(queue) return res
第四步判断是否含循环必不可少，要根据题目要求来处理。除非L310 min height明确一定有解，而L269外星人字典就明确可能无解
Python代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
deftopological_sort(self, graph: List[List[int]], n: int) -> List[int]: in_degree = [0] * n for i in range(len(graph)): for j in range(len(graph[i])): in_degree[graph[i][j]] += 1
start_nodes = [i for i in range(len(in_degree)) if in_degree[i] == 0] queue, res = deque(start_nodes), []
while queue: root = queue.popleft() res.append(root) for i in graph[root]: in_degree[i] -= 1 if in_degree[i] == 0: queue.append(i) return res if len(res) == n elseNone
defbfs(self, graph, start) -> List[int]: queue, res = deque([start]), [] visited = set([start]) while queue: node = queue.popleft() res.append(node) for neighbor in graph[node]: if neighbor in visited: continue queue.append(neighbor) visited.add(neighbor) return res
树模板只要把visited去掉，neighbor改成left和right
计算最短距离的图遍历(最常考的模板)
只要加line 4和14
visited在函数内定义
遇到target就返回最短距离，若离开循环返回-1，问清楚是否存在路径不存在的情况
求距离公式不需要用min，因为这个遍历保证了最短距离了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
defbfs_layer(self, graph, start) -> List[int]: queue = deque([start]) visited = set([start]) distance = {start: 1} while queue: node = queue.popleft() if node == target: return distance[node] for neighbor in graph[node]: if neighbor in visited: continue queue.append(neighbor) visited.add(neighbor) distance[neighbor] = distance[node] + 1 return-1
按层遍历
核心是加这一行for _ in range(len(queue)) 具体还要加line 5, 6和14, 15. 二叉树不需要visited。能用distance dict就尽量不用此法，因为多了一个循环。
注意事项：
关键行： 多这一行for循环
1 2 3 4 5 6 7 8 9 10 11 12 13
defbfs_layer2(self, graph, visited, start) -> List[List[int]]: queue, res, layer = deque([start]), [], 0 visited.add(start) while queue: for _ in range(len(queue)): node = queue.popleft() for neighbor in graph[node]: if neighbor in visited: continue queue.append(neighbor) visited.add(neighbor) layer += 1 return res
