Leetcode 的强大之处, 挺多的.
本文写的是, 其强大的讨论区.
讨论区里面, 有各种具有启发性的代码.
(换句话说, 就是有很强的代码. 看了, 觉得脑洞大开, 大神们把语言的语法特性发挥到了极致)
里面有各种常见语言的实现
( 这里指 Leetcode 主站的, 中文站点的同一功能弱了一点 )
进入 Leetcode 的题目,
进入讨论区, 里面的讨论挺多的, 这道题就有 470 个帖子.
本文推荐选择 "Most Votes",
事实就是得分高的代码, 看起来爽
也可以搜索一下自己关心的, 一般是按语言来搜索.
就 Leetcode 算法题, 本文认为有了 Leetcode 的讨论区, 和官方题解 (有些没有, 最近的题都有)
其他的资料...... , 都好像有些弱 (不喜欢英语的少年, 除外)
题目描述: 36. 有效的数独
判断一个 9x9 的数独是否有效. 只需要根据以下规则, 验证已经填入的数字是否有效即可.
数字 1-9 在每一行只能出现一次. 数字 1-9 在每一列只能出现一次. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次.
上图是一个部分填充的有效的数独.
数独部分空格内已填入了数字, 空白格用 '.' 表示. 示例 :
输入:
输出: true
题解 ( 改进前):
下面的解法, 非常直观, 根据数独的成立条件, 分三次检查数字, 按行, 按列, 按块
(先横着来, 再竖着来, 最后一块一块来)
因为数独有数字的唯一性, 这里使用散列集合
每一次处理, 通过的情况分两种,
扫描一轮, 1-9 刚刚好. 或者含有 ''.", 其他的数字各不相同.
- class Solution {
- func isValidSudoku(_ board: [[Character]]) -> Bool {
- let count = board.count
- var set = Set<Character>()
- for i in 0..<count{
- // 横着来, 按行, 检查数字
- set = Set(board[i])
- var num = board[i].reduce(0 , {(result : Int, char : Character)
- in
- var cent = 0
- if String(char) == "."{
- cent = 1
- }
- return result + cent
- })
- // 每一次处理, 通过本次循环的情况分两种,
- // 扫描一轮, 1-9 刚刚好. 或者含有 ".", 其他的数字各不相同.
- // 这里做了一个针对处理
- if num> 0 , count - num != set.count - 1{
- return false
- }
- else if num == 0, set.count != count{
- return false
- }
- // 竖着来, 按列, 检查数字
- set = Set(board.reduce([Character]() , { resultArray, chars in
- return resultArray + [chars[i]]
- }))
- num = board.reduce(0 , {(result : Int, chars : [Character])
- in
- var cent = 0
- if String(chars[i]) == "."{
- cent = 1
- }
- return result + cent
- })
- if num> 0 , count - num != set.count - 1{
- return false
- }
- else if num == 0, set.count != count{
- return false
- }
- // 一块一块来, 按块, 检查数字
- let characters = board.flatMap{
- return $0
- }
- let fisrtMiddle = ( i/3 ) * 27 + ( i % 3 ) * 3 + 1
- let secondMiddle = fisrtMiddle + 9
- let thirdMiddle = fisrtMiddle + 18
- // 找出每一块
- let arrayThree = [characters[fisrtMiddle - 1], characters[fisrtMiddle], characters[fisrtMiddle + 1],
- characters[secondMiddle - 1], characters[secondMiddle], characters[secondMiddle + 1],
- characters[thirdMiddle - 1], characters[thirdMiddle], characters[thirdMiddle + 1]]
- set = Set(arrayThree)
- num = arrayThree.reduce(0 , {(result : Int, char : Character)
- in
- var cent = 0
- if String(char) == "."{
- cent = 1
- }
- return result + cent
- })
- if num> 0 , count - num != set.count - 1{
- return false
- }
- else if num == 0, set.count != count{
- return false
- }
- }
- return true
- }
- }
Code Review :
算法上的提高
没必要计算 "." 的个数. 先处理数据, 把 "." 过滤掉, 再创建散列集合.
按行, 按列, 按块查找重复数字, 就直观了很多. 不需要考虑 "." 的干扰.
命名要规范,
怎么知道 set 里面包含什么?
不清晰, 不知道 num 是记录的是什么的数量.
cent 和 arrayThree 是什么鬼?
改进代码
if String(char) == "." , 可以直接写成 if char == "."
Swift 中 "." 是字符串的字面量, 也是字符的字面量. 不需要把字符转化为字符串.
改进闭包
按行, 计算一次循环, 不包含 "." 的
- var num = board[i].reduce(0 , {(result : Int, char : Character)
- in
- var cent = 0
- if String(char) == "."{
- cent = 1
- }
- return result + cent
- })
1⃣ 简写闭包, 用三目, 减少临时变量
- var num = board[i].reduce(0 , {(result, char) in
- char == "." ? result + 1 : result
- })
这样处理更高效
先把数据处理干净, 过滤 "."
- let rowDigits = board[i].filter { $0 != "." }
- if rowDigits.count != Set(rowDigits).count {
- return false
- }
- set = Set(board.reduce([Character]() , { resultArray, chars in
- return resultArray + [chars[i]]
- }))
2⃣ 科学类型转换
- let column = board.map {
- $0[i]
- } // Column #i
- set = Set(column)
找出每一块
- let fisrtMiddle = ( i/3 ) * 27 + ( i % 3 ) * 3 + 1
- let secondMiddle = fisrtMiddle + 9
- let thirdMiddle = fisrtMiddle + 18
- // 找出每一块
- let arrayThree = [characters[fisrtMiddle - 1], characters[fisrtMiddle], characters[fisrtMiddle + 1],
- characters[secondMiddle - 1], characters[secondMiddle], characters[secondMiddle + 1],
- characters[thirdMiddle - 1], characters[thirdMiddle], characters[thirdMiddle + 1]]
3⃣ 使用数组片段 ( slice ), 发挥高阶函数的威力
- let firstRow = 3 * (i / 3)
- let firstCol = 3 * (i % 3)
- let block = board[firstRow..<firstRow+3].flatMap {
- $0[firstCol..<firstCol+3]
- }
最后的代码:
- class Solution {
- func isValidSudoku(_ board: [[Character]]) -> Bool {
- for i in 0..<9 {
- // 按行, 检查数字
- let rowDigits = board[i].filter { $0 != "." }
- if rowDigits.count != Set(rowDigits).count {
- return false
- }
- // 按列, 检查数字
- let colDigits = board.map { $0[i] }.filter { $0 != "." }
- if colDigits.count != Set(colDigits).count {
- return false
- }
- // 按块, 检查数字
- let firstRow = 3 * (i / 3)
- let firstCol = 3 * (i % 3)
- let blockDigits = board[firstRow..<firstRow+3].flatMap { $0[firstCol..<firstCol+3]}
- .filter { $0 != "." }
- if blockDigits.count != Set(blockDigits).count {
- return false
- }
- }
- return true
- }
- }
另一种解法, 更加的函数式, 性能差一些
使用 27 个散列集合, 对应 9 次循环 X 3 种方式 ( 按行, 按块, 按列)
排除掉 "." , 有重复的数字, 就返回错误.
两层遍历顺利完成后, 返回成功.
- class Solution {
- func isValidSudoku(_ board: [[Character]]) -> Bool {
- var rowSets = Array(repeating: Set<Character>(), count: 9)
- var colSets = Array(repeating: Set<Character>(), count: 9)
- var blockSets = Array(repeating: Set<Character>(), count: 9)
- for (i, row) in board.enumerated() {
- for (j, char) in row.enumerated() where char != "." {
- if !rowSets[i].insert(char).inserted {
- return false
- }
- if !colSets[j].insert(char).inserted {
- return false
- }
- let block = (i / 3) + 3 * (j / 3)
- if !blockSets[block].insert(char).inserted {
- return false
- }
- }
- }
- return true
- }
- }
Leetcode 链接: https://leetcode.com/problems/valid-sudoku/
感谢 Martin R 大神 code review 我的代码
相关代码: https://github.com/BoxDengJZ/leet_algo_101
强大的代码: Python 实现
来源: https://juejin.im/post/5c03cdd051882518805ae375