526互联

[LeetCode] 1222. Queens That Can Attack the King

发布时间 2023-09-16 05:18:23作者: CNoodle

On a 0-indexed 8 x 8 chessboard, there can be multiple black queens ad one white king.

You are given a 2D integer array queens where queens[i] = [xQueeni, yQueeni] represents the position of the ith black queen on the chessboard. You are also given an integer array king of length 2 where king = [xKing, yKing] represents the position of the white king.

Return the coordinates of the black queens that can directly attack the king. You may return the answer in any order.

Example 1:

Input: queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]
Output: [[0,1],[1,0],[3,3]]
Explanation: The diagram above shows the three queens that can directly attack the king and the three queens that cannot attack the king (i.e., marked with red dashes).

Example 2:

Input: queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king = [3,3]
Output: [[2,2],[3,4],[4,4]]
Explanation: The diagram above shows the three queens that can directly attack the king and the three queens that cannot attack the king (i.e., marked with red dashes).

Constraints:

  • 1 <= queens.length < 64
  • queens[i].length == king.length == 2
  • 0 <= xQueeni, yQueeni, xKing, yKing < 8
  • All the given positions are unique.

可以攻击国王的皇后。

在一个 8x8 的棋盘上，放置着若干「黑皇后」和一个「白国王」。

给定一个由整数坐标组成的数组 queens ，表示黑皇后的位置；以及一对坐标 king ，表示白国王的位置，返回所有可以攻击国王的皇后的坐标(任意顺序)。

又是一道在棋盘上的模拟题。注意题目要求，需要返回的是在与国王分别在同一行，同一列，同一条对角线上的能最先攻击到国王的皇后的坐标。有几个地方题目没有点出，比如在同一行（同一列或者同一条对角线也是同理）上，国王的左边和右边各有一个与国王距离相等的皇后，那么这两个皇后都需要被记录。

具体做法是我先用一个二维 boolean 数组记录棋盘上所有皇后的位置，标记为 true。然后从国王的位置开始，往八个方向延伸（这是皇后能走的方向），在每个方向上只要遇到皇后就停下并把皇后的坐标加入结果集。

时间O(1) - 8x8

空间O(1) - 8x8

Java实现

 1 class Solution {
 2     public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
 3         List<List<Integer>> res = new ArrayList<>();
 4         boolean[][] board = new boolean[8][8];
 5         for (int[] q : queens) {
 6             int qx = q[0];
 7             int qy = q[1];
 8             board[qx][qy] = true;
 9         }
10 
11         int[][] dirs = new int[][] {{-1, 0}, {-1, 1}, {-1, -1}, {0, 1}, {0, -1}, {1, 0}, {1, 1}, {1, -1}};
12         for (int[] dir : dirs) {
13             int x = king[0] + dir[0];
14             int y = king[1] + dir[1];
15             while (x >= 0 && x < 8 && y >= 0 && y < 8) {
16                 if (board[x][y] == true) {
17                     res.add(Arrays.asList(x, y));
18                     break;
19                 }
20                 x += dir[0];
21                 y += dir[1];
22             }
23         }
24         return res;
25     }
26 }

 

LeetCode 题目总结