首页 > 编程语言 >算法练习第三十天|两道hard51. N 皇后、37. 解数独

算法练习第三十天|两道hard51. N 皇后、37. 解数独

时间:2024-03-22 17:02:38浏览次数:28  
标签:row return int chessboard 37 char board 解数 hard51

37. 解数独
51. N 皇后

  1. 解数独
class Solution {
    public void solveSudoku(char[][] board) {
        backTrace(board);
    }

    public boolean backTrace(char[][] board){
        //仅收集一个结果

        for(int i = 0;i<9;i++){
            for(int j = 0;j<9;j++){
                if(board[i][j] != '.') continue;
                for (char k = '1'; k <= '9'; k++){
                    
                    if (isValid(i, j, k, board)){
                            board[i][j] = k;
                            if (backTrace(board)) // 如果找到合适一组立刻返回
                            return true;
                            
                            board[i][j] = '.';
                    }
                }
                // 9个数都试完了,都不行,那么就返回false

                return false;
            }
        }
        // 遍历完没有返回false,说明找到了合适棋盘位置了
        return true;
    }


/**
     * 判断棋盘是否合法有如下三个维度:
     *     同行是否重复
     *     同列是否重复
     *     9宫格里是否重复
     */
    private boolean isValid(int row, int col, char val, char[][] board){
        // 同行是否重复
        for (int i = 0; i < 9; i++){
            if (board[row][i] == val){
                return false;
            }
        }
        // 同列是否重复
        for (int j = 0; j < 9; j++){
            if (board[j][col] == val){
                return false;
            }
        }
        // 9宫格里是否重复
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++){
            for (int j = startCol; j < startCol + 3; j++){
                if (board[i][j] == val){
                    return false;
                }
            }
        }
        return true;
    }
}
  1. N 皇后
class Solution {
    List<List<String>> res = new ArrayList();
    public List<List<String>> solveNQueens(int n) {
        char[][] chessboard = new char[n][n];
        for(char[] c : chessboard){
            Arrays.fill(c,'.');
        }
        backTrace(chessboard,n,0);
        return res;
    }

    public void backTrace(char[][] chessboard,int n,int row){
        if(row == n){
            res.add(arrays2String(chessboard));
        }
        //从0到第n列
        for(int i = 0;i<n;i++){
            if(!isValid(row,i,chessboard,n)) continue;
            chessboard[row][i] = 'Q';
            backTrace(chessboard,n,row+1);
            chessboard[row][i] = '.';
        }
    }

    public List<String> arrays2String(char[][] chessboard){
        List<String> list = new ArrayList<>();

        for (char[] c : chessboard) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }

    public boolean isValid(int row,int col,char[][] chessboard,int n){
        //检查列
        for(int i = 0;i<row;i++){
            if(chessboard[i][col] == 'Q') return false;
        }

        // 检查45度对角线,从当前位置往左上
        for(int i = row-1,j=col-1; i>=0&&j>=0;i--,j--){
            if(chessboard[i][j] == 'Q') return false;
        }
       
        // 从当前位置往右上
        for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }

        return true;
    }
}

标签:row,return,int,chessboard,37,char,board,解数,hard51
From: https://blog.csdn.net/qq_51059003/article/details/136946253

相关文章

  • 洛谷 P1379 八数码难题 A* 题解
    刚做完一道模板A*,看到这题我直接小脑萎缩了...阿米诺斯!这怎么用A*?!——刚开题的我beeeeeeeeeelike甚至比模板简单(这是绿的...)其实会是会但是纸张的是这玩意我不会搞估价函数我草!然后突然想到能不能把这个状态下有多少个数字不在目标位置作为估价函数?我喜欢\(IDA*\),有兴趣......
  • lc375 猜数字大小2
    A从1到n之间选择一个数字让B来猜,假设B猜数字x,如果猜对,直接结束;否则B需要支付金额x,然后A告诉B小了或者大了并继续猜。给定数字n,问能确保获胜的最小现金,无论A选择哪个数字。1<=n<=200区间dp,记dp[i][j]表示区间为[i,j]时获胜所需的最小现金,枚举每次猜的数字k,考虑最坏情况进行转移即......
  • 洛谷题单指南-集合-P3370 【模板】字符串哈希
    原题链接:https://www.luogu.com.cn/problem/P3370题意解读:本题要求理解哈希的原理,自行建立哈希表解题,如果直接使用map,就不推荐。解题思路:先介绍哈希的原理1、什么是哈希?什么是哈希表?先从一个问题出发:给定不超过105个整数(取值1~109),要统计不重复整数的数量。首先,如果取值范围......
  • Edu37
    基本情况场出三题,C卡了很久而且不是正解。C.SwapAdjacentElementsProblem-C-Codeforces前缀和妙用显然连续的\(1\)对应的序列是一定可以有序的。有想到这点,但没想到合理的检查方式,所以直接用\(\texttt{dsu}\)模拟了。myCodevoidsolve(){intn;st......
  • P3714 [BJOI2017] 树的难题
    fromxcs题意:给定一棵\(n\)个节点的树,树根为\(1\),每个点有一个编号,每条边有一个边权。定义\(dep(x)\)表示一个点到根简单路径上边权的和,\(lca(x,y)\)表示\(x,y\)节点在树上的最近公共祖先。共\(m\)组询问,每次询问给出\(l,r\),求对于所有点编号的二元组\((i,j)\)......
  • SQL-Labs靶场“36-37”关通关教程
    一、36关GET单引号宽字节注入请求方式注入类型拼接方式GET联合、报错、布尔盲注、延时盲注id=‘$id’首先我们进行测试(使用?id=1\,查看过滤后的回显)这里可以看到对我们的注释符进行了注释以及单双引号进行测试会发现都是如此:所以这里我们判断使用了过滤函数进行了过滤......
  • P1377 [TJOI2011] 树的序 (笛卡尔树)
    笛卡尔树模板题题目给出一个生成序列要我们构造一个二叉搜索树。所以值要满足二叉搜索树的性质。因为给出的是生成序列,所以序列的下标是满足最小堆的性质。那么可以按照满足二叉搜索树的那一维度进行排序也就是值进行排序。然后进行构建即可。最后进行先序遍历即可获得答......
  • 【题解】A18537.我心中珍藏的游戏
    题目跳转思路:题目问最多可以获得的额外伤害,其实就是询问在这些技能中,如何怎样选取一个最优的发动技能顺序使得攻击加成最大。我们可以把每一个技能看作成一个图的顶点,把每一个攻击加成看作图的边,权制为\(Ei,j\)。由于\(Ei,j\)与\(Ej,i\)相等,则可以将这个图视为无向图。可以样样......
  • C语言指针(适合C语言进阶者):一道题带你深入理解数组与指针的关系
    ......
  • 376. 摆动序列c
    intmax(inti,intj){if(i>j)returni;returnj;}intwiggleMaxLength(int*nums,intnumsSize){int**dp=(int**)malloc(sizeof(int*)*numsSize);for(inti=0;i<numsSize;i++)dp[i]=(int*)malloc(sizeof(int)*2);dp[0][0]=1,dp[0][1]=......