【面试经典150 | 矩阵】有效的数独

这篇具有很好参考价值的文章主要介绍了【面试经典150 | 矩阵】有效的数独。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

写在前面

本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更……

专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删:

  • Tag:介绍本题牵涉到的知识点、数据结构;
  • 题目来源:贴上题目的链接,方便大家查找题目并完成练习;
  • 题目解读:复述题目(确保自己真的理解题目意思),并强调一些题目重点信息;
  • 解题思路:介绍一些解题思路,每种解题思路包括思路讲解、实现代码以及复杂度分析;
  • 知识回忆:针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【矩阵】【数组】


题目来源

面试经典150 | 36. 有效的数独

【面试经典150 | 矩阵】有效的数独,面试经典150题,矩阵,数组,C++,算法

题目解读

9 x 9 的数独,有 9 行,9 列,每一行、列中可以填的数字为 1 - 9,每一行中 1 - 9 中的数字只能出现一次,列也是。9 x 9 的数独会被分成 3 x 3九宫格,每一个九宫格中需要填满 1 - 9 这九个数字。

给你一个部分填充的 9 x 9 数独,请判断是否有效。


解题思路

方法一:一次遍历+数组

根据 9 x 9 数独的每一行、每一列和每一个九宫格的填数要求来判断给定部分填充的数独是否有效。

维护三个数组 rowscolsboxes,分别用来记录 9 x 9 数独中的每一行、每一列和每一个九宫格中的字符数量,比如 rows[i][2] 表示第 i 行中字符 2 出现的次数,boxes[i][1] 表示从上往下、从左往右的第 i 个九宫格中字符 1 的数量。

我们根据 board 来更新以上三个数组,假设当前遍历的 (i, j) 处的字符 c = board[i][j],如果 c 不是表示空格的 .,则更新:

  • ++rows[i][c];
  • ++cols[j][c]
  • ++boxes[box_idx][c],其中,box_idx 表示字符 c 属于的九宫格编号,box_idx = i / 3 * 3 + j / 3

我们一边更新一边判断:

  • row[i][c] > 1
  • cols[j][c] > 1
  • boxes[box_idx][c] >1

以上条件满足任何一条,该数独都是无效的直接返回 false

最后,如果全部遍历完 board 任然没有退出,说明该数独是有效的,返回 true

实现代码

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # init data
        rows = [{} for i in range(9)]
        columns = [{} for i in range(9)]
        boxes = [{} for i in range(9)]

        # validate a board
        for i in range(9):
            for j in range(9):
                num = board[i][j]
                if num != '.':
                    num = int(num)
                    box_index = (i // 3) * 3 + j // 3

                    # keep the current cell value
                    rows[i][num] = rows[i].get(num, 0) + 1  # get(num, 0)如果字典中的值num不存在,则返回0
                    columns[j][num] = columns[j].get(num, 0) + 1
                    boxes[box_index][num] = boxes[box_index].get(num, 0) + 1

                    # check if this value has been already seen before
                    if rows[i][num] > 1 or columns[j][num] > 1 or boxes[box_index][num] > 1:
                        return False
        return True

复杂度分析

时间复杂度: O ( 1 ) O(1) O(1),数独共有 81 个单元格,只需对每一个单元格就行一次遍历。

空间复杂度: O ( 1 ) O(1) O(1),由于数独的大小固定,因此数组的空间也是固定的。


写在最后

如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。

最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。文章来源地址https://www.toymoban.com/news/detail-742663.html

到了这里,关于【面试经典150 | 矩阵】有效的数独的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣36. 有效的数独

    思路: 使用三个哈希表来存储数字个数 row[r][val] 用于存储第 r 行 val + 1 的个数; column[c][val] 用于存储第 c 列 val + 1 的个数; subboxes[i][j][val] 用于存储第 i 行、第 j 列个小九宫格 val + 1 的个数,其中: i = r / 3,j = c / 3 ​​​​​​​遍历每个小格子,统计数字的个数,分别

    2024年01月21日
    浏览(37)
  • LeetCode 36. 有效的数独

    请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 有效数独的三个条件: 1.同一个数字在每一行只能

    2024年01月16日
    浏览(45)
  • 【LeetCode: 36. 有效的数独 + 模拟】

    🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,CSDN-Java领域优质创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文

    2024年02月20日
    浏览(35)
  • LeetCode 36题:有效的数独

    请你判断一个  9 x 9  的数独是否有效。只需要  根据以下规则  ,验证已经填入的数字是否有效即可。 数字  1-9  在每一行只能出现一次。 数字  1-9  在每一列只能出现一次。 数字  1-9  在每一个以粗实线分隔的  3x3  宫内只能出现一次。(请参考示例图) 注意: 一个有

    2024年02月12日
    浏览(32)
  • 【面试经典150 | 数组】合并两个有序数组

    本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更…… 专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删: Tag:介绍本题牵涉到的知识点、数据结构; 题目来源:

    2024年02月09日
    浏览(45)
  • 【面试经典150 | 矩阵】矩阵置零

    本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更…… 专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删: Tag:介绍本题牵涉到的知识点、数据结构; 题目来源:

    2024年02月06日
    浏览(45)
  • 【面试经典150 | 数组】移除元素

    本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更…… 专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删: Tag:介绍本题牵涉到的知识点、数据结构; 题目来源:

    2024年02月09日
    浏览(75)
  • 力扣题库刷题笔记36--有效的数独

    1、题目如下:  2、个人Python代码实现如下: 3、个人Python代码思路:         先放一个AI解释的思路:         个人理解,本题思路其实很简单,判断每一行、每一列、每一个3*3的子数独是否存在重复数字,如果存在则返回False,如果不存在则返回True。         1、首先

    2024年02月13日
    浏览(44)
  • 【面试经典150 | 矩阵】生命游戏

    本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更…… 专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删: Tag:介绍本题牵涉到的知识点、数据结构; 题目来源:

    2024年02月07日
    浏览(37)
  • 1.5 面试经典150题 - 轮转数组

    轮转数组 给定一个整数数组  nums ,将数组中的元素向右轮转  k   个位置,其中  k   是非负数。 注意:本题需要原地操作 本题解题思路是: 以[]1, 2, 3, 4, 5, 6, 7] 3 为例 1. 先整体轮转,将 [1, 2, 3, 4, 5, 6, 7]转为 [7, 6, 5, 4, 3, 2, 1] 2. 再局部分别轮转前k个和剩余的,[5, 6, 7,   

    2024年01月16日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包