数组 - 有效的数独

题目

https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/30/

个人解法

测试用例数(个) 执行用时(ms) 战胜
504 184 32.36%
var unvalidCell = function (row, column) {
    return `${ ~~(row / 3) }_${ ~~(column / 3) }`;
}


/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function(board) {
    var cache = {};
    var rowNum = board.length;
    var columnNum = board[0].length;

    for (var r = 0 ; r < rowNum ; r++) {
        for (var c = 0 ; c < columnNum ; c++) {
            var num = board[r][c];
            var ucell = unvalidCell(r, c);

            if (num !== '.') {
                if (cache[num]) {
                    var numCache = cache[num];

                    if (numCache.notAllowedRows[r] || numCache.notAllowedColumns[c] || numCache.notAllowedCells[ucell]) {
                        return false;
                    } else {
                        numCache.notAllowedRows[r] = true;
                        numCache.notAllowedColumns[c] = true;
                        numCache.notAllowedCells[ucell] = true;
                    }
                } else {
                    cache[num] = {
                        notAllowedRows: {
                            [r]: true
                        },
                        notAllowedColumns: {
                            [c]: true
                        },
                        notAllowedCells: {
                            [ucell]: true
                        }
                    };
                }
            }
        }
    }

    return true;
};

最快解法

测试用例数(个) 执行用时(ms) 战胜
504 104 100%
/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function (board) {

        var columns = [{}, {}, {}, {}, {}, {}, {}, {}, {}],
            rows = [{}, {}, {}, {}, {}, {}, {}, {}, {}],
            boxs = [{}, {}, {}, {}, {}, {}, {}, {}, {}];
        for (var i = 0; i < board.length; i++) {
            for (var j = 0; j < board[i].length; j++) {
                var item = board[i][j];

                if (item != ".") {
                    var box_index = Math.floor((i / 3)) * 3 + Math.floor(j / 3);

                    rows[i][item] = rows[i][item] ? rows[i][item] += 1 : 1;
                    columns[j][item] = columns[j][item] ? columns[j][item] += 1 : 1;
                    boxs[box_index][item] = boxs[box_index][item] ? boxs[box_index][item] += 1 : 1;

                    if(rows[i][item]>1 || columns[j][item]>1 || boxs[box_index][item]>1){
                        return false;
                    }
                }
            }
        }
        return true;
    };

分析

*****
Written by Zheng Yu on 14 May 2019