前言

想要精通算法和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}};

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

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

然后对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];}
}

最终代码如下：

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;}
}