LeetCode 52. N 皇后 II

Categories:

题目描述
思路分析
1. 解法一：位运算回溯（推荐）
相似题目

题目描述

✅ 52. N 皇后 II

思路分析

解法一：位运算回溯（推荐）

核心思路：

使用位掩码表示已占用的列、主对角线、副对角线。

当前行可放置位置为 available = limit & ~(cols | diag1 | diag2)。

依次取最低位 1 放置，递归下一行。

复杂度分析：

时间复杂度：O(n!)，n 为皇后数量（位运算剪枝更快）。

空间复杂度：O(n)，递归栈。

class Solution {
    public int totalNQueens(int n) {
        int limit = (1 << n) - 1;
        return dfs(0, 0, 0, limit);
    }

    private int dfs(int cols, int diag1, int diag2, int limit) {
        if (cols == limit) {
            return 1;
        }

        int available = limit & ~(cols | diag1 | diag2);
        int count = 0;
        while (available != 0) {
            int p = available & -available;
            available -= p;
            count += dfs(cols | p, (diag1 | p) << 1, (diag2 | p) >> 1, limit);
        }
        return count;
    }
}

func totalNQueens(n int) int {
	limit := (1 << n) - 1
	return dfsQueens(0, 0, 0, limit)
}

func dfsQueens(cols int, diag1 int, diag2 int, limit int) int {
	if cols == limit {
		return 1
	}

	available := limit & ^(cols|diag1|diag2)
	count := 0
	for available != 0 {
		p := available & -available
		available -= p
		count += dfsQueens(cols|p, (diag1|p)<<1, (diag2|p)>>1, limit)
	}
	return count
}

相似题目

题目	难度	考察点
51. N 皇后	困难	回溯
52. N 皇后 II	困难	回溯
37. 解数独	困难	回溯
46. 全排列	中等	回溯
47. 全排列 II	中等	回溯
216. 组合总和 III	中等	回溯

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/49698074