LeetCode 题解工作台
按距离统计房屋对数目 I
给你三个 正整数 n 、 x 和 y 。 在城市中，存在编号从 1 到 n 的房屋，由 n 条街道相连。对所有 1 ，都存在一条街道连接编号为 i 的房屋与编号为 i + 1 的房屋。另存在一条街道连接编号为 x 的房屋与编号为 y 的房屋。 对于每个 k （ 1 ），你需要找出所有满足要求的 房屋…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 图·搜索
答案摘要
我们可以枚举每个点对 $(i, j)$，那么从 到 的最短距离为 $min(|i - j|, |i - x| + 1 + |j - y|, |i - y| + 1 + |j - x|)$，我们将该距离的出现次数加 ，因为 $(i, j)$ 和 $(j, i)$ 都是满足要求的点对。 时间复杂度 ，其中 是题目给定的 。忽略答案数组的空间消耗，空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
给你三个 正整数 n 、x 和 y 。
在城市中，存在编号从 1 到 n 的房屋，由 n 条街道相连。对所有 1 <= i < n ，都存在一条街道连接编号为 i 的房屋与编号为 i + 1 的房屋。另存在一条街道连接编号为 x 的房屋与编号为 y 的房屋。
对于每个 k（1 <= k <= n），你需要找出所有满足要求的 房屋对 [house1, house2] ，即从 house1 到 house2 需要经过的 最少 街道数为 k 。
返回一个下标从 1 开始且长度为 n 的数组 result ，其中 result[k] 表示所有满足要求的房屋对的数量，即从一个房屋到另一个房屋需要经过的 最少 街道数为 k 。
注意，x 与 y 可以 相等 。
示例 1：
输入：n = 3, x = 1, y = 3 输出：[6,0,0] 解释：让我们检视每个房屋对 - 对于房屋对 (1, 2)，可以直接从房屋 1 到房屋 2。 - 对于房屋对 (2, 1)，可以直接从房屋 2 到房屋 1。 - 对于房屋对 (1, 3)，可以直接从房屋 1 到房屋 3。 - 对于房屋对 (3, 1)，可以直接从房屋 3 到房屋 1。 - 对于房屋对 (2, 3)，可以直接从房屋 2 到房屋 3。 - 对于房屋对 (3, 2)，可以直接从房屋 3 到房屋 2。
示例 2：
输入：n = 5, x = 2, y = 4 输出：[10,8,2,0,0] 解释：对于每个距离 k ，满足要求的房屋对如下： - 对于 k == 1，满足要求的房屋对有 (1, 2), (2, 1), (2, 3), (3, 2), (2, 4), (4, 2), (3, 4), (4, 3), (4, 5), 以及 (5, 4)。 - 对于 k == 2，满足要求的房屋对有 (1, 3), (3, 1), (1, 4), (4, 1), (2, 5), (5, 2), (3, 5), 以及 (5, 3)。 - 对于 k == 3，满足要求的房屋对有 (1, 5)，以及 (5, 1) 。 - 对于 k == 4 和 k == 5，不存在满足要求的房屋对。
示例 3：
输入：n = 4, x = 1, y = 1 输出：[6,4,2,0] 解释：对于每个距离 k ，满足要求的房屋对如下： - 对于 k == 1，满足要求的房屋对有 (1, 2), (2, 1), (2, 3), (3, 2), (3, 4), 以及 (4, 3)。 - 对于 k == 2，满足要求的房屋对有 (1, 3), (3, 1), (2, 4), 以及 (4, 2)。 - 对于 k == 3，满足要求的房屋对有 (1, 4), 以及 (4, 1)。 - 对于 k == 4，不存在满足要求的房屋对。
提示：
2 <= n <= 1001 <= x, y <= n
解题思路
方法一：枚举
我们可以枚举每个点对 ，那么从 到 的最短距离为 ，我们将该距离的出现次数加 ，因为 和 都是满足要求的点对。
时间复杂度 ，其中 是题目给定的 。忽略答案数组的空间消耗，空间复杂度 。
class Solution:
def countOfPairs(self, n: int, x: int, y: int) -> List[int]:
x, y = x - 1, y - 1
ans = [0] * n
for i in range(n):
for j in range(i + 1, n):
a = j - i
b = abs(i - x) + 1 + abs(j - y)
c = abs(i - y) + 1 + abs(j - x)
ans[min(a, b, c) - 1] += 2
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Focus on BFS to handle graph traversal efficiently.
- question_mark
Recognize the extra street creates shortcut paths impacting minimum distances.
- question_mark
Expect optimization by avoiding repeated full graph scans when counting pairs.
常见陷阱
外企场景- error
Forgetting to count both (house1, house2) and (house2, house1) pairs.
- error
Ignoring the impact of the extra street, which can reduce distances unexpectedly.
- error
Using DFS or naive iteration which misses minimum distance optimization and increases time complexity.
进阶变体
外企场景- arrow_right_alt
Change the extra street to multiple extra streets creating a more complex graph.
- arrow_right_alt
Require counting unordered pairs instead of ordered pairs.
- arrow_right_alt
Increase n to larger values, emphasizing the need for BFS optimization or prefix sum aggregation.