可以攻击国王的皇后
难度:
标签:
题目描述
在一个 下标从 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 <= xQueeni, yQueeni, xKing, yKing < 8
- 所有给定的位置都是 唯一 的。
代码结果
运行时间: 22 ms, 内存: 16.2 MB
// 思路:
// 使用流式处理将棋盘上的所有可能路径简化为一个可迭代的流。
// 使用坐标来过滤能攻击国王的皇后。
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class QueensAttackKingStream {
public List<int[]> queensAttacktheKing(int[][] queens, int[] king) {
boolean[][] board = new boolean[8][8];
for (int[] queen : queens) {
board[queen[0]][queen[1]] = true;
}
int[][] directions = {
{0, 1}, {1, 0}, {0, -1}, {-1, 0},
{1, 1}, {1, -1}, {-1, 1}, {-1, -1}
};
return Stream.of(directions)
.flatMap(direction -> {
int x = king[0];
int y = king[1];
while (x >= 0 && x < 8 && y >= 0 && y < 8) {
x += direction[0];
y += direction[1];
if (x >= 0 && x < 8 && y >= 0 && y < 8 && board[x][y]) {
return Stream.of(new int[]{x, y});
}
}
return Stream.empty();
})
.collect(Collectors.toList());
}
}
解释
方法:
这道题的思路是首先将所有皇后的位置存储在一个集合中,以便于快速查找。然后,从国王的位置出发,沿着八个可能的方向(上、下、左、右、四个对角线方向)探索,直到遇到棋盘边界或者遇到一个皇后。如果在某个方向上遇到了皇后,那么这个皇后就可以攻击到国王,将其坐标加入结果列表中。最后返回结果列表。
时间复杂度:
O(1)
空间复杂度:
O(1)
代码细节讲解
🦆
如何确定每个方向上的第一个皇后是可以攻击国王的,而不是被其他皇后阻挡?
▷🦆
在循环搜索各个方向时,为什么在找到一个可以攻击国王的皇后后就停止继续搜索那个方向?
▷🦆
为什么在`visited`集合中存储皇后的位置而不是直接在列表中迭代查找?
▷🦆
在处理边界条件时(棋盘的边缘),代码是如何确保不会超出棋盘范围的?
▷