程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode36:Valid Sudoku

LeetCode36:Valid Sudoku

編輯:關於C++

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

\

A partially filled sudoku which is valid.

 

Note:

A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

 

這道題一看就是用空間來換取時間,正常情況下應該每行進行比較,每列進行比較,然後每一個網格進行比較,但是每個比較都有一個雙層循環。

可以借助STL中的set來進行判斷是否已經存在該元素,典型的空間換取時間的方法。

runtime:24ms

 

class Solution {
public:
    bool isValidSudoku(vector>& board) {
        unordered_set rows[9];//每一行一個set來判斷改行是否存在重復元素
        unordered_set columns[9];//每一列一個set用來判斷該列是否存在重復元素
        unordered_set grids[3][3];//每一個3*3網格一個set來判斷該網格是否存在重復元素
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(board[i][j]!='.')
                {
                    char tmp=board[i][j];
                    if(!rows[i].insert(tmp).second||!columns[j].insert(tmp).second||!grids[i/3][j/3].insert(tmp).second)
                    return false;
                    
                }
            }
            
        }
        return true;
        
    }
};
除了使用STL外由於這道題比較簡單,可以使用和上面同樣的方式自己定義一個掩碼。

 

用一個int rows[9][9]來記錄行的掩碼

用一個int column[9][9]來記錄列的掩碼

用一個int gird[3][3][9]來記錄網格的掩碼。

runtime:12ms

運行時間少了一半!!!!

 

class Solution {
public:  
       bool isValidSudoku(vector>& board) {
             int rows[9][9]={0};
             int columns[9][9]={0};
             int grids[3][3][9]={0};
            
            for(int i=0;i<9;i++)
            {
                for(int j=0;j<9;j++)
                {
                    if(board[i][j]!='.')
                    {
                           char tmp=board[i][j];
                           int index=tmp-'1';
                           
                           if(rows[i][index]++)
                               return false;
                               
                           if(columns[j][index]++)
                                return false;
                                
                            if(grids[i/3][j/3][index]++)
                                return false;  
                    }
            
                }
            }
            return true;
            
        }
        
        
};




 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved