LeetCode-73-SetMatrixZeroes

73矩阵置零

题目描述

• 给定一个 *m* x *n* 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例

示例1

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例2

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

提示：

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -231 <= matrix[i][j] <= 231 - 1

题解一：

     /**
     * 思路：根据数独特点
     *  a. 行不能重复
     *  b. 列不能重复
     *  c. 3x3区域不能重复（boxId = i/3 * 3 + j/3）
     * 分别建立三个字典来记录已经扫描到到值
     * 
     *  时间复杂度 O（1）
     *  空间复杂度 O（1）
     *
     * @param board 数组
     * @return 是否是数独
     */
    public boolean isValidSudoku(char[][] board) {
        // 记录行数字
        Map> row = new HashMap<>(9);
        // 记录列数字
        Map> col = new HashMap<>(9);
        // 记录块数字
        Map> box = new HashMap<>(9);
        for (int i = 0; i < 9; i++) {
            row.put(i, new HashSet<>(9));
            col.put(i, new HashSet<>(9));
            box.put(i, new HashSet<>(9));
        }
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c == '.') {
                    continue;
                }
                int u = c - '0';
                int boxId = i / 3 * 3 + j / 3;
                if (row.get(i).contains(u) || col.get(j).contains(u) || box.get(boxId).contains(u)) {
                    return false;
                }
                row.get(i).add(u);
                col.get(j).add(u);
                box.get(boxId).add(u);
            }
        }
        return true;
    }