[TOC]

前端与算法 leetcode 36. 有效的数独

题目描述

判断一个 9×9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能出现一次。

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

示例 1:

输入:
[["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: true
示例 2:

输入:
[["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例 1 相同。但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。说明:

一个有效的数独（部分已被填充）不一定是可解的。

• 只需要根据以上规则，验证已经填入的数字是否有效即可。
• 给定数独序列只包含数字 1-9 和字符 ‘.’。
• 给定数独永远是 9×9 形式的。

36. 有效的数独

概要

这道题的解决方案有很多种, 由于数组格式和长度都是固定的, 我看到有些神仙甚至写死小宫格的坐标来答题 …, 题目的要求是行 / 列 /3* 3 小宫格没有重复数字, 在一次迭代内完成即可

提示

舍去取整

解析

js 对 map 操作有较强的优势, 既能通过 new Map 的方式建立一个 hash 表, 也能直接构建对象的方式来操作, 这里为了简化操作直接使用对象, 行和列的操作没有难度, 小宫格的操作要小心, 整除时若带有小数部分,js 默认四舍五入, 其他语言默认舍去小数部分, 小宫格计算方式 Math.floor((i / 3)) * 3 + Math.floor(j / 3) 中注意使用 Math.floor 舍去取整, 判断是否重复时只需要判断对象的 val 值是否大于 1 即可

算法

/**
 * @param {character[][]} board
 * @return {boolean}
 */
// eslint-disable-next-line complexity
var isValidSudoku = function (board) {let [rows, columns, boxes] = [[], [], []];
    for (let i = 0; i < 9; i++) {rows[i] = {};// 行数据
        columns[i] = {}; // 列数据
        boxes[i] = {}; // 小宫格}
    // const fun = (r, x, y) => (r[x][y] ? r[x][y]++ : (r[x][y] = 1));
    for (let i = 0; i < board.length; i++) {for (let j = 0; j < board[i].length; j++) {let num = board[i][j];
            if (num !== '.') {let n = parseInt(num, 10);
                // js 中 1 /3* 3 计算结果为 1 但是按理说应该是 0.999 无限(浮点误差) 而 java 中 1 /3* 3 则取值为 0, 浮点数默认舍去 0
                let boxix = Math.floor((i / 3)) * 3 + Math.floor(j / 3);
                // fun(rows, i, n);
                // fun(columns, j, n);
                // fun(boxes, boxix, n);
                rows[i][n] ? rows[i][n]++ : (rows[i][n] = 1);
                columns[j][n] ? columns[j][n]++ : (columns[j][n] = 1);
                boxes[boxix][n] ? boxes[boxix][n]++ : (boxes[boxix][n] = 1);
                if (rows[i][n] >= 2 || columns[j][n] >= 2 || boxes[boxix][n] >= 2) {return false;}
            }
        }
    }
    return true;
};

传入测试用例的运行结果

测试用例

input:[['5', '3', '.', '.', '7', '.', '.', '.', '.'],['6', '.', '.', '1', '9', '5', '.', '.', '.'],['.', '9', '8', '.', '.', '.', '.', '6', '.'],['8', '.', '.', '.', '6', '.', '.', '.', '3'],['4', '.', '.', '8', '.', '3', '.', '.', '1'],['7', '.', '.', '.', '2', '.', '.', '.', '6'],['.', '6', '.', '.', '.', '.', '2', '8', '.'],['.', '.', '.', '4', '1', '9', '.', '.', '5'],['.', '.', '.', '.', '8', '.', '.', '7', '9'],]
output:true

执行结果

执行用时 :84 ms, 在所有 javascript 提交中击败了 92.76% 的用户
内存消耗 :38.1 MB, 在所有 javascript 提交中击败了 47.58% 的用户

GitHub 仓库

36. 有效的数独