Leetcode 36. 有效的数独（DAY 150) ---- LeetCode 精选 TOP 面试题

忘是亡心i 2022-09-07 04:59 110阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（首刷自解 未优化空间）
     *  代码实现（首刷自解 优化版）

--------------------

## 原题题目 ##

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70]

--------------------

## 代码实现（首刷自解 未优化空间） ##

--------------------

class Solution { 
    public:
        bool isValidSudoku(vector<vector<char>>& board) { 
            vector<unordered_set<char>> boxs(9),rows(9),lines(9);
            for(int x=0;x<board.size();++x)
            { 
                for(int y=0;y<board[0].size();++y)
                { 
                    if(board[x][y] == '.')   continue;
                    char chr = board[x][y];
                    int boxpos = (x/3)*3+y/3;
                    if(rows[x].find(chr) != rows[x].end()||lines[y].find(chr) != lines[y].end() || boxs[boxpos].find(chr) != boxs[boxpos].end()) 
                        return false;
                    rows[x].emplace(chr);
                    lines[y].emplace(chr);
                    boxs[boxpos].emplace(chr);
                }
            }
            return true;
        }
    };

--------------------

## 代码实现（首刷自解 优化版） ##

--------------------

class Solution { 
    public:
        bool isValidSudoku(vector<vector<char>>& board) { 
            vector<vector<bool>> boxs(9,vector<bool>(10,false)),rows(boxs),lines(boxs);
            for(int x=0;x<board.size();++x)
            { 
                for(int y=0;y<board[0].size();++y)
                { 
                    if(board[x][y] == '.')   continue;
                    int chr = board[x][y] - '0';
                    int boxpos = (x/3)*3+y/3;
                    if(rows[x][chr] || lines[y][chr] || boxs[boxpos][chr]) 
                        return false;
                    rows[x][chr] = true;
                    lines[y][chr] = true;
                    boxs[boxpos][chr] = true;
                }
            }
            return true;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70]: /images/20220829/4da5a188afeb4838aa54933a2e4a793a.png