Medium

题目描述

给你三个正整数 n、x 和 y。

在一个城市中，存在编号从 1 到 n 的房屋，由 n 条街道相连。对于所有 1 <= i <= n - 1，都有一条街道连接编号为 i 的房屋与编号为 i + 1 的房屋。另外还有一条街道连接编号为 x 的房屋与编号为 y 的房屋。

对于每个 k（1 <= k <= n），你需要找到满足以下条件的房屋对 (house1, house2) 的数量：从 house1 到达 house2 需要经过的最少街道数为 k。

返回一个长度为 n 的 1 索引 数组 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 <= 100
  • 1 <= x, y <= n

解题思路

解题思路

这道题需要计算图中任意两个房屋间的最短距离。由于房屋编号连续且有额外的连接边，我们需要建立图并计算所有点对的最短路径。

方法一：BFS（推荐）

从每个房屋出发，使用BFS计算到其他所有房屋的最短距离。这种方法直观易懂，时间复杂度可接受。

具体步骤：

  1. 构建邻接表表示图：相邻房屋相连，额外添加x和y的连接
  2. 对每个房屋执行BFS，计算到其他房屋的距离
  3. 统计每种距离的房屋对数量

方法二：Floyd-Warshall算法

使用动态规划计算所有点对最短路径，适合稠密图。由于n最大为100，O(n³)的复杂度完全可接受。

方法三：数学分析

由于图的特殊结构（线性排列+一条额外边），可以通过数学方法直接计算距离分布，但实现较复杂。

考虑到代码简洁性和可读性，推荐使用BFS方法。

代码实现

class Solution {
public:
    vector<int> countOfPairs(int n, int x, int y) {
        // 构建邻接表
        vector<vector<int>> graph(n + 1);
        for (int i = 1; i < n; i++) {
            graph[i].push_back(i + 1);
            graph[i + 1].push_back(i);
        }
        if (x != y) {
            graph[x].push_back(y);
            graph[y].push_back(x);
        }
        
        vector<int> result(n, 0);
        
        // 从每个房屋出发进行BFS
        for (int start = 1; start <= n; start++) {
            vector<int> dist(n + 1, -1);
            queue<int> q;
            q.push(start);
            dist[start] = 0;
            
            while (!q.empty()) {
                int curr = q.front();
                q.pop();
                
                for (int next : graph[curr]) {
                    if (dist[next] == -1) {
                        dist[next] = dist[curr] + 1;
                        q.push(next);
                    }
                }
            }
            
            // 统计距离
            for (int end = 1; end <= n; end++) {
                if (start != end && dist[end] > 0) {
                    result[dist[end] - 1]++;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:
        from collections import deque, defaultdict
        
        # 构建邻接表
        graph = defaultdict(list)
        for i in range(1, n):
            graph[i].append(i + 1)
            graph[i + 1].append(i)
        
        if x != y:
            graph[x].append(y)
            graph[y].append(x)
        
        result = [0] * n
        
        # 从每个房屋出发进行BFS
        for start in range(1, n + 1):
            dist = [-1] * (n + 1)
            queue = deque([start])
            dist[start] = 0
            
            while queue:
                curr = queue.popleft()
                
                for next_house in graph[curr]:
                    if dist[next_house] == -1:
                        dist[next_house] = dist[curr] + 1
                        queue.append(next_house)
            
            # 统计距离
            for end in range(1, n + 1):
                if start != end and dist[end] > 0:
                    result[dist[end] - 1] += 1
        
        return result

public class Solution {
    public int[] CountOfPairs(int n, int x, int y) {
        // 构建邻接表
        var graph = new List<int>[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new List<int>();
        }
        
        for (int i = 1; i < n; i++) {
            graph[i].Add(i + 1);
            graph[i + 1].Add(i);
        }
        
        if (x != y) {
            graph[x].Add(y);
            graph[y].Add(x);
        }
        
        int[] result = new int[n];
        
        // 从每个房屋出发进行BFS
        for (int start = 1; start <= n; start++) {
            int[] dist = new int[n + 1];
            Array.Fill(dist, -1);
            var queue = new Queue<int>();
            queue.Enqueue(start);
            dist[start] = 0;
            
            while (queue.Count > 0) {
                int curr = queue.Dequeue();
                
                foreach (int next in graph[curr]) {
                    if (dist[next] == -1) {
                        dist[next] = dist[curr] + 1;
                        queue.Enqueue(next);
                    }
                }
            }
            
            // 统计距离
            for (int end = 1; end <= n; end++) {
                if (start != end && dist[end] > 0) {
                    result[dist[end] - 1]++;
                }
            }
        }
        
        return result;
    }
}

var countOfPairs = function(n, x, y) {
    const result = new Array(n).fill(0);
    
    // Calculate shortest distance between all pairs
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= n; j++) {
            if (i === j) continue;
            
            // Distance without using x-y edge
            const normalDist = Math.abs(i - j);
            
            // Distance using x-y edge (if x !== y)
            let shortcutDist = Infinity;
            if (x !== y) {
                shortcutDist = Math.min(
                    Math.abs(i - x) + 1 + Math.abs(j - y),
                    Math.abs(i - y) + 1 + Math.abs(j - x)
                );
            }
            
            const minDist = Math.min(normalDist, shortcutDist);
            result[minDist - 1]++;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度BFS解法
时间复杂度O(n²)
空间复杂度O(n)

时间复杂度分析：

  • 对每个房屋执行BFS：O(n)次
  • 每次BFS遍历所有边：O(n)条边
  • 总时间复杂度：O(n²)

空间复杂度分析：

  • 邻接表存储：O(n)
  • BFS队列和距离数组：O(n)
  • 总空间复杂度：O(n)

相关题目