今天在 LeetCode 做到一道题:有效的数独,难度是中等。

题目

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

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

数独题目

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

数独部分空格内已填入了数字,空白格用 '.' 表示。

代码

如果你只想通过程序,直接复制就行了(。•ˇ‸ˇ•。)

// 个人代码先贴上。做法不一定好,但能通过!
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {

        int bnl = 0;    // 当前块位置(默认从0开始)

        for(int i = 0; i < 9; i++){

            map<char,int> sta_h; 
            map<char,int> sta_l;            
            map<char,int> sta_b;           

            // 检查行
            for(int j = 0; j < 9; j++){
                if(board[i][j] != '.'){
                    if(sta_h[board[i][j]] == 0){
                        sta_h[board[i][j]] = 1;
                    }else{
                        return false;
                    }
                }
            }

            // 检查列
            for(int j = 0; j < 9; j++){
                if(board[j][i] != '.'){
                    if(sta_l[board[j][i]] == 0){
                        sta_l[board[j][i]] = 1;
                    }else{
                        return false;
                    }
                }
            }

            // 检查块            
            int now_h,now_l;

            // 取得当前 3X3 的初始行列
            if((bnl / 3) < 1){
                now_h = 0;
                now_l = (bnl * 3);
            }else if((bnl / 3) >= 1 && (bnl / 3) < 2){
                now_h = 3;
                now_l = ((bnl - 3) * 3);
            }else{
                now_h = 6;
                now_l = ((bnl - 6) * 3);
            }

            if(now_l == -1){
                now_l = 0;
            }

            for(int j = now_l; j < now_l + 3; j++){ // 开始时的列
                   for(int k = now_h; k < now_h + 3; k++){  // 开始时的行
                    if(board[k][j] != '.'){   
                        if(sta_b[board[k][j]] == 0){
                            sta_b[board[k][j]] = 1; 
                        }else{
                            return false;
                        }
                    }
                   }
            }
            bnl ++;

        }

        return true;
    }
};

解题思路

这道题的难点主要在: “数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。”
横竖不能重复是非常简单的,只需要进行遍历并记录每个出现过的信息即可。

在个人代码中创建了三个Map用于储存已被使用过的数据:

  • sta_h: 储存行检测中出现过的值
  • sta_l: 储存列检测中出现过的值
  • sta_b: 储存块检测中出现过的值

每一次扫到非“.”的值时就检测是否存在,存在则直接 return false; 不存在则将map状态转为已存在。

在做这道题时很快就完成了横竖的检测。但 3 X 3 时却卡了很久(当时还以为这题贼简单)

3 X 3 宫内检测

首先我的思路是:在这个 9 X 9 的数独中正好有 9 个 3 X 3 的宫。可以使用一个变量来储存当前遍历到的宫是哪一个,然后可以通过简单的计算算出下一个需要检测的宫的开始位置。

由于需要检测的宫正好也有 9 个,所以可以直接把这个检测程序也放到横竖检查的遍历中。

// 取得当前 3X3 的初始行列
if((bnl / 3) < 1){
    now_h = 0;
    now_l = (bnl * 3);
}else if((bnl / 3) >= 1 && (bnl / 3) < 2){
    now_h = 3;
    now_l = ((bnl - 3) * 3);
}else{
    now_h = 6;
    now_l = ((bnl - 6) * 3);
}

if(now_l == -1){
    now_l = 0;
}

上面的代码可以取得对应宫的初始行和列(这段代码很水,我都不知道自己是怎么搞出来的)

遍历时便可根据取得的初始行列进行检查。中间检查是否存在的程序和横竖的检测是一样的。

for(int j = now_l; j < now_l + 3; j++){ // 开始时的列
    for(int k = now_h; k < now_h + 3; k++){  // 开始时的行
        if(board[k][j] != '.'){   
            if(sta_b[board[k][j]] == 0){
                sta_b[board[k][j]] = 1; 
            }else{
                return false; // 如果中途发现重复数据,直接返回 false
            }
        }
    }
}
bnl ++; // bnl 记录了当前所在的块(当一个块检测完毕,就进入下一个检测)

这道题写的很水,如果有大佬有改进意见请评论给我!万分感激!!

Last modification:May 10th, 2020 at 09:44 pm
如果觉得我的文章对你有用,请随意赞赏