Medium

题目描述

在一个 8 x 8 的棋盘上，有多个黑皇后和一个白国王。

给你一个二维整数数组 queens，其中 queens[i] = [xQueeni, yQueeni] 表示第 i 个黑皇后在棋盘上的位置。还给你一个长度为 2 的整数数组 king，其中 king = [xKing, yKing] 表示白国王的位置。

返回可以直接攻击国王的黑皇后的坐标。你可以按任何顺序返回答案。

示例 1：

输入：queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]
输出：[[0,1],[1,0],[3,3]]
解释：上图显示了三个可以直接攻击国王的皇后和三个无法攻击国王的皇后（用红色虚线标记）。

示例 2：

输入：queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king = [3,3]
输出：[[2,2],[3,4],[4,4]]
解释：上图显示了三个可以直接攻击国王的皇后和三个无法攻击国王的皇后（用红色虚线标记）。

约束条件：

  • 1 <= queens.length < 64
  • queens[i].length == king.length == 2
  • 0 <= xQueeni, yQueeni, xKing, yKing < 8
  • 所有给定的位置都是唯一的

提示：

  • 检查国王周围的 8 个方向
  • 找到每个方向上最近的皇后

解题思路

这道题的关键在于理解皇后的攻击范围：皇后可以在横线、竖线和对角线上攻击任意距离的棋子。

核心思路： 从国王位置出发，向8个方向（上、下、左、右、左上、右上、左下、右下）延伸，找到每个方向上距离国王最近的皇后。只有最近的皇后才能攻击到国王，因为如果有多个皇后在同一条线上，远处的皇后会被近处的皇后阻挡。

算法步骤：

  1. 将所有皇后位置存储在集合中，便于快速查找
  2. 定义8个方向的偏移量：(dx, dy)
  3. 对于每个方向，从国王位置开始，按照该方向逐步移动
  4. 当遇到第一个皇后时，将其加入结果并停止该方向的搜索
  5. 当移出棋盘边界时，停止该方向的搜索

这种方法确保我们只找到每个方向上最近的皇后，时间复杂度为O(1)（因为棋盘大小固定为8x8），空间复杂度为O(queens.length)用于存储皇后位置。

代码实现

class Solution {
public:
    vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {
        set<pair<int, int>> queenSet;
        for (auto& queen : queens) {
            queenSet.insert({queen[0], queen[1]});
        }
        
        vector<vector<int>> result;
        vector<vector<int>> directions = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
        
        for (auto& dir : directions) {
            int x = king[0] + dir[0];
            int y = king[1] + dir[1];
            
            while (x >= 0 && x < 8 && y >= 0 && y < 8) {
                if (queenSet.count({x, y})) {
                    result.push_back({x, y});
                    break;
                }
                x += dir[0];
                y += dir[1];
            }
        }
        
        return result;
    }
};

class Solution:
    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:
        queen_set = set(map(tuple, queens))
        result = []
        directions = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
        
        for dx, dy in directions:
            x, y = king[0] + dx, king[1] + dy
            
            while 0 <= x < 8 and 0 <= y < 8:
                if (x, y) in queen_set:
                    result.append([x, y])
                    break
                x += dx
                y += dy
        
        return result

public class Solution {
    public IList<IList<int>> QueensAttacktheKing(int[][] queens, int[] king) {
        var queenSet = new HashSet<(int, int)>();
        foreach (var queen in queens) {
            queenSet.Add((queen[0], queen[1]));
        }
        
        var result = new List<IList<int>>();
        int[,] directions = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
        
        for (int i = 0; i < directions.GetLength(0); i++) {
            int x = king[0] + directions[i,0];
            int y = king[1] + directions[i,1];
            
            while (x >= 0 && x < 8 && y >= 0 && y < 8) {
                if (queenSet.Contains((x, y))) {
                    result.Add(new List<int>{x, y});
                    break;
                }
                x += directions[i,0];
                y += directions[i,1];
            }
        }
        
        return result;
    }
}

var queensAttacktheKing = function(queens, king) {
    const queenSet = new Set();
    for (const queen of queens) {
        queenSet.add(queen[0] + ',' + queen[1]);
    }
    
    const result = [];
    const directions = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
    
    for (const [dx, dy] of directions) {
        let x = king[0] + dx;
        let y = king[1] + dy;
        
        while (x >= 0 && x < 8 && y >= 0 && y < 8) {
            if (queenSet.has(x + ',' + y)) {
                result.push([x, y]);
                break;
            }
            x += dx;
            y += dy;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(1)棋盘大小固定为8x8，最多检查8个方向，每个方向最多7步
空间复杂度O(n)n为皇后数量，用于存储皇后位置的集合

相关题目