可以攻击国王的皇后【LC1222】
在一个 8x8 的棋盘上，放置着若干「黑皇后」和一个「白国王」。
给定一个由整数坐标组成的数组
queens，表示黑皇后的位置；以及一对坐标king，表示白国王的位置，返回所有可以攻击国王的皇后的坐标(任意顺序)。
- 思路
- 将Queen的坐标一维化，记录在哈希表中
- 从King出发，寻找8个方向中第一个Queen的位置
- 实现
class Solution { public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) { List<List<Integer>> res = new ArrayList<>(); int[][] dirs = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}; int N = 8; Set<Integer> set = new HashSet<>(); for (int[] q : queens){ set.add(q[0] * N + q[1]); } for (int i = 0; i < 8; i++){ int x = king[0] + dirs[i][0], y = king[1] + dirs[i][1]; while (x >= 0 && x < N && y >= 0 && y < N){ if (set.contains(x * N + y)){ res.add(Arrays.asList(x, y)); break; } x += dirs[i][0]; y += dirs[i][1]; } } return res; } }
