`

Leetcode - Valid Sudoku

 
阅读更多
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
[分析] 九宫格规则:每一行,每一列,每个3*3的区块的9个数字恰好为1-9,不能有重复。
注意3*3的区块为行列三等分形成的,共9个,而不是任意的3*3区块。 此题对我来说难点在于3*3区块下标的表示上,方法2参照https://leetcode.com/discuss/45494/java-solution-easy-to-understand,代码非常简洁。

public class Solution {
    // Method 2
    public boolean isValidSudoku(char[][] board) {
        boolean[][] rows = new boolean[9][9];
        boolean[][] cols = new boolean[9][9];
        boolean[][] block = new boolean[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.')
                    continue;
                int digit = board[i][j] - '1';
                int blockId = i / 3 * 3 + j / 3;
                
                if (rows[i][digit]) return false;
                else rows[i][digit] = true;
                
                if (cols[j][digit]) return false;
                else cols[j][digit] = true;
                
                if (block[blockId][digit]) return false;
                else block[blockId][digit] = true;
            }
        }
        return true;
    }
    
    // Method 1
    public boolean isValidSudoku1(char[][] board) {
        boolean[] used = new boolean[board.length + 1];
        int n = board.length;
        //check each row
        for(int i = 0; i < n; i++){
            used = new boolean[n + 1];
            for(int j = 0; j < n; j++)
                if(board[i][j] == '.')
                    continue;
                else if(!used[board[i][j] - '0'])
                    used[board[i][j] - '0'] = true;
                else
                    return false;
        }
        
        //check each column
        for(int j = 0; j < n; j++){
            used = new boolean[n + 1];
            for(int i = 0; i < n; i++)
                if(board[i][j] == '.')
                    continue;
                else if(!used[board[i][j] - '0'])
                    used[board[i][j] - '0'] = true;
                else
                    return false;
        }
        
        //check for each block
        for(int r = 0; r < 3; r++){
            for(int c = 0; c < 3; c++){
                used = new boolean[n + 1];
                int x = 3 * r;
                int y = 3 * c;
                for(int i = 0; i < 3; i++){
                    for(int j = 0; j < 3; j++){
                        if(board[x + i][y + j] == '.')
                            continue;
                        else if(!used[board[x + i][y + j] - '0'])
                            used[board[x + i][y + j] - '0'] = true;
                        else
                            return false;
                    }
                }
            }
        }
        
        return true;
    }
}
分享到:
评论

相关推荐

    C语言-leetcode题解之36-valid-sudoku.c

    c语言入门 C语言_leetcode题解之36-valid-sudoku.c

    js-leetcode题解之第36-valid-sudoku.js

    js js_leetcode题解之第36-valid-sudoku.js

    leetcode-cpp刷题

    - **2.1.14 Valid Sudoku** - 判断给定的数独是否有效。 - 实现思路:分别检查行、列和小九宫格是否包含重复数字。 - **2.1.15 Trapping Rain Water** - 计算雨水能够困住的水量。 - 实现思路:使用动态规划...

    _leetcode-python.pdf

    - Valid Sudoku: 验证一个9x9的数独是否有效。 - Sudoku Solver: 解数独问题,即给出一个部分填充的数独,要求填充剩余空格。 - Count and Say: 第n个数是“1”,“21”,“1211”,“111221”等描述的下一个数。 - ...

    dna匹配leetcode-leetcode:leetcode刷题

    Valid Sudoku 数组 遍历 Sudoku Solver 深度优先遍历 回溯 先检查后修改 Group Anagrams 排序 unordered_map Minimum Window Substring 两个指针遍历 map Maximal Rectangle 栈 局部递增 或者 动态规划 Binary Tree ...

    leetcode2-Codonfest:鳕鱼{ON}节2020

    leetcode 2 密码节 以及在竞争性编程中组织了第一个 1.5 个月的指导计划。 该计划将包括 2 个阶段。 学习阶段: 学员将与导师配对,在为期 1 个月的时间里,学员将获得学员每天需要尝试的不同难度级别的学习材料和...

    leetcode-answer

    例如,“Valid Sudoku”(有效的数独)问题,可以利用HashSet来检查每一行、每一列以及每一个宫格的唯一性。 最后,我们要提的是Java的性能优化。在LeetCode中,除了正确性,代码的运行效率也非常重要。这包括合理...

    leetcode1-200题源码(c++)

    2. 题目36:有效的数独 (Valid Sudoku) 验证一个9x9的数独是否有效,需要检查每一行、每一列以及每个小九宫格内的数字是否唯一。可以使用哈希表来快速检查数字是否存在。 3. 题目87:扫描线排序 (Scramble String)...

    LeetCode最全代码

    # [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...

    leetcode卡-leetcode:利特码解决方案

    Valid Sudoku linked list Palindrome linked list Linked List Cycle trees Convert Sorted Array to Binary Search Tree string and search First Bad Version Dynamic Programing *** Climbing Stairs Set Matrix...

    python-leetcode面试题解之第36题有效的数独-python题解.zip

    在本压缩包中,我们关注的是一个Python编程相关的学习资源,特别针对LeetCode平台上的第36题——“有效的数独”(Valid Sudoku)。这是一道典型的算法问题,经常出现在IT求职面试中,尤其是对Python程序员来说。让...

    leetcode添加元素使和等于-leetcode_py:leetcode的python版本问题

    leetcode添加元素使和等于 leetcode_py Python version of leetcode problems 33 Search in Rotated Sorted Array 问题:找到经过旋转的有序数组中是否有目标的数。 解法:基于二分的方法,根据 ...Valid Sudoku 问题

    lintcode:LintCode题解,LintCode是LeetCode.com网站的增强版,题目更优质,覆盖知识点更多

    #LintCode题解##PDF下载本书即将由电子工业出版社出版,因此这个Repo更新会略落后于纸质版。欢迎大家购买纸质版,支持我持续更新本书。C++ 文件夹下是C++版,内容一摸一样,代码是用C++写的,Java 文件夹下是Java版...

    LeetCode

    除了基本算法,LeetCode还包含一些涉及复杂数据结构和算法的问题,如"Longest Increasing Subsequence.py"(最长递增子序列)、"Valid Sudoku.py"(验证数独)以及"Minimum Spanning Tree.py"(最小生成树)。...

    lrucacheleetcode-LeetCode:这个库用于总结leetcode中遇到的习题,期望按照数据结构和常用方法分成2类,进行总结,

    lru cache leetcode LeetCode 这个库用于总结leetcode中遇到的习题 常用数据结构习题总结 1.线性表 解决进度 No. Describition mark 1 Remove Duplicates from ...Valid Sudoku 15 Trapping Rain W

    uber leetcode

    #### 二、Valid Sudoku - **知识点:**数组、哈希表。 - **题目描述:**判断一个9x9的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可: - 每行中的数字必须是1-9,并且不能重复。 - 每列中的...

    春节7天练丨Day6:图1

    - **Valid Sudoku**:检查一个数独是否有效,即每一行、每一列以及每一个宫格内的数字是否都在1到9之间且不重复。 这些知识点在编程竞赛、算法设计、网络分析、图形理论等领域都有广泛应用。通过LeetCode等在线...

    leetcode

    4. "Valid Sudoku":使用二维HashSet检查9x9的数独是否合法。 通过不断练习LeetCode中的Java解决方案,不仅可以巩固和深化对Java语言的理解,还能提升算法思维和问题解决能力,对于程序员的职业发展大有裨益。在...

Global site tag (gtag.js) - Google Analytics