有关Dijkstra 算法基础可以参考之前的文章：
【LeetCode】1631 and 145（Dijkstra 算法应用，最小路径算法）
【LeetCode】743 and 917（Dijkstra 算法，最小路径算法）
额外问题：
如果我只想计算起点 start 到某⼀个终点 end 的最短路径，是否可以修改算法，提升⼀些效率？
肯定可以的，因为我们标准 Dijkstra 算法会算出 start 到所有其他节点的最短路径，你只想计算到 end 的最短路径，相当于减少计算量，当然可以提升效率。
需要在代码中做的修改也⾮常少，只要改改函数签名，再加个 if 判断就⾏了：
# 返回节点from 到 节点 to 之间边的权重def weight(form ,to)# 图的邻接表graph = {}# 输入一幅图和⼀个起点 start，计算 start 到其他节点的最短距离。def dijkstra(start, graph):# 图中节点个数n = len(graph)# 记录最短路径的权重# 定义：distTo[i] 的值就是节点 start 到达节点 i 的最短路径权重。初始化为正无穷distTo = [float("inf") for _ in range(n)]# base case，start 到 start 的最短距离就是 0distTo[start] = 0# 优先队列，distFromStart 较⼩的排在前⾯。# 贪心思维，对于每个状态，选择权值最小的那条边前进pq = PriorityQueue()# 从起点开始进行BFSpq.put([0, start])while not pq.empty():curDistFromStart, curNodeId = pq.get()# 在这⾥加⼀个判断就⾏了，其他代码不⽤改if (curNodeID == end):return curDistFromStartif (curDistFromStart > distTo[curNodeID]):# 已经有⼀条更短的路径到达 curNode 节点了continue# 将curNode的相邻节点装入队列，（层序遍历）for nextNodeID in graph[curNodeID]:# 看看从 curNode 达到 nextNode 的距离是否会更近distTonextNode = distTo[curNodeID] + weight(curNodeID,nextNodeID)if distTo[nextNodeID] > distToNextNode:# 更新 dp tabledistTo[nextNodeID] = distTonextNode# 将这个节点以及距离放⼊队列pq.put(distToNextNode, nextNodeID)# 如果运⾏到这⾥，说明从 start ⽆法⾛到 endreturn float("inf")
因为优先级队列⾃动排序的性质，每次从队列⾥⾯拿出来的都是distFromStart 值最⼩的，所以当你第⼀次从队列中拿出终点 end 时，此时的 distFromStart 对应的值就是从 start 到 end 的最短距离。
这个算法较之前的实现提前 return 了，所以效率有⼀定的提⾼。
下面本文将从实例出发，应用上述框架进行求解。
解法：Dijkstra 算法
Dijkstra 和很多最优化算法⼀样，计算的是「最优值」，这个最优
值可能是最⼤值，也可能是最⼩值。
标准 Dijkstra 算法是计算最短路径的，但你有想过为什么 Dijkstra 算法不允许存在负权重边么？
因为 Dijkstra 计算最短路径的正确性依赖⼀个前提：路径中每增加⼀条边，路径的总权重就会增加。
如果你想计算最⻓路径，路径中每增加⼀条边，路径的总权重就会减少，要是能够满⾜这个条件，也可以⽤Dijkstra 算法。
你看这道题是不是符合这个条件？边和边之间是乘法关系，每条边的概率都是⼩于 1 的，所以肯定会越乘越⼩。
只不过，这道题的解法要把优先级队列的排序顺序反过来，⼀些 if ⼤⼩判断也要反过来，我们直接看解法代码吧：
class Solution: def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float: graph = collections.defaultdict(list) # 无向图的构造 for i, (x, y) in enumerate(edges): graph[x].append((succProb[i], y)) graph[y].append((succProb[i], x)) que = [(-1.0, start)] prob = [0.0] * n prob[start] = 1.0 while que: pr, node = heapq.heappop(que) pr = -pr if node == end: return prob[end] if pr < prob[node]: continue for prNext, nodeNext in graph[node]: if prob[nodeNext] < prob[node] * prNext: prob[nodeNext] = prob[node] * prNext heapq.heappush(que, (-prob[nodeNext], nodeNext)) return prob[end]
191、位1的个数
解法：循环检查二进制位
我们可以直接循环检查给定整数 n 的二进制位的每一位是否为 1。
具体代码中，当检查第 i 位时，我们可以让 n与 2 i 2^i 2i 进行与运算，当且仅当 n 的第 i 位为 1 时，运算结果不为 0。
class Solution: def hammingWeight(self, n: int) -> int: ret = sum(1 for i in range(32) if n & (1 << i)) return ret
解法2：位运算优化
class Solution: def hammingWeight(self, n: int) -> int: ret = 0 while n: n &= n - 1 ret += 1 return ret