Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >[Leetcode][python]Valid Sudoku/有效的数独

[Leetcode][python]Valid Sudoku/有效的数独

作者头像
蛮三刀酱
发布于 2019-03-26 08:24:10
发布于 2019-03-26 08:24:10
69500
代码可运行
举报
运行总次数:0
代码可运行

题目大意

判断一个数度棋盘是否合理,不需要能解。 1. 横向0-9 2. 纵向0-9 3. 小方格0-9

解题思路

这台网上很多答案都在暴力穷举,正确的python答案应该是用set。

代码

set()

leetcode内他人提交的答案,膜一下。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        seen = set()
        for i in range(9):
            for j in range(9):
                c = board[i][j]
                if c == '.':
                    continue
                if (i, c) in seen or (c, j) in seen or (i/3, j/3, c) in seen:
                    return False
                seen.add((i, c))
                seen.add((c, j))
                seen.add((i/3, j/3, c))
        return True

dict

我提交的,我强行按照标签给的hash table来做,把整个三中需要验证的都写为key,然后去组合这些key名,十分容易看懂,但最后通过时ms很高。所以用hash table的合理方案就是答案1(set)!!!

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        Sudoku_dict = {'row_0':[], 'row_1':[], 'row_2':[], 'row_3':[], 'row_4':[], 'row_5':[], 'row_6':[], 'row_7':[], 'row_8':[],
                       'col_0':[], 'col_1':[], 'col_2':[], 'col_3':[], 'col_4':[], 'col_5':[], 'col_6':[], 'col_7':[], 'col_8':[],
                       'squ_00':[], 'squ_01':[], 'squ_02':[], 'squ_10':[], 'squ_11':[], 'squ_12':[], 'squ_20':[], 'squ_21':[], 'squ_22':[]}
        for i in range(9):
            for j in range(9):
                if board[i][j]=='.':
                    continue
                temp = board[i][j]
                row_name = 'row_' + str(i)
                col_name = 'col_' + str(j)
                squ_name = 'squ_' + str((i)/3) + str((j)/3)
                # print row_name, col_name, squ_name
                if temp in Sudoku_dict[row_name]:
                    return False
                else:
                    Sudoku_dict[row_name].append(temp)
                if temp in Sudoku_dict[col_name]:
                    return False
                else:
                    Sudoku_dict[col_name].append(temp)
                if temp in Sudoku_dict[squ_name]:
                    return False
                else:
                    Sudoku_dict[squ_name].append(temp)
        # print Sudoku_dict
        return True

总结

set和dict类似,也是一组key的集合,但不存储value。由于key不能重复,所以,在set中,没有重复的key。

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

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

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

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

评论
登录后参与评论
暂无评论
推荐阅读
leetcode 37. Sudoku Solver 36. Valid Sudoku 数独问题
三星机试也考了类似的题目,只不过是要针对给出的数独修改其中三个错误数字,总过10个测试用例只过了3个与世界500强无缘了
流川疯
2019/01/18
1K0
leetcode: 36. Valid Sudoku
Problem # 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 '.'. # # A partially filled sudoku which is valid. # # Note: # A valid
JNingWei
2018/09/27
5400
leetcode: 36. Valid Sudoku
Array - 36. Valid Sudoku
Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
ppxai
2020/09/23
4040
Array - 36. Valid Sudoku
Leetcode: Valid Sudoku
题目: Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
卡尔曼和玻尔兹曼谁曼
2019/01/22
4680
数据结构算法操作试题(C++/Python)——有效的数独
leetcode 链接:https://leetcode-cn.com/problems/valid-sudoku/submissions/
莫斯
2020/09/10
3440
数据结构算法操作试题(C++/Python)——有效的数独
Leetcode 题目解析之 Valid Sudoku
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
ruochen
2022/01/14
1.2K0
Python3刷题系列(五)
英文版:https://leetcode.com/problems/number-of-islands/description/
用户5473628
2019/08/08
5070
[Leetcode][python]Sudoku Solver/解数独
上一题hashtable的解法效率很高,想挪过来判断,但始终没修改成功,以后有空改好它,在这里做备份。
蛮三刀酱
2019/03/26
8930
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 '.'. image.png A partially filled sudoku which is valid. Note: A valid Sudoku boar
triplebee
2018/01/12
8490
Leetcode 36 Valid Sudoku 数独的合法性判断
数独的暴力回溯解法和Python GUI版
数独起源于18世纪初瑞士数学家欧拉等人研究的拉丁方阵,20世纪70年代,经过美国及日本学者的推广和改良,定名为数独(Sudoku),大致的意思是“独个的数字”或“只出现一次的数字”。
蛰虫始航
2019/12/12
1.6K0
数独的暴力回溯解法和Python GUI版
详解Apache Hudi Schema Evolution(模式演进)
Schema Evolution(模式演进)允许用户轻松更改 Hudi 表的当前模式,以适应随时间变化的数据。从 0.11.0 版本开始,支持 Spark SQL(spark3.1.x 和 spark3.2.1)对 Schema 演进的 DDL 支持并且标志为实验性的。
ApacheHudi
2022/07/11
2.2K0
leetcode: explore-array-30 有效的数独
https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/30/
用户7685359
2020/08/21
4050
Swift 有效的数独 - LeetCode
判断一个数独是否有效,根据:Sudoku Puzzles - The Rules。 (数独规则: 每一行不能有重复的数字;每一列不能有重复的数字;将数独框划分为三行三列,没9个小方格不能有重复;)
韦弦zhy
2018/09/11
9100
Swift 有效的数独 - LeetCode
Leetcode 36. Valid Sudoku
版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn.net/Quincuntial/article/details/83450552
Tyan
2019/05/25
3310
LeetCode 0036 - Valid Sudoku
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
Reck Zhang
2021/08/11
2860
回溯法+约束编程-LeetCode37(数独扫雷问题、Tuple使用)
在Python中,大家都知道tuple这个概念,是一个只读的元素容器,容器内的元素数据类型可以不同,而在CPP中大部分的容器只能储存相同数据类型的数据,而std::pair函数是为数不多的可以将两个不同类型的值放到一起。我们今天说的tuple是std::pair的推广,表示固定大小的异类值的汇集。 std::tuple是C++11标准开始提出的,其有很多用途,比如一个函数如果拥有多个不同类型的返回值,就可以直接返回一个tuple.不用再像以前一样,定义一个class或者struct保存结果进行返回那么麻烦了! 其使用的重要函数有:
算法工程师之路
2019/10/08
9850
回溯法+约束编程-LeetCode37(数独扫雷问题、Tuple使用)
攻克最后一关:解数独!
力扣题目链接:https://leetcode-cn.com/problems/sudoku-solver
代码随想录
2021/11/05
7280
LeetCode-36-Valid-Sudoku
判断一个二维数组是不是数独数组。要求是:同行同列,斜对角不能有相同的数组,这里需要定义三个数组,当然参考了一下讨论区一个大神的代码。采用行列,竖列和斜列。其中比较惊艳的是k=i/3*3+j/3;这里可以直接得到斜对角的元素。
小二三不乌
2018/08/07
3960
LeetCode-36-Valid-Sudoku
【每日一题】36. Valid Sudoku
Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
公众号-不为谁写的歌
2020/08/12
2800
【每日一题】36. Valid Sudoku
LeetCode 36. 有效的数独
判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。
freesan44
2020/06/03
3690
相关推荐
leetcode 37. Sudoku Solver 36. Valid Sudoku 数独问题
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验