算法做题-有效的数独

349次阅读

没有评论

共计 2191 个字符，预计需要花费 6 分钟才能阅读完成。

题目背景：

给一个 9 * 9 矩阵，请你按规则判断该矩阵是否有效

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

返回布尔类型

我的分析

这个题目的要求很清晰，就是要判断在同一行，列，子矩阵内是否有重复的数字。

从行来说，我们可以维护一个表，每次遍历时存储位置的数字，在每个位置进行判断是否已经存在

从列来讲，我们一样可以维护一个表，这表的设计，可以是数字，可以是一个布尔表示，其实布尔标识更方便一点，每个位置设置 true / false，初始化状态下，它们都是 false。

从子矩阵看，可以维护三维数组，标识 [i][j][x]

这样以来，利用布尔值来标记每个位置是否出现过当前数字，当遍历到该位置，即判断布尔值就可以判定该位置是否重复出现了数字，进而判定整个矩阵是否合法

以上的表称为哈希表，哈希表是根据键（Key）而直接访问在内存存储位置的数据结构。

访问每个值的时间复杂度为 O(1)

具体实现

    const rowHas = Array.from({length:9},()=> Array(9).fill(false))  //rowHas[i][x] = false
    const colHas = Array.from({length:9},()=> Array(9).fill(false))
    const subBoxHas = Array.from({length:3},()=>Array.from({length:3},()=>Array(9).fill(false)))

我们已知这是 9 * 9 的矩阵，所以直接用数组的形式表示这个矩阵，这个矩阵用于记录在给定矩阵的相同位置数字的重复情况

接下来我们开始遍历：

for(let i =0;i<board.length;i++) {for(let j =0;j<board[0].length;j++) {
            // 
            const num = board[i][j]   // 当前数字
            if(num == '.') {continue}
              // 从字符串转成数字，将每个字符
            const x = num.charCodeAt(0) - '1'.charCodeAt(0)
            // 重复了
            if(rowHas[i][x] || colHas[j][x] || subBoxHas[Math.floor(i/3)][Math.floor(j/3)][x]) {return false}
            // 将当前点的横竖 以及子矩阵 记录  便于后续使用
            rowHas[i][x] = colHas[j][x] = subBoxHas[Math.floor(i/3)][Math.floor(j/3)][x] = true
          
        }
    }

开启一个嵌套循环，用于遍历 board 中每一个字符，当遇到. 就跳过，继续下一次遍历，如果遍历到某个位置的横向纵向甚至子矩阵的某个位置为 true，表示在该横向纵向子矩阵内已经存在该数字，则直接返回 false，结束执行否则，记录该位置

具体完整代码 js

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function(board) {
    // 每一行维护哈希表，检查唯一
    // 定义每行 每列 每个宫格的哈希 通过循环进行记录
    const rowHas = Array.from({length:9},()=> Array(9).fill(false))  //rowHas[i][x] = false
    const colHas = Array.from({length:9},()=> Array(9).fill(false))
    const subBoxHas = Array.from({length:3},()=>Array.from({length:3},()=>Array(9).fill(false)))

    for(let i =0;i<board.length;i++) {for(let j =0;j<board[0].length;j++) {
            // 
            const num = board[i][j]   // 当前数字
            if(num == '.') {continue}
              // 从字符串转成数字，将每个字符
            const x = num.charCodeAt(0) - '1'.charCodeAt(0)
            // 重复了
            if(rowHas[i][x] || colHas[j][x] || subBoxHas[Math.floor(i/3)][Math.floor(j/3)][x]) {return false}
            // 将当前点的横竖 以及子矩阵 记录  便于后续使用
            rowHas[i][x] = colHas[j][x] = subBoxHas[Math.floor(i/3)][Math.floor(j/3)][x] = true
          
        }
    }
    return true

};

这个方法的时间复杂度 0(n^2) 空间复杂度 O(n^2)