前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >Leetcode No.36 有效的数独

Leetcode No.36 有效的数独

作者头像
week
发布于 2022-01-07 05:54:51
发布于 2022-01-07 05:54:51
34500
代码可运行
举报
文章被收录于专栏:用户画像用户画像
运行总次数:0
代码可运行

一、题目描述

判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字,空白格用 '.' 表示。

示例 1: 输入: [ ["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ] 输出: true

示例 2: 输入: [ ["8","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ] 输出: false

解释: 除了第一行的第一个数字从 5 改为 8 以外,空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。 说明:

一个有效的数独(部分已被填充)不一定是可解的。 只需要根据以上规则,验证已经填入的数字是否有效即可。 给定数独序列只包含数字 1-9 和字符 '.' 。 给定数独永远是 9x9 形式的。

二、解题思路

1、验证数字 1-9 在每一行只能出现一次。

2、验证数字 1-9 在每一列只能出现一次。

3、验证数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

三、代码

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
package is_valid_sudoku;

import java.util.HashMap;
import java.util.Map;
public class Solution {
    public boolean isValidSudoku(char[][] board) {
        int len=board.length;
        for(int i=0;i<len;i++){
            if(!checkRow(board,i)){
                System.out.println("第"+i+"行验证失败");
                return false;
            }else{
                System.out.println("第"+i+"行验证成功");
            }
        }
        for(int i=0;i<len;i++){
            if(!checkColumn(board,i)){
                System.out.println("第"+i+"列验证失败");
                return false;
            }
            else{
                System.out.println("第"+i+"列验证成功");
            }
        }
        for(int i=0;i<3;i++) {
            for(int j=0;j<3;j++){
                if (!checkMatrix(board, i*3, j*3)) {
                    return false;
                }
                else{
                    System.out.println("第"+i*3+","+j*3+"矩阵验证成功");
                }
            }
        }
        return true;
    }
    public boolean checkRow(char[][] board,int row){
        int len=board.length;
        Map<Character, Integer> map=new HashMap<>();
        for(int i=0;i<10;i++){
            map.put(Character.forDigit(i,10),0);
        }
        for(int i=0;i<len;i++){
            if(board[row][i]!='.'){
                if(map.get(board[row][i])>=1){
                    return false;
                }else{
                    map.put(board[row][i],map.get(board[row][i])+1);
                }
            }
        }
        return true;
    }
    public boolean checkColumn(char[][] board,int column){
        int len=board.length;
        Map<Character, Integer> map=new HashMap<>();
        for(int i=0;i<10;i++){
            map.put(Character.forDigit(i,10),0);
        }
        for(int i=0;i<len;i++){
            if(board[i][column]!='.'){
                if(map.get(board[i][column])>=1){
                    return false;
                }else{
                    map.put(board[i][column],map.get(board[i][column])+1);
                }
            }
        }
        return true;
    }
    public boolean checkMatrix(char[][] board,int rowStart,int columnStart){
        int len=board.length;
        Map<Character, Integer> map=new HashMap<>();
        for(int n=0;n<10;n++){
            map.put(Character.forDigit(n,10),0);
        }
        int rowEnd=rowStart+3;
        int columnEnd=columnStart+3;
        for(int i=rowStart;i<rowEnd;i++){
            for(int j=columnStart;j<columnEnd;j++) {
                if(board[i][j]!='.'){
                    if (map.get(board[i][j]) >= 1) {
                        return false;
                    } else {
                        map.put(board[i][j], map.get(board[i][j]) + 1);
                        System.out.println(map);
                    }
                }
            }
        }
        System.out.println(map);
        return true;
    }

    public static void main(String[] args) {
        Solution solution=new Solution();
        char[][] board={
                {'5','3','.','.','7','.','.','.','.'},
                {'6','.','.','1','9','5','.','.','.'},
                {'.','9','8','.','.','.','.','6','.'},
                {'8','.','.','.','6','.','.','.','3'},
                {'4','.','.','8','.','3','.','.','1'},
                {'7','.','.','.','2','.','.','.','6'},
                {'.','6','.','.','.','.','2','8','.'},
                {'.','.','.','4','1','9','.','.','5'},
                {'.','.','.','.','8','.','.','7','9'}
        };
        System.out.println(solution.isValidSudoku(board));
    }

}

四、复杂度分析

时间复杂度:O(1),只对 81 个单元格进行了3次迭代。

空间复杂度:O(1),只需要常数空间存放若干变量。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021/01/23 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、题目描述
  • 二、解题思路
  • 三、代码
  • 四、复杂度分析
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档