LeetCode 题解工作台
可以攻击国王的皇后
在一个 下标从 0 开始 的 8 x 8 棋盘上，可能有多个黑皇后和一个白国王。 给你一个二维整数数组 queens ，其中 queens[i] = [xQueeni, yQueeni] 表示第 i 个黑皇后在棋盘上的位置。还给你一个长度为 2 的整数数组 king ，其中 king = [xKin…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·matrix
答案摘要
我们先将所有皇后的位置存入哈希表或者二维数组 中。 接下来，我们从国王的位置开始，依次向上、下、左、右、左上、右上、左下、右下八个方向搜索，如果某个方向上存在皇后，那么就将其位置加入答案中，并且停止继续搜索该方向。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·matrix 题型思路
题目描述
在一个 下标从 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 < 64queens[i].length == king.length == 20 <= xQueeni, yQueeni, xKing, yKing < 8- 所有给定的位置都是 唯一 的。
解题思路
方法一：直接搜索
我们先将所有皇后的位置存入哈希表或者二维数组 中。
接下来，我们从国王的位置开始，依次向上、下、左、右、左上、右上、左下、右下八个方向搜索，如果某个方向上存在皇后，那么就将其位置加入答案中，并且停止继续搜索该方向。
搜索结束后，返回答案即可。
时间复杂度 ，空间复杂度 。本题中 。
class Solution:
def queensAttacktheKing(
self, queens: List[List[int]], king: List[int]
) -> List[List[int]]:
n = 8
s = {(i, j) for i, j in queens}
ans = []
for a in range(-1, 2):
for b in range(-1, 2):
if a or b:
x, y = king
while 0 <= x + a < n and 0 <= y + b < n:
x, y = x + a, y + b
if (x, y) in s:
ans.append([x, y])
break
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(64) since each of the eight directions can cover at most 8 squares, and lookup in a set is O(1). Space complexity is O(N) for storing the queen positions in a set, where N is the number of queens. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate should quickly identify eight directions from the king.
- question_mark
Look for correct handling of blocked paths by other queens.
- question_mark
Expect usage of sets for efficient position lookup.
常见陷阱
外企场景- error
Forgetting to stop scanning after the first queen in a direction.
- error
Confusing row and column indices when scanning diagonals.
- error
Attempting to check all queens against the king without direction pruning, causing inefficiency.
进阶变体
外企场景- arrow_right_alt
Return only queens attacking from rows and columns, ignoring diagonals.
- arrow_right_alt
Chessboard size can be generalized beyond 8x8, requiring dynamic bounds checking.
- arrow_right_alt
Include multiple kings and determine attacking queens for each.