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

LeetCode_Valid Sudoku

編輯:關於C++

一.題目

Valid Sudoku

Total Accepted: 29804 Total Submissions: 109584My Submissions

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.

Show Tags Have you met this question in a real interview? Yes No

Discuss


 

二.解題技巧

這道題比較簡單,就是遍歷棋盤的所有位置,查看每一個位置上的元素是否滿足Sudoku的要求,也就是每一行,每一列以及每個小9×9的區域是否存在相同的元素,如果存在相同的元素,即為不合法。對於判斷一個元素是否在某一行,某一列或者某個小區域內,我的實現是將定義了9個整數代表每一列,9個整數代表每一行,9個元素代表了9個小的9×9的區域,因此,用每一個整數的第1到第九位表示某個元素是否在該列,該行或該小區域中。通過位操作可以判斷該元素是否存在。

三.實現代碼

#include 

#include 

using namespace std;

class Solution
{
private:
    bool isExist(int &Input, int Number)
    {
        if (Input & (1 << Number))
        {
            return true;
        }

        Input =  Input | (1 << Number);
        return false;
    }


public:
    bool isValidSudoku(vector > &board)
    {
        int X_value[9] = {0};
        int Y_value[9] = {0};
        int Inside[9] = {0};

        for (int Index_y = 0; Index_y < 9; Index_y++)
        {
            vector &TmpRow = board[Index_y];

            for (int Index_x = 0; Index_x < 9; Index_x++)
            {
                if (TmpRow[Index_x] == '.')
                {
                    continue;
                }

                int TmpValue = TmpRow[Index_x] - '0';

                // is valid in Index_x row
                if (isExist(X_value[Index_x], TmpValue))
                {
                    return false;
                }

                // is valid in Index_y col
                if (isExist(Y_value[Index_y], TmpValue))
                {
                    return false;
                }

                // is valid in 3*3 sub block
                if (isExist(Inside[Index_x / 3 + Index_y / 3 * 3] , TmpValue))
                {
                    return false;
                }
            }
        }

        return true;

    }
};





四.體會

這道題基本上不需要什麼算法,只是在考慮如何判斷一個元素是否已經存在時需要稍微考慮下,我的實現用來27個整數的第1到第9位來判斷一個元素是否已經存在。其實使用三個整數就基本上可以完成這樣的任務了,只不過這樣處理起來稍微有點復雜。 這道題也算是一道水題,可以用於練練手。


 





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