LeetCode 36. 有效的数独 C++&java

xiaoxiao2021-02-28  6

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

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

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

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

示例 1:

输入: [ ["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ] 输出: true

示例 2:

输入: [   ["8","3",".",".","7",".",".",".","."],   ["6",".",".","1","9","5",".",".","."],   [".","9","8",".",".",".",".","6","."],   ["8",".",".",".","6",".",".",".","3"],   ["4",".",".","8",".","3",".",".","1"],   ["7",".",".",".","2",".",".",".","6"],   [".","6",".",".",".",".","2","8","."],   [".",".",".","4","1","9",".",".","5"],   [".",".",".",".","8",".",".","7","9"] ] 输出: false 解释: 除了第一行的第一个数字从 5 改为 8 以外,空格内其他数字均与 示例1 相同。

但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

C++: 思路没什么难得,就是检测每个元素所在的行列和区块是否有相同的即可

class Solution { public:     bool isValidSudoku(vector<vector<char>>& board) {                  for(int i =0;i< 9 ;i++)         {   for(int j = 0 ; j< 9; j++)             {                if(board[i][j] != '.')   //                {                   for(int k = 0; k<9 ;k++)                   {                       if(k != i &&board[k][j] == board[i][j]) return false ;                   }                   for(int k = 0; k<9 ;k++)                   {                       if(k != j && board[i][k] == board[i][j]) return false;                   }                   if(i<3&&j<3)                   {                       for(int k1 = 0;k1<3 ;k1++ )                       {    for(int k2 = 0;k2<3;k2++)                           {                               if(i !=k1&&j!=k2&&board[i][j] == board[k1][k2]) return false ;                           }                       }                   }                   if(i<6&&j<3&&i>=3)                   {                       for(int k1 = 3;k1<6 ;k1++ )                       {    for(int k2 = 0;k2<3;k2++)                           {                               if(i !=k1&&j!=k2)                               {                                   if(board[i][j] == board[k1][k2]) return false;                               }                           }                       }                   }                                      if(i<3&&j<6&&j>=3)                   {                       for(int k1 = 0;k1<3 ;k1++ )                       {    for(int k2 = 3;k2<6;k2++)                           {                               if(i !=k1&&j!=k2&&board[i][j] == board[k1][k2]) return false;                           }                       }                   }                     if(i<3&&j<9&&j>=6)                   {                       for(int k1 = 0;k1<3 ;k1++ )                       {    for(int k2 = 6;k2<9;k2++)                           {                               if(i !=k1&&j!=k2&&board[i][j] == board[k1][k2]) return false;                           }                       }                   }                   if(i<6&&j<6&&i>=3&&j>=3)                   {                       for(int k1 = 3;k1<6 ;k1++ )                       {    for(int k2 = 3;k2<6;k2++)                           {                                 if(i !=k1&&j!=k2&&board[i][j] == board[k1][k2]) return false;                           }                       }                   }                     if(i<9&&j<3&&i>=6)                    {                      for(int k1 = 6;k1<9 ;k1++ )                       {   for(int k2 = 0;k2<3;k2++)                           {                              if(i !=k1&&j!=k2&&board[i][j] == board[k1][k2]) return false;                           }                       }                    }                   if(i<9&&j<6&&i>=6&&j>=3)                   {                       for(int k1 = 6;k1<9 ;k1++ )                       {    for(int k2 = 3;k2<6;k2++)                           {                               if(i !=k1&&j!=k2&&board[i][j] == board[k1][k2]) return false;                           }                       }                   }                                       if(i<6&&j<9&&i>=3&&j>=6)                   {                       for(int k1 = 3;k1<6 ;k1++ )                       {    for(int k2 = 6;k2<9;k2++)                           {                              if(i !=k1&&j!=k2&&board[i][j] == board[k1][k2]) return false;                           }                       }                   }                   if(i<9&&j<9&&i>=6&&j>=6)                   {                       for(int k1 = 6;k1<9 ;k1++ )                       {    for(int k2 = 6;k2<9;k2++)                           {                               if(i !=k1&&j!=k2&&board[i][j] == board[k1][k2]) return false;                           }                       }                   }                 }             }         }         return true ;     } }; JAVA:

class Solution {     public boolean isValidSudoku(char[][] board) {         for(int i = 0 ; i<9;i++)         {             for(int j = 0 ; j<9;j++)             {                 if(board[i][j] != '.')                 {                     for(int k = 0 ; k<9;k++)                     {                         if(k != i&&board[k][j] == board[i][j]) return false ;                     }                     for(int k = 0 ; k<9;k++)                     {                         if(k != j&&board[i][k] == board[i][j]) return false ;                     }                     if(i<3&&j<3)     //3.3                     {                         for(int k1 = 0;k1<3;k1++)                          {                             for(int k2 = 0;k2<3;k2++)                              {                                 if(k1 != i&&k2 !=j&&board[k1][k2]==board[i][j]) return false ;                             }                         }                     }                     if(i<3&&j<6&&j>=3)   // 3,6                     {                         for(int k1 = 0;k1<3;k1++)                          {                             for(int k2 = 3;k2<6;k2++)                              {                                 if(k1 != i&&k2 !=j&&board[k1][k2]==board[i][j]) return false ;                             }                         }                     }                                         if(i<3&&j<9&&j>=6)    // 3,9                     {                         for(int k1 = 0;k1<3;k1++)                          {                             for(int k2 = 6;k2<9;k2++)                              {                                 if(k1 != i&&k2 !=j&&board[k1][k2]==board[i][j]) return false ;                             }                         }                     }                                         if(i<6&&j<3&&i>=3)   // 6,3                     {                         for(int k1 = 3;k1<6;k1++)                          {                             for(int k2 = 0;k2<3;k2++)                              {                                 if(k1 != i&&k2 !=j&&board[k1][k2]==board[i][j]) return false ;                             }                         }                     }                     if(i<6&&j<6&&i>=3&&j>=3) // 6,6                     {                         for(int k1 = 3;k1<6;k1++)                          {                             for(int k2 = 3;k2<6;k2++)                              {                                 if(k1 != i&&k2 !=j&&board[k1][k2]==board[i][j]) return false ;                             }                         }                     }                                         if(i<6&&j<9&&i>=3&&j>=6)  // 6,9                     {                         for(int k1 = 3;k1<6;k1++)                          {                             for(int k2 = 6;k2<9;k2++)                             {                                 if(k1 != i&&k2 !=j&&board[k1][k2]==board[i][j]) return false ;                             }                         }                     }                                         if(i<9&&j<9&&i>=6&&j>=6) //9.9                     {                         for(int k1 = 6;k1<9;k1++)                          {                             for(int k2 = 6;k2<9;k2++)                             {                                 if(k1 != i&&k2 !=j&&board[k1][k2]==board[i][j]) return false ;                             }                         }                     }                                         if(i<9&&j<3&&i>=6)   //9,3                     {                         for(int k1 = 6;k1<9;k1++)                          {                             for(int k2 = 0;k2<3;k2++)                              {                                 if(k1 != i&&k2 !=j&&board[k1][k2]==board[i][j]) return false ;                             }                         }                     }                                         if(i<9&&j<6&&i>=6&&j>=3)   //9.6                     {                         for(int k1 = 6;k1<9;k1++)                          {                             for(int k2 = 3;k2<6;k2++)                             {                                 if(k1 != i&&k2 !=j&&board[k1][k2]==board[i][j]) return false ;                             }                         }                     }                                                          }                              }         }         return true ;     } }

转载请注明原文地址: https://www.6miu.com/read-2150300.html

最新回复(0)