生命短暂，而你可以决定让它活出灿烂。

题目描述：

有效的数独

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

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

解题代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        // 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

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

        int row[9][9] = {0};
        int col[9][9] = {0};
        int box[9][9] = {0};

        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] == '.') continue;

                int num = board[i][j] - '1';
                if(row[i][num]) return false;
                if(col[j][num]) return false;
                if(box[i/3*3+j/3][num]) return false;

                row[i][num] = 1;
                col[j][num] = 1;
                box[i/3*3+j/3][num] = 1;
            }
        }
        return true;
    }
};

image-20231111185538069

解读与收获：

简单的暴力算法，设置三个9*9的数组分别记录下每行每列每块（9x9）中，数字是否出现过，然后从头遍历该二维数组，经过int num = boardij - ‘1’，将char转int,分别判断：

            if(row[i][num]) return false;  //条件1
            if(col[j][num]) return false;  //条件2
            if(box[i/3*3+j/3][num]) return false; //条件3

其实刷了一些日子的题，我发现自己的思想发生了改变。看到题的第一眼，我总是会下意识否认掉那些“暴力解法”，因为我认为它们太简单，占用资源太多了，如果提交上去很容易出现超时之类的。但是很难否认，看起来困难的题，他的最优解法往往就是暴力算法，直来直去。如果一个题，暴力算法都没有思路的话，那就没资格去思考更优的方法，我之后会先思考每一题的暴力算法，然后进行优化，这是我最近醒悟到的。