LeetCode 题解工作台
按距离统计房屋对数目 II
给你三个 正整数 n 、 x 和 y 。 在城市中，存在编号从 1 到 n 的房屋，由 n 条街道相连。对所有 1 ，都存在一条街道连接编号为 i 的房屋与编号为 i + 1 的房屋。另存在一条街道连接编号为 x 的房屋与编号为 y 的房屋。 对于每个 k （ 1 ），你需要找出所有满足要求的 房屋…
2
题型
4
代码语言
3
相关题
当前训练重点
困难 · 前缀和
答案摘要
class Solution: def countOfPairs(self, n: int, x: int, y: int) -> List[int]:
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 <= 1051 <= x, y <= n
解题思路
方法一
class Solution:
def countOfPairs(self, n: int, x: int, y: int) -> List[int]:
if abs(x - y) <= 1:
return [2 * x for x in reversed(range(n))]
cycle_len = abs(x - y) + 1
n2 = n - cycle_len + 2
res = [2 * x for x in reversed(range(n2))]
while len(res) < n:
res.append(0)
res2 = [cycle_len * 2] * (cycle_len >> 1)
if not cycle_len & 1:
res2[-1] = cycle_len
res2[0] -= 2
for i in range(len(res2)):
res[i] += res2[i]
if x > y:
x, y = y, x
tail1 = x - 1
tail2 = n - y
for tail in (tail1, tail2):
if not tail:
continue
i_mx = tail + (cycle_len >> 1)
val_mx = 4 * min((cycle_len - 3) >> 1, tail)
i_mx2 = i_mx - (1 - (cycle_len & 1))
res3 = [val_mx] * i_mx
res3[0] = 0
res3[1] = 0
if not cycle_len & 1:
res3[-1] = 0
for i, j in enumerate(range(4, val_mx, 4)):
res3[i + 2] = j
res3[i_mx2 - i - 1] = j
for i in range(1, tail + 1):
res3[i] += 2
if not cycle_len & 1:
mn = cycle_len >> 1
for i in range(mn, mn + tail):
res3[i] += 2
for i in range(len(res3)):
res[i] += res3[i]
return res
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for a clear understanding of graph traversal and its integration with prefix sums.
- question_mark
Evaluate the candidate's ability to handle edge cases, especially the influence of the additional street.
- question_mark
Check if the candidate can optimize their approach to avoid unnecessary recalculations.
常见陷阱
外企场景- error
Ignoring the impact of the additional street between houses x and y, which can alter the pair distances.
- error
Incorrectly handling edge cases where there are no valid pairs for certain distances.
- error
Failing to optimize the approach to handle larger inputs within the problem's constraints.
进阶变体
外企场景- arrow_right_alt
Modify the problem to ask for the number of pairs at exactly k distance for a given subset of houses.
- arrow_right_alt
Extend the problem to handle multiple additional streets between different pairs of houses.
- arrow_right_alt
Change the problem to ask for the distance between a specific pair of houses, rather than counting all pairs.