rust 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2023-09-14 07:39:57

impl Solution {
    // 从king的8个方向模拟
    pub fn queens_attackthe_king(queens: Vec<Vec<i32>>, king: Vec<i32>) -> Vec<Vec<i32>> {
        use std::collections::HashSet;
        let queens: HashSet<_> = queens.into_iter().map(|q| (q[0], q[1])).collect();
        let dir = [
            (-1, 0),
            (-1, -1),
            (0, -1),
            (1, -1),
            (1, 0),
            (1, 1),
            (0, 1),
            (-1, 1),
        ];
        let mut ans = vec![];
        for &d in dir.iter() {
            let mut cur = (king[0], king[1]);
            while cur.0 >= 0 && cur.0 < 8 && cur.1 >= 0 && cur.1 < 8 {
                if queens.contains(&cur) {
                    ans.push(vec![cur.0, cur.1]);
                    break;
                }
                cur.0 += d.0;
                cur.1 += d.1;
            }
        }
        ans
    }

    pub fn queens_attackthe_king2(queens: Vec<Vec<i32>>, king: Vec<i32>) -> Vec<Vec<i32>> {
        let mut ret = Vec::new();
        let dir = vec![(-1, 0, king[0]),
                       (0, -1, king[1]),
                       (1, 0, 7 - king[0]),
                       (0, 1, 7 - king[1]),
                       (-1, 1, king[0].min(7 - king[1])),
                       (1, -1, king[1].min(7 - king[0])),
                       (-1, -1, king[0].min(king[1])),
                       (1, 1, 7 - king[0].max(king[1]))];

        for (a, b, c) in dir {
            for i in 1..=c {
                if queens.contains(&vec![king[0] + a * i, king[1] + b * i]) {
                    ret.push(vec![king[0] + a * i, king[1] + b * i]);
                    break;
                }
            }
        }

        ret
    }
}

javascript 解法, 执行用时: 60 ms, 内存消耗: 42.3 MB, 提交时间: 2023-09-14 07:37:56

/**
 * @param {number[][]} queens
 * @param {number[]} king
 * @return {number[][]}
 */
var queensAttacktheKing = function(queens, king) { // 从国王出发
    queen_pos = new Set();
    for (const queen of queens) {
        let x = queen[0], y = queen[1];
        queen_pos.add(x * 8 + y);
    }

    const ans = [];
    for (let dx = -1; dx <= 1; ++dx) {
        for (let dy = -1; dy <= 1; ++dy) {
            if (dx == 0 && dy == 0) {
                continue;
            }
            let kx = king[0] + dx, ky = king[1] + dy;
            while (kx >= 0 && kx < 8 && ky >= 0 && ky < 8) {
                let pos = kx * 8 + ky;
                if (queen_pos.has(pos)) {
                    ans.push([kx, ky]);
                    break;
                }
                kx += dx;
                ky += dy;
            }
        }
    }
    return ans;
};

/**
 * @param {number[][]} queens
 * @param {number[]} king
 * @return {number[][]}
 */
var queensAttacktheKing2 = function(queens, king) { // 从皇后出发
    const sgn = function(x) {
        return x > 0 ? 1 : (x == 0 ? 0 : -1);
    }

    const candidates = new Map();
    const kx = king[0], ky = king[1];
    for (const queen of queens) {
        let qx = queen[0], qy = queen[1];
        let x = qx - kx, y = qy - ky;
        if (x == 0 || y == 0 || Math.abs(x) == Math.abs(y)) {
            let dx = sgn(x), dy = sgn(y);
            const key = dx * 10 + dy;
            if (!candidates.has(key) || candidates.get(key)[2] > Math.abs(x) + Math.abs(y)) {
                candidates.set(key, [qx, qy, Math.abs(x) + Math.abs(y)]);
            }
        }
    }

    const ans = [];
    for (let value of candidates.values()) {
        ans.push([value[0], value[1]]);
    }
    return ans;
};

golang 解法, 执行用时: 0 ms, 内存消耗: 2.4 MB, 提交时间: 2023-09-14 07:36:36

// 从国王出发
func queensAttacktheKing(queens [][]int, king []int) [][]int {
    queen_pos := make(map[int]bool)
    for _, queen := range queens {
        x, y := queen[0], queen[1]
        queen_pos[x * 8 + y] = true
    }
        
    ans := [][]int{}
    for dx := -1; dx <= 1; dx++ {
        for dy := -1; dy <= 1; dy++ {
            if dx == 0 && dy == 0 {
                continue
            }
            kx, ky := king[0] + dx, king[1] + dy
            for kx >= 0 && kx < 8 && ky >= 0 && ky < 8 {
                pos := kx * 8 + ky
                if _, ok := queen_pos[pos]; ok {
                    ans = append(ans, []int{kx, ky})
                    break
                }
                kx += dx
                ky += dy
            }
        }
    }
    return ans
}

// 从皇后出发
func queensAttacktheKing2(queens [][]int, king []int) [][]int {
    var sgn = func(x int) int {
        if x > 0 {
            return 1
        } else if x == 0 {
            return 0
        } else {
            return -1
        }
    }

    var abs = func(x int) int {
        if x < 0 {
            return -x
        }
        return x
    }

    candidates := make(map[int][]int)
    kx, ky := king[0], king[1]
    for _, queen := range queens {
        qx, qy := queen[0], queen[1]
        x, y := qx - kx, qy - ky
        if x == 0 || y == 0 || abs(x) == abs(y) {
            dx, dy := sgn(x), sgn(y)
            key := dx * 10 + dy
            if val, ok := candidates[key]; !ok || val[2] > abs(x) + abs(y) {
                candidates[key] = []int{qx, qy, abs(x) + abs(y)}
            }
        }
    }

    ans := [][]int{}
    for _, value := range candidates {
        ans = append(ans, []int{value[0], value[1]})
    }
    return ans
}

java 解法, 执行用时: 1 ms, 内存消耗: 40.7 MB, 提交时间: 2023-09-14 07:35:20

class Solution {
    // 从国王出发
    public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
        Set<Integer> queenPos = new HashSet<Integer>();
        for (int[] queen : queens) {
            int x = queen[0], y = queen[1];
            queenPos.add(x * 8 + y);
        }

        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        for (int dx = -1; dx <= 1; ++dx) {
            for (int dy = -1; dy <= 1; ++dy) {
                if (dx == 0 && dy == 0) {
                    continue;
                }
                int kx = king[0] + dx, ky = king[1] + dy;
                while (kx >= 0 && kx < 8 && ky >= 0 && ky < 8) {
                    int pos = kx * 8 + ky;
                    if (queenPos.contains(pos)) {
                        List<Integer> posList = new ArrayList<Integer>();
                        posList.add(kx);
                        posList.add(ky);
                        ans.add(posList);
                        break;
                    }
                    kx += dx;
                    ky += dy;
                }
            }
        }
        return ans;
    }

    // 从皇后出发
    public List<List<Integer>> queensAttacktheKing2(int[][] queens, int[] king) {
        Map<Integer, int[]> candidates = new HashMap<Integer, int[]>();
        int kx = king[0], ky = king[1];
        for (int[] queen : queens) {
            int qx = queen[0], qy = queen[1];
            int x = qx - kx, y = qy - ky;
            if (x == 0 || y == 0 || Math.abs(x) == Math.abs(y)) {
                int dx = sgn(x), dy = sgn(y);
                int key = dx * 10 + dy;
                if (!candidates.containsKey(key) || candidates.get(key)[2] > Math.abs(x) + Math.abs(y)) {
                    candidates.put(key, new int[]{queen[0], queen[1], Math.abs(x) + Math.abs(y)});
                }
            }
        }

        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        for (Map.Entry<Integer, int[]> entry : candidates.entrySet()) {
            int[] value = entry.getValue();
            List<Integer> posList = new ArrayList<Integer>();
            posList.add(value[0]);
            posList.add(value[1]);
            ans.add(posList);
        }
        return ans;
    }

    public int sgn(int x) {
        return x > 0 ? 1 : (x == 0 ? 0 : -1);
    }
}

cpp 解法, 执行用时: 4 ms, 内存消耗: 11.2 MB, 提交时间: 2023-09-14 07:33:54

class Solution {
public:
    // 从国王出发
    vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {
        unordered_set<int> queen_pos;
        for (const auto& queen: queens) {
            int x = queen[0], y = queen[1];
            queen_pos.insert(x * 8 + y);
        }

        vector<vector<int>> ans;
        for (int dx = -1; dx <= 1; ++dx) {
            for (int dy = -1; dy <= 1; ++dy) {
                if (dx == 0 && dy == 0) {
                    continue;
                }
                int kx = king[0] + dx, ky = king[1] + dy;
                while (kx >= 0 && kx < 8 && ky >= 0 && ky < 8) {
                    int pos = kx * 8 + ky;
                    if (queen_pos.count(pos)) {
                        ans.push_back({kx, ky});
                        break;
                    }
                    kx += dx;
                    ky += dy;
                }
            }
        }
        return ans;
    }
    
    // 从皇后出发
    vector<vector<int>> queensAttacktheKing2(vector<vector<int>>& queens, vector<int>& king) {
        auto sgn = [](int x) -> int{
            return x > 0 ? 1 : (x == 0 ? 0 : -1);
        };

        unordered_map<int, pair<vector<int>, int>> candidates;
        int kx = king[0], ky = king[1];
        for (const auto& queen: queens) {
            int qx = queen[0], qy = queen[1];
            int x = qx - kx, y = qy - ky;
            if (x == 0 || y == 0 || abs(x) == abs(y)) {
                int dx = sgn(x), dy = sgn(y);
                int key = dx * 10 + dy;
                if (!candidates.count(key) || candidates[key].second > abs(x) + abs(y)) {
                    candidates[key] = {queen, abs(x) + abs(y)};
                }
            }
        }

        vector<vector<int>> ans;
        for (const auto& [_, value]: candidates) {
            ans.push_back(value.first);
        }
        return ans;
    }
};

golang 解法, 执行用时: 0 ms, 内存消耗: 2.4 MB, 提交时间: 2022-11-25 22:03:14

func queensAttacktheKing(queens [][]int, king []int) [][]int {
    res := [][]int{}
    table := [][]int{}
    // 创建8*8的空棋盘
    for i:=0;i<8;i++ {
        table = append(table,[]int{})
        for j:=0;j<8;j++ {
            table[i] = append(table[i],0)
        }
    }
    // 标记皇后的位置
    for _,v := range queens {
        table[v[0]][v[1]] = 1
    }
    // 从八个方向上移动国王
    for i:=-1;i<=1;i++ {
        for j:=-1;j<=1;j++ {
            if i==0 && j==0 {
                continue
            }
            temp := move(table,king[0],king[1],i,j)
            if len(temp) > 0 {
                res = append(res,temp)
            }
        }
    }
    return res
}

// 移动国王，判断是否碰到皇后
func move(board [][]int, rx,ry,mx,my int) []int {
    res := []int{}
    if mx != 0 && my == 0 {
        for i:=rx;i>=0&&i<8;i+=mx {
            if board[i][ry] == 1 {
                res = append(res,i)
                res = append(res,ry)
                return res
            }
        }
    }
    if my != 0 && mx == 0 {
        for j:=ry;j>=0&&j<8;j+=my {
            if board[rx][j] == 1 {
                res = append(res,rx)
                res = append(res,j)
                return res
            }
        }
    }
    if mx != 0 && my != 0 {
        for i,j:=rx,ry;i>=0&&i<8&&j>=0&&j<8;i,j=i+mx,j+my {
            if board[i][j] == 1 {
                res = append(res,i)
                res = append(res,j)
                return res
            }
        }
    }
    return res
}

python3 解法, 执行用时: 36 ms, 内存消耗: 14.8 MB, 提交时间: 2022-11-25 22:01:47

class Solution:
    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:
        def sign(x):
            return 1 if x > 0 else -1 if x < 0 else 0

        def transfer(king, queen):
            (rk, ck), (rq, cq) = king, queen
            rv, cv = rq - rk, cq - ck
            if rv == 0 or cv == 0 or abs(rv) == abs(cv) != 0:
                return (sign(rv), sign(cv)), abs(rv) + abs(cv)
            return (None, None), False

        queens_dist = dict()
        for queen in queens:
            direction, distance = transfer(king, queen)
            if distance and (direction not in queens_dist or distance < queens_dist[direction][1]):
                queens_dist[direction] = (queen, distance)

        return list(map(lambda x: x[0], queens_dist.values()))

python3 解法, 执行用时: 28 ms, 内存消耗: 14.8 MB, 提交时间: 2022-11-25 22:01:16

class Solution:
    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:
        rows = columns = 8
        queens = set(map(tuple, queens))
        directions = [(dr, dc) for dr in [-1, 0, 1] for dc in [-1, 0, 1] if not dr == dc == 0]

        def get_queen(loc, direction):
            (r, c), (dr, dc) = loc, direction
            while 0 <= r + dr < rows and 0 <= c + dc < columns:
                if (r + dr, c + dc) in queens:
                    return [r + dr, c + dc]
                r += dr
                c += dc
            return None

        ans = [get_queen(king, d) for d in directions]
        return [a for a in ans if a]

python3 解法, 执行用时: 40 ms, 内存消耗: 14.8 MB, 提交时间: 2022-11-25 22:00:46

class Solution:
    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:
        a = [[0 for _ in range(8)] for _ in range(8)]
        for r,c in queens:                  #状态标记  queen所在的位置 置1
            a[r][c] = 1
        
        res = []
        dirs = [[-1,-1],[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1]]  #8个方向
        for dr,dc in dirs:                  #遍历 每次照着一个方向一路查找
            r,c = king[0], king[1]
            nr, nc = r + dr, c + dc
            while 0<=nr<8 and 0<=nc<8:      #只要还没出边界
                if a[nr][nc] == 1:
                    res.append([nr, nc])
                    break
                nr = nr + dr                    #按照这个方向一直找  直到找到或者和出了范围
                nc = nc + dc

        return res