想要精通算法和SQL的成长之路 - 可以攻击国王的皇后

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 可以攻击国王的皇后

原题链接

这个题目其实并没有涉及到什么很难的算法，其实就是一个简单的遍历题目。核心思想：

• 以国王为起点，分别向8个方向遍历数组。
• 遍历终止条件：遇到第一个皇后，或者下标越界。

问题是，我们如何编写代码，让代码更加简洁呢？总不会写8个for循环吧？我们可以这样：

1. 我们可以发现，我们8个方向的遍历起始位置（不算国王本身），一共8个，正好绕了国王一圈，如下图的红色框框部分。
2. 我们朝8个方向分别移动，正好每次移动的横纵坐标，都要加上下图的8个下标组：(-1,-1)、(-1,0)…等等

如图：

同时，这8个下标分别加上国王的下标，就分别是8个方向的起始搜索点。因此我们用一个二维数组代表这8个下标组：

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

同时，我们用一个二维数组isQueen来标识当前位置是否为皇后：

// 1.先构建二维数组，标识皇后是否存在
boolean[][] isQueen = new boolean[8][8];
for (int[] queen : queens) {
    isQueen[queen[0]][queen[1]] = true;
}
1
2
3
4
5

然后对8个方向分别搜索：

for (int[] direction : directions) {
    // 当前方向的起始搜索点的横纵坐标 (x,y)
    int x = king[0] + direction[0];
    int y = king[1] + direction[1];
    // 开始循环，条件是不能越界
    while (x >= 0 && x < 8 && y >= 0 && y < 8) {
        // 如果找到了皇后，直接把他加入结果集，并终止本次循环
        if (isQueen[x][y]) {
            res.add(Arrays.asList(x, y));
            break;
        }
        // 更新下标，继续朝相同方向前进
        x += direction[0];
        y += direction[1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

最终代码如下：

public class Test1222 {
    public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
        // 1.先构建二维数组，标识皇后是否存在
        boolean[][] isQueen = new boolean[8][8];
        for (int[] queen : queens) {
            isQueen[queen[0]][queen[1]] = true;
        }
        List<List<Integer>> res = new ArrayList<>();

        // 2.从king的位置，分别朝8个方向搜索。我们构建一个具有8个方向起始位置的数组.King的坐标分别加上下面的坐标，就是King旁那一圈的起始点
        int[][] directions = {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};
        for (int[] direction : directions) {
            // 当前方向的起始搜索点的横纵坐标 (x,y)
            int x = king[0] + direction[0];
            int y = king[1] + direction[1];
            // 开始循环，条件是不能越界
            while (x >= 0 && x < 8 && y >= 0 && y < 8) {
                // 如果找到了皇后，直接把他加入结果集，并终止本次循环
                if (isQueen[x][y]) {
                    res.add(Arrays.asList(x, y));
                    break;
                }
                // 更新下标，继续朝相同方向前进
                x += direction[0];
                y += direction[1];
            }
        }

        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31