持续创作，加速生长！这是我参加「掘金日新计划 10 月更文挑战」的第18天，点击查看活动概况

‍作者简介：一位喜欢写作，计科专业的大三菜鸟

个人主页：starry陆离 的个人主页

假如文章有帮到你的话记得点赞+保藏支撑一下哦

1.每日一题

原题链接：传送门-》戳我

N 皇后问题是指在 n * n 的棋盘上要摆 n 个皇后， 要求：任何两个皇后不同行，不同列也不在同一条斜线上， 求给一个整数 n ，返回 n 皇后的摆法数。

数据规模: 1≤n≤9

要求：空间复杂度 O(1) ，时刻复杂度 O(n!)

例如当输入4时，对应的返回值为2，

对应的两种四皇后摆位如下图所示：

2.解题思路

2.1思路剖析

皇后问题很简单，由于每一行，每一列，每条斜线不能有重复的皇后，所以咱们只需要从遍历行的角度动身，去查看新的一行里每一列和左右两条斜线是否有皇后抵触，当没有抵触的时候就坐标信息表明放置皇后。当一向找到最终一行时就表明找到了一种摆法，然后回溯去找新的解。

• step 1：界说一个公共变量记载摆法的种数

  //皇后摆法得个数
   public int ans;

• step 2：用一个一维数组来记载每一列是否放了皇后，数组的下标表明行，值表明列（很奇妙吧，假如是你去保存一个坐标的信息是不是只会开一个二维数组呢）

  //记载某一列是否放了皇后
    int col[]=new int[10];
  

• step 3：调用深搜函数，咱们按行来深搜，递归的结束条件便是查找完最终一行后代表找到一种解，开端回溯。

  //假如查找完棋盘的最终一行(下标从0开端最终一行是n-1)
   if(r==n){
     //摆放的办法+1
     ans++;
     return;
    }

• step 4：假如没有查找完最终一行，咱们就遍历这一行的每一列，首要经过check()查看假如在这一列放是否与之前行现已放好的皇后抵触；假如不抵触的话才放置皇后，便是符号col[]数组，然后往下一行查找；记得回溯时去皇后 col[r]=0;

 //遍历n列
   for(int c=0;c<n;++c){
     //剪枝操作
     if(check(r,c,col)){
       //符号在第r行的第c列放的皇后
       col[r]=c;
       //深度查找下一行,在下一行放皇后
       dfs(r+1,n,col);
       //回溯,去除符号
       col[r]=0;
      }
    }

• step 5：第四步顶用到了check()函数查看抵触，抵触的查看规则便是不能同行同列同斜线，同行的查看是不需要的由于咱们的深搜便是按行进行肯定不会在同一行放两个皇后。查看列便是比对此刻的列是否现已被符号（记载过皇后的坐标col[i]==c）；查看斜线这儿也很巧，由于在同一斜线上的两点的横坐标之差与纵坐标之差会相等，所以只需判别(Math.abs(col[i]-c)==(Math.abs(i-r)))是否成立

3.关键代码

import java.util.*;
​
​
public class Solution {
  /**
   * 
   * @param n int整型 the n
   * @return int整型
   */
  //皇后摆法得个数
  public int ans;
  public int Nqueen (int n) {
    // write code here
    ans=0;
    //记载某一列是否放了皇后
    int col[]=new int[10];
    Arrays.fill(col,0);
    //深度查找
    dfs(0,n,col);
    return ans;
   }
   //深度查找
  public void dfs(int r,int n,int col[]){
    //假如查找完棋盘的最终一行(下标从0开端最终一行是n-1)
    if(r==n){
      //摆放的办法+1
      ans++;
      return;
     }
    //遍历n列
    for(int c=0;c<n;++c){
      //剪枝操作
      if(check(r,c,col)){
        //符号在第r行的第c列放的皇后
        col[r]=c;
        //深度查找下一行,在下一行放皇后
        dfs(r+1,n,col);
        //回溯,去除符号
        col[r]=0;
       }
     }
   }
  public boolean check(int r,int c,int col[]){
    //查看是否与前面现已放了皇后的r行是否抵触
    for(int i=0;i<r;++i){
      //查看列抵触和对角线抵触
      if(col[i]==c||(Math.abs(col[i]-c)==(Math.abs(i-r)))){
        return false;
       }
     }
    return true;
   }
}

每日推荐：算法面试神器：牛客网-面试神器

假如文章有帮到你的话记得点赞+保藏支撑一下哦