LeetCode-Valid Sudoku

缺乏、安全感 2022-08-06 15:14 7阅读 0赞

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 `'.'`.

![250px-Sudoku-by-L2G-20050714.svg.png][]

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.

自己的解答：

public boolean isValidSudoku(char[][] board) {
        	for (int i = 0; i < 9; i++) {
        		Map<Character, Integer> map = getMap();
        		for (int j = 0; j < 9; j++) {
        			if (board[i][j] != '.') {
        				Integer times = map.get(new Character(board[i][j]));
        				if (times == 0) {
        					return false;
        				}
        				map.put(new Character(board[i][j]), 0);
        			}
        		}
        	}
        	for (int i = 0; i < 9; i++) {
        		Map<Character, Integer> map = getMap();
        		for (int j = 0; j < 9; j++) {
        			if (board[j][i] != '.') {
        				Integer times = map.get(new Character(board[j][i]));
        				if (times == 0) {
        					return false;
        				}
        				map.put(new Character(board[j][i]), 0);
        			}
        		}
        	}
        	for (int i = 0; i < 9; i += 3) {
        		for (int j = 0; j < 9; j += 3) {
        			Map<Character, Integer> map = getMap();
        			for (int k = i; k < i+3; k++) {
        				for (int l = j; l < j+3; l++) {
        					if (board[k][l] != '.') {
        	    				Integer times = map.get(new Character(board[k][l]));
        	    				if (times == 0) {
        	    					return false;
        	    				}
        	    				map.put(new Character(board[k][l]), 0);
        	    			}
        				}
        			}
        		}
        	}
            return true;
        }
        public Map<Character, Integer> getMap() {
        	Map<Character, Integer> list = new HashMap<Character, Integer>();
        	for (int i = 0; i < 10; i++) {
        		list.put(new Character((char) (i+'0')), 1);
        	}
        	return list;
        }

代码比较，但是比较容易理解：

在贴几个比较好的优化：

class Solution
    {
    public:
        bool isValidSudoku(vector<vector<char> > &board)
        {
            int used1[9][9] = {0}, used2[9][9] = {0}, used3[9][9] = {0};
    
            for(int i = 0; i < board.size(); ++ i)
                for(int j = 0; j < board[i].size(); ++ j)
                    if(board[i][j] != '.')
                    {
                        int num = board[i][j] - '0' - 1, k = i / 3 * 3 + j / 3;
                        if(used1[i][num] || used2[j][num] || used3[k][num])
                            return false;
                        used1[i][num] = used2[j][num] = used3[k][num] = 1;
                    }
    
            return true;
        }
    };

空间换时间了。下面这个把我的map数据结构换成了set。貌似有提高：

public boolean isValidSudoku(char[][] board) {
        for (int i=0; i<9; i++) {
            if (!isParticallyValid(board,i,0,i,8)) return false;
            if (!isParticallyValid(board,0,i,8,i)) return false;
        }
        for (int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                if (!isParticallyValid(board,i*3,j*3,i*3+2,j*3+2)) return false;
            }
        }
        return true;
    }
    private boolean isParticallyValid(char[][] board, int x1, int y1,int x2,int y2){
        Set singleSet = new HashSet();
        for (int i= x1; i<=x2; i++){
            for (int j=y1;j<=y2; j++){
                if (board[i][j]!='.') if(!singleSet.add(board[i][j])) return false;
            }
        }
        return true;
    }

但是能不能，只用一个位标识呢？位操作，更加高效，简洁：

bool isValidSudoku(vector<vector<char> > &board) {
            int rows = board.size();
            int cols = board[0].size();
            int mask=0;
            int val;
            for(int i=0;i<rows;i++){
                mask=0;
                for(int j=0;j<cols;j++){
                    if(board[i][j]!='.'){
                        int val = (int)(board[i][j]-'0');
                        if(mask & (1<<val))
                            return false;
                        else mask |= (1<<val);
                    }
                }
            }
            //rows are checked
            for(int j=0;j<cols;j++){
                mask=0;
                for(int i=0;i<rows;i++){
                    if(board[i][j]!='.'){
                        int val = (int)(board[i][j]-'0');
                        if(mask & (1<<val))
                            return false;
                        else mask |= (1<<val);
                    }
                }
            }
            //cols are checked
            for(int i=0;i<rows;i+=3)
            {
                for(int j=0;j<cols;j+=3)
                {
                    mask=0;
                    for(int k=i;k<=i+2;k++)
                    {
                        for(int l=j;l<=j+2;l++)
                        {
                            if(board[k][l]!='.'){
                                val = (int)(board[k][l]-'0');
                                if(mask&(1<<val))
                                    return false;
                                else mask|=(1<<val);
                            }
                        }
                    }
                }
            }
            return true;
        }

我喜欢！！！

[Sudoku Puzzles - The Rules]: http://sudoku.com.au/TheRules.aspx
[250px-Sudoku-by-L2G-20050714.svg.png]: /images/20220805/4e7ae0ee62634b0f919b551894b4f7bd.png