Koko loves to eat bananas. There are n piles of bananas, the i<sup>th</sup> pile has piles[i] bananas. The guards have gone and will come back in h hours.
Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.
Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.
Return the minimum integerksuch that she can eat all the bananas withinhhours.
Example 1:
<pre>Input: piles = [3,6,7,11], h = 8
Output: 4
</pre>
Example 2:
<pre>Input: piles = [30,11,23,4,20], h = 5
Output: 30
</pre>
Example 3:
<pre>Input: piles = [30,11,23,4,20], h = 6
Output: 23
</pre>
You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (u<sub>i</sub>, v<sub>i</sub>, w<sub>i</sub>), where u<sub>i</sub> is the source node, v<sub>i</sub> is the target node, and w<sub>i</sub> is the time it takes for a signal to travel from source to target.
We will send a signal from a given node k. Return the minimum time it takes for all thennodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.
Example 1:
<pre>Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
</pre>
Example 2:
<pre>Input: times = [[1,2,1]], n = 2, k = 1
Output: 1
</pre>
Example 3:
<pre>Input: times = [[1,2,1]], n = 2, k = 2
Output: -1
</pre>
Constraints:
1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= u<sub>i</sub>, v<sub>i</sub> <= n
u<sub>i</sub> != v<sub>i</sub>
0 <= w<sub>i</sub> <= 100
All the pairs (u<sub>i</sub>, v<sub>i</sub>) are unique. (i.e., no multiple edges.)
</div>
题目大意：
求从某一个点出发的所有能到达的点中的最短时间。若不能都到达返回-1
解题思路：
单源最短路径的最大值，如果有点不能到达返回-1.用BFS+Heap的模板
解题步骤：
N/A
注意事项：
用queue
Python代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
defnetworkDelayTime(self, times: List[List[int]], n: int, k: int) -> int: # build graph graph = collections.defaultdict(list) for e in times: graph[e[0]].append((e[1], e[2])) heap = [(0, k)] # weight, node visited = {k: 0} while heap: weight, node = heapq.heappop(heap) for neighbor, _weight in graph[node]: if neighbor in visited and visited[neighbor] <= weight + _weight: continue heapq.heappush(heap, (weight + _weight, neighbor)) visited[neighbor] = weight + _weight returnmax(visited.values()) iflen(visited) == n else -1
defbfs(self, graph, start) -> List[int]: queue, res = deque([start]), [] visited = {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
注意事项：
visited = {start}不写set([start])
if neighbor in visited在循环里，不是if node in visited
在bfs_layer2，res.append(level)
计算最短距离的图遍历(最常考的模板)
只要加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, target) -> int: queue = deque([start]) visited = {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
写法2
1 2 3 4 5 6 7 8 9 10 11 12 13
defbfs_layer_v2(self, graph, start, target) -> int: queue = deque([(start, 1)]) visited = {start} while queue: node, distance = queue.popleft() if node == target: return distance for neighbor in graph[node]: if neighbor in visited: continue queue.append((neighbor, distance + 1)) visited.add(neighbor) 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 14 15
defbfs_layer2(self, graph, start) -> List[List[int]]: queue, res = deque([start]), [] visited = {start} while queue: level = [] for _ inrange(len(queue)): node = queue.popleft() level.append(node) for neighbor in graph[node]: if neighbor in visited: continue queue.append(neighbor) visited.add(neighbor) res.append(level) return res
<div>
Implement a key-value store that can serialize multiple string key-value pairs into a single string and deserialize it back. Both keys and values can contain any characters including delimiters, newlines, and special characters.
