leetcode
leetcode 1151 ~ 1200
可以攻击国王的皇后

可以攻击国王的皇后

难度:

标签:

题目描述

在一个 下标从 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`集合中存储皇后的位置而不是直接在列表中迭代查找?
使用`visited`集合存储皇后的位置可以大大提高查找效率。集合(在Python中通常实现为哈希表)提供平均时间复杂度为O(1)的成员查找性能,这比在列表中逐个迭代查找(平均时间复杂度为O(n))要快得多。这意味着当在每个方向上搜索皇后时,能够更快地确定某个位置是否有皇后存在。
🦆
在处理边界条件时(棋盘的边缘),代码是如何确保不会超出棋盘范围的?
代码中使用了一个循环,并在循环中检查当前坐标`(x, y)`是否仍在棋盘的有效范围内(即`0 <= x < 8`和`0 <= y < 8`)。只有当坐标在这个范围内时,才会继续沿着当前方向搜索。这种检查确保了搜索不会超出棋盘的边缘,从而防止了数组越界的错误。

相关问题