On an 8×8 chessboard, there can be multiple Black Queens and one White King.
Given an array of integer coordinates queens
that represents the positions of the Black Queens, and a pair of coordinates king
that represent the position of the White King, return the coordinates of all the queens (in any order) that can attack the King.
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 queen at [0,1] can attack the king cause they're in the same row. The queen at [1,0] can attack the king cause they're in the same column. The queen at [3,3] can attack the king cause they're in the same diagnal. The queen at [0,4] can't attack the king cause it's blocked by the queen at [0,1]. The queen at [4,0] can't attack the king cause it's blocked by the queen at [1,0]. The queen at [2,4] can't attack the king cause it's not in the same row/column/diagnal as the king.
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]]
Example 3:
Input: queens = [[5,6],[7,7],[2,1],[0,7],[1,6],[5,1],[3,7],[0,3],[4,0],[1,2],[6,3],[5,0],[0,4],[2,2],[1,1],[6,4],[5,4],[0,0],[2,6],[4,5],[5,2],[1,4],[7,5],[2,3],[0,5],[4,2],[1,0],[2,7],[0,1],[4,6],[6,1],[0,6],[4,3],[1,7]], king = [3,4] Output: [[2,3],[1,4],[1,6],[3,7],[4,3],[5,4],[4,5]]
Constraints:
1 <= queens.length <= 63
queens[0].length == 2
0 <= queens[i][j] < 8
king.length == 2
0 <= king[0], king[1] < 8
- At most one piece is allowed in a cell.
Solution2: Simulation
Time complexity: O(n)
Space complexity: O(1)
C++
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 |
// Author: Huahua class Solution { public: vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) { vector<vector<int>> b(8, vector<int>(8)); for (const auto& q : queens) b[q[0]][q[1]] = 1; vector<vector<int>> ans; for (const auto& q : queens) { for (int dx = -1; dx <= 1; ++dx) for (int dy = -1; dy <= 1; ++dy) { if (dx == 0 && dy == 0) continue; int x = q[1] + dx; int y = q[0] + dy; while (x >= 0 && y >= 0 && x < 8 && y < 8 && !b[y][x]) { if (x == king[1] && y == king[0]) ans.push_back(q); x += dx; y += dy; } } } return ans; } }; |
Solution 2: HashTable + Binary Search
Time complexity: O(nlogn)
Space complexity: O(n)
Support arbitrarily large boards, e.g. 1e9 x 1e9 with 1e6 # of queens.
C++
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 32 33 34 |
// Author: Huahua class Solution { public: vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) { unordered_map<int, map<int, vector<int>>> rows, cols, diag1, diag2; for (const auto& q : queens) { const int x = q[1]; const int y = q[0]; rows[y][x] = q; cols[x][y] = q; diag1[x + y][x] = q; diag2[x - y][x] = q; } const int x = king[1]; const int y = king[0]; vector<vector<int>> ans; find(rows, y, x, ans); find(cols, x, y, ans); find(diag1, x + y, x, ans); find(diag2, x - y, x, ans); return ans; } private: void find(const unordered_map<int, map<int, vector<int>>>& m, int idx, int key, vector<vector<int>>& ans) { if (!m.count(idx)) return; const auto& d = m.at(idx); auto it = d.upper_bound(key); if (it != end(d)) ans.push_back(it->second); if (it != begin(d)) ans.push_back(prev(it)->second); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment