LeetCode 1222. 可以攻击国王的皇后

Categories:

题目描述
思路分析
1. 解法一：八方向扫描（推荐）
相似题目

题目描述

✅ 1222. 可以攻击国王的皇后

思路分析

解法一：八方向扫描（推荐）

核心思路：

先用集合记录所有皇后的位置，便于 O(1) 判断。

从国王位置向 8 个方向逐步前进，遇到第一枚皇后即为可攻击皇后。

每个方向最多走 7 步，总复杂度为常数级。

复杂度分析：

时间复杂度：O(1)，棋盘大小固定 8x8。

空间复杂度：O(1)，最多存储 64 个位置。

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
        Set<Integer> set = new HashSet<>();
        for (int[] q : queens) {
            set.add(q[0] * 8 + q[1]);
        }

        int[][] dirs = {
                {-1, -1}, {-1, 0}, {-1, 1},
                {0, -1}, {0, 1},
                {1, -1}, {1, 0}, {1, 1}
        };

        List<List<Integer>> res = new ArrayList<>();
        for (int[] d : dirs) {
            int x = king[0] + d[0];
            int y = king[1] + d[1];
            while (x >= 0 && x < 8 && y >= 0 && y < 8) {
                if (set.contains(x * 8 + y)) {
                    List<Integer> pos = new ArrayList<>(2);
                    pos.add(x);
                    pos.add(y);
                    res.add(pos);
                    break;
                }
                x += d[0];
                y += d[1];
            }
        }
        return res;
    }
}

func queensAttacktheKing(queens [][]int, king []int) [][]int {
    set := make(map[int]struct{})
    for _, q := range queens {
        set[q[0]*8+q[1]] = struct{}{}
    }

    dirs := [][]int{
        {-1, -1}, {-1, 0}, {-1, 1},
        {0, -1}, {0, 1},
        {1, -1}, {1, 0}, {1, 1},
    }

    res := make([][]int, 0)
    for _, d := range dirs {
        x := king[0] + d[0]
        y := king[1] + d[1]
        for x >= 0 && x < 8 && y >= 0 && y < 8 {
            if _, ok := set[x*8+y]; ok {
                res = append(res, []int{x, y})
                break
            }
            x += d[0]
            y += d[1]
        }
    }
    return res
}

相似题目

题目	难度	考察点
51. N 皇后	困难	回溯、约束
52. N 皇后 II	困难	回溯
36. 有效的数独	中等	哈希表
37. 解数独	困难	回溯
999. 可以被一步捕获的棋子数	简单	棋盘扫描

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/82536159