leetcode--N 皇后 II(java)

SP_1024

2024-04-28 帮助1人

leetcode 52 题 - N 皇后 II (困难)

原题链接:
https://leetcode.cn/problems/n-queens-ii/

题目描述

n 皇后问题研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回 n 皇后问题不同的解决方案的数量。

示例1:

输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例2 :
输入：n = 1
输出：1

解题思路

我们用递归来解决这个问题:
我们一行一行的去验证哪列可以放置皇后,
(因此这个思路就推导出,需要循环加递归)

每到一行,我们只需要验证他前面皇后放的位置,来确定他哪里能放.
验证的方法:
同一列有的肯定不能放了
还有就是斜线位置怎么验证,
举个例子:
A 点(1,2) 和B 点 (2,3) 这两个点在一条斜线上,
那么 1-2 肯定等于 2 - 3 .,
也就是A 的行号 - B 的行号等于A 的列号 - B 的列号.

代码演示

代码可以放到leetcode 上去测试

public int totalNQueens(int n) {
        if(n < 1){
            return 0;
        }
        // 这个数组 下标来记录行号 值代表列 记录哪行哪列有皇后
        int[] ans = new int[n];
        return process(0,ans,n);

    }
	/**
	* i 代表 行号
	* n 总共几个皇后
	* record 记录已经防置皇后的位置
	*/
    public int process(int i,int[]record,int n){
     	//i == n 代表所有行都校验通过才来到这里  所以返回一种方案
       if(i == n){
           return 1;
       }
    int res = 0;
    //j 代表列号 每到一个行我们就考察所有列,能放在哪一列上
    for(int j = 0;j < n;j  ){
        if(checkPostion(record,i,j)){
        //皇后位置记录下来
            record[i] = j;
            //递归 行号加1 
            res  = process(i 1,record,n);
        }
    }

    return res;

    }
	/**
	* 验证这个位置可以放不可以放
	*/
    public boolean checkPostion(int[]record,int i,int j){
       for(int k = 0; k < i;k  ){
       //同一列有皇后不能放,和斜线有皇后不能放
           if(record[k] == j || Math.abs(record[k] - j) == Math.abs(i - k)){
               return false;
           }
       }
       return true;
    }