[Leetcode]36 Valid Sudoku

zhichangterry 发布于2019-08-14 14:54 / 2432人阅读

摘要：的可以由确定，这一点在里面的位置可以由确定所以每确定一行，每一个值都可以被转换到一个之中。如果允许的空间复杂度，可以设置一个二维数组来用来判断是否在里重现了重复的数字。将一个数字的每一个位上表示每一个数字。

Leetcode[36] 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.

坐标转换

复杂度
时间复杂度 O(MN) 空间复杂度 O(1)

思路
对于boardi上的一点，要满足这一点所在的行，所在的列，和这一点所在的block里有且只有这一个数。首先考虑，如何找到这一点对应的block。block的index可以由(i / 3) 3 + j / 3确定，这一点在block里面的位置可以由(i % 3) 3 + j % 3确定. 所以每确定一行，每一个值都可以被转换到一个block之中。

如果允许O(N)的空间复杂度，可以设置一个二维数组9*9来用来判断是否在block里重现了重复的数字。如果用O(1)的空间复杂度，可以用bitset的方式。将一个数字的每一个bit位上表示每一个数字。通过将set和新来的数字相与，可以知道这个数字是否之前出过。

代码

// 关键是如何将坐标转换成在每一个小的九宫格；
public boolean isValidSudoku(char[][] board) {
    for(int i = 0; i < 9; i ++) {
        // set bitmap for row, col and block.
        int row = 0;
        int col = 0;
        int block = 0;
        for(int j = 0; j < 9; j ++) {
            int rowval = board[i][j] - "1";
            int colval = board[j][i] - "1";
            int blockval = board[i / 3 * 3 + j / 3][i % 3 * 3 + j % 3] - "1";
            // 将值移动每一个bit位上，来判断是否相等。
            if(rowval >= 0 && (row & (1 << rowval)) != 0
            || colval >= 0 && (col & (1 << colval)) != 0
            || blockval >= 0 && (block & (1 << blockval)) != 0) return false;
            row |= 1 << rowval;
            col |= 1 << colval;
            block |= 1 << blockval;
        }
    }
    return true;
}

云服务器 GPU云服务器 sudoku LeetCode Valid valid?file

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65173.html

leetcode36 Valid Sudoku 查看数独是否合法

摘要：如果重复则不合法，否则极为合法。在这里我们使用数组代替作为存储行列和小正方形的值得数据结构。我存储这所有的行列小正方形的情况，并判断当前值是否重复。外循环则代表对下一行，下一列和下一个小正方形的遍历。题目要求 Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku boa...

wing324 2019-08-16 10:32 评论0 收藏0
leetcode 36 Valid Sudoku

摘要：要求我们判断已经填入的数字是否满足数独的规则。即满足每一行每一列每一个粗线宫内的数字均含，不重复。没有数字的格子用字符表示。通过两层循环可以方便的检查每一行和每一列有没有重复数字。对于每个，作为纵坐标，作为横坐标。题目详情 Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.The Sudo...

entner 2019-08-15 14:51 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
[LeetCode] 37. Sudoku Solver

Problem Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exactly once in each row.Each ...

alaege 2019-08-19 11:14 评论0 收藏0
leetcode37 Sudoku Solver

摘要：题目要求也就是给出一个解决数独的方法，假设每个数独只有一个解决方案。并将当前的假象结果带入下一轮的遍历之中。如果最终遍历失败，则逐级返回，恢复上一轮遍历的状态，并填入下一个合理的假想值后继续遍历。题目要求 Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indi...

pepperwang 2019-08-15 10:49 评论0 收藏0