标签: 图
难度: Medium
Submission
运行时间: 133 ms
内存: 25.9 MB
class Solution:
def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:
masks = [0]*(n+1)
for r1, r2 in corridors:
masks[r1]|=1<<r2
masks[r2]|=1<<r1
res = 0
for r1, r2 in corridors:
r1, r2 = min(r1, r2), max(r1,r2)
res += (masks[r1]&masks[r2]& ((1<<r2)-1) & ~((1<<(r1+1))-1)).bit_count()
return res
Explain
该题解利用位操作和邻接矩阵的思想求解。首先，通过一个数组 `masks` 构建每个房间的邻接房间的位掩码表示。对于每对房间 (r1, r2)，设置 r1 的位掩码中 r2 位为 1，反之亦然，表示 r1 和 r2 之间有直接连接。接下来，对于每条走廊 (r1, r2)，计算 r1 和 r2 的邻接掩码的位与操作，这可以找出同时与 r1 和 r2 直接相连的房间。通过位操作计算，筛选出介于 r1 和 r2 之间的房间，利用 `bit_count()` 方法计算这些房间的数量，这些房间即为同时与 r1 和 r2 直接相连的房间。
时间复杂度: O(E)
空间复杂度: O(n)
# Class to solve the problem
class Solution:
def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:
# Initialize the masks array to store bit masks of connections
masks = [0]*(n+1)
# Set bits in masks for direct corridors
for r1, r2 in corridors:
masks[r1] |= 1 << r2
masks[r2] |= 1 << r1
# Initialize result counter
res = 0
# Count paths for each corridor
for r1, r2 in corridors:
# Ensure r1 < r2 for consistency
r1, r2 = min(r1, r2), max(r1, r2)
# Calculate common connected rooms between r1 and r2
res += (masks[r1] & masks[r2] & ((1 << r2) - 1) & ~((1 << (r1 + 1)) - 1)).bit_count()
# Return the total count of paths
return res
Explore
位操作相较于列表或字典具有空间效率高和处理速度快的优势。使用位掩码（bitmask）可以将房间的连接状态压缩到整数的单个位上，这样可以用非常紧凑的方式表示大量的布尔信息。每个整数可以表示多达32或64个房间的连接状态（取决于整数的位数），这种方法减少了内存消耗，并且由于位运算（如AND, OR）在现代计算机上非常高效，因此可以提高算法的执行速度。此外，位操作使得比较和计算两个房间的共同邻接房间更为直接和快速。
`masks[r1] & masks[r2]`计算了房间r1和r2共同直接连接的房间的位掩码。`((1 << r2) - 1)`生成一个从位0到位r2-1的掩码，这保证了我们只考虑房间号小于r2的房间。`~((1 << (r1 + 1)) - 1)`生成一个掩码，从位r1+1开始到最高位都是1，这确保我们不考虑房间号小于或等于r1的房间。这样，整个表达式确保我们只计算房间号在r1和r2之间的房间的数量，即只统计位于r1和r2之间的共同直接连接的房间。
`bit_count()`方法是一种计算整数中设置为1的位数（即计算位为1的数量）的方法。在这个上下文中，我们使用`bit_count()`来计算满足特定条件（即同时与两个指定房间直接相连的房间数量）的房间数量。经过位掩码计算后，结果整数中的每个设置为1的位代表一个符合条件的房间，`bit_count()`帮助我们快速统计这些房间的总数，从而确定有多少路径可以连接给定的两个房间。这是解决问题的关键步骤之一，有效利用了位操作的高效处理能力。