可以攻击国王的皇后

难度: Medium

在一个 下标从 0 开始 的 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 <= xQueen_i, yQueen_i, xKing, yKing < 8
所有给定的位置都是唯一的。

Submission

运行时间: 22 ms

内存: 16.2 MB

class Solution:
    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
        result = []
        
        # Mark all queen positions as visited
        visited = set()
        for queen in queens:
            visited.add((queen[0], queen[1]))
        
        # Check each direction from the king's position
        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 visited:
                    result.append([x, y])
                    break
                x += dx
                y += dy
        
        return result

Explain

这道题的思路是首先将所有皇后的位置存储在一个集合中，以便于快速查找。然后，从国王的位置出发，沿着八个可能的方向（上、下、左、右、四个对角线方向）探索，直到遇到棋盘边界或者遇到一个皇后。如果在某个方向上遇到了皇后，那么这个皇后就可以攻击到国王，将其坐标加入结果列表中。最后返回结果列表。

时间复杂度: O(1)

空间复杂度: O(1)

class Solution:
    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
        result = []
        
        # Mark all queen positions as visited
        visited = set()
        for queen in queens:
            visited.add((queen[0], queen[1]))
        
        # Check each direction from the king's position
        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 visited:
                    result.append([x, y])
                    break
                x += dx
                y += dy
        
        return result

Explore

在给定的方向上，代码从国王的位置开始，沿着该方向逐格检查，直到遇到第一个皇后或者到达棋盘边界。在这个过程中，由于是按照方向一格一格地移动，并记录第一个遇到的皇后位置，这确保了在该方向上第一个遇到的皇后是可以攻击国王的。因为在棋盘的每个方向上，皇后的攻击是线性的，所以第一个遇到的皇后之后的任何皇后都会被前面的皇后阻挡。

在国际象棋中，皇后可以攻击同一行、列或对角线上的任何位置。因此，一旦在某一方向上找到第一个皇后，该方向上国王之后的任何位置都会被这个皇后直接攻击，没有必要继续搜索该方向，因为在同一方向上的其他位置被第一个皇后阻挡了。

使用`visited`集合存储皇后的位置可以大大提高查找效率。集合（在Python中通常实现为哈希表）提供平均时间复杂度为O(1)的成员查找性能，这比在列表中逐个迭代查找（平均时间复杂度为O(n)）要快得多。这意味着当在每个方向上搜索皇后时，能够更快地确定某个位置是否有皇后存在。

代码中使用了一个循环，并在循环中检查当前坐标`(x, y)`是否仍在棋盘的有效范围内（即`0 <= x < 8`和`0 <= y < 8`）。只有当坐标在这个范围内时，才会继续沿着当前方向搜索。这种检查确保了搜索不会超出棋盘的边缘，从而防止了数组越界的错误。