11-4  n皇后问题:要求在一个nXn的棋盘上放置n个皇后,要求放置的n个皇后不会互相吃掉;皇后棋子可以吃掉任何它所在的那一行、那一列,以及那两条对角线上的任何棋子。-笔试面试资料

这是qklbishe.com第7443 篇笔试面试资料
提供答案分析,通过本文《11-4  n皇后问题:要求在一个nXn的棋盘上放置n个皇后,要求放置的n个皇后不会互相吃掉;皇后棋子可以吃掉任何它所在的那一行、那一列,以及那两条对角线上的任何棋子。-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:
11-4  n皇后问题:要求在一个nXn的棋盘上放置n个皇后,要求放置的n个皇后不会互相吃掉;皇后棋子可以吃掉任何它所在的那一行、那一列,以及那两条对角线上的任何棋子。

11-4  n皇后问题:要求在一个nXn的棋盘上放置n个皇后,要求放置的n个皇后不会互相吃掉;皇后棋子可以吃掉任何它所在的那一行、那一列,以及那两条对角线上的任何棋子。 温暖的秋裤
class Solution {
    LinkedList<List<String>> res=new LinkedList();
    public List<List<String>> solveNQueens(int n) {
        if(n==0)return res;
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<n;i++){
            sb.append(".");
        }
        String[] str=new String[n];
        for(int i=0;i<n;i++){
            str[i]=sb.toString();
        }
        backTrack(str,0);
        return res;
    }

    //在第i行放值,回溯

    public void backTrack(String[] str,int i){
        int n=str.length;
        if(i==n){
            ArrayList<String> list=new ArrayList();
            for(String s:str){
                list.add(s);
            }
            res.add(list);
            return;
        }
        for(int j=0;j<n;j++){
            if(valid(str,i,j)){
                //改变
                String old=str[i];
                StringBuilder sb=new StringBuilder(old);
                sb.setCharAt(j,‘Q’);
                str[i]=sb.toString();
                backTrack(str,i+1);
                str[i]=old;
            }
        }
    }

    public boolean valid(String[] str,int i,int j){
        int len=str.length;
        //检查列
        for(int a=0;a<i;a++){
            if(str[a].charAt(j)==‘Q’)return false;
        }
        //检查左上
        for(int dis=1;dis<=i&&j>=dis;dis++){
            if(str[idis].charAt(jdis)==‘Q’)return false;
        }
        //检查右上
        for(int dis=1;dis<=i&&j+dis<len;dis++){
            if(str[idis].charAt(j+dis)==‘Q’)return false;
        }

        return true;

    }
}

今天 01:58:21 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 11-4  n皇后问题:要求在一个nXn的棋盘上放置n个皇后,要求放置的n个皇后不会互相吃掉;皇后棋子可以吃掉任何它所在的那一行、那一列,以及那两条对角线上的任何棋子。-笔试面试资料

提供最优质的资源集合

立即查看 了解详情