Stroke Practice - 62 Valid Sudokus

62 有效的数独

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

数字 1-9 在每一行只能出现一次.

数字 1-9 在每一列只能出现一次.

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

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

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

示例 1:

输入:

53…7…

6…195…

.98…6.

8…6…3

4…8.3…1

7…2…6

.6…28.

…419…5

…8…79

输出: true

示例 2:

输入:

83…7…

6…195…

.98…6.

8…6…3

4…8.3…1

7…2…6

.6…28.

…419…5

…8…79

输出: false

解释: 除了第一行的第一个数字从 5 改为 8 以外,空格内其他数字均与 示例1 相同.

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

说明:

一个有效的数独（部分已被填充）不一定是可解的.

只需要根据以上规则,验证已经填入的数字是否有效即可.

给定数独序列只包含数字 1-9 和字符 ‘.’ .

给定数独永远是 9x9 形式的.

可使用以下main函数：

int main()

{

vector<vector<char> > board;

char ch;

for(int i=0; i<9; i++)

{

    vector<char> aLine;

    for(int j=0; j<9; j++)

    {

        cin>>ch;

        aLine.push_back(ch);

    }

    board.push_back(aLine);

}

bool res=Solution().isValidSudoku(board);

cout<<(res?"true":"false")<<endl;

return 0;

}

2.输入说明
输入9行,每行9个字符,只包含数字 1-9 和字符 ‘.’
3.输出说明
输出true或false
4.范例
输入
83…7…
6…195…
.98…6.
8…6…3
4…8.3…1
7…2…6
.6…28.
…419…5
…8…79
输出
false
5.代码

#include<iostream>
#include<map>
#include<string>
#include<unordered_map>
#include<algorithm>
#include<string.h>//memset函数
using namespace std;



bool cmp(pair<char, int> a, pair<char, int>b)
{
    
	return a.second == b.second?a.first<b.first:a.second>b.second;//The most crucial part of the question,注意写法！
}


string OrderbyChar(string s)
{
    
	//给定一个字符串,请将字符串里的字符按照出现的频率降序排列,如果频率相同,Then according to the characterASCII码升序排列.
	string res;//结果字符串
	unordered_map<char, int>hash;//记录每个字符出现次数
	vector<pair<char, int> > v;//使用pair记录对应关系
	for (auto c : s)//遍历字符串
		hash[c]++;
	for (auto it : hash)
		v.emplace_back(it);//directly to eachhash元素插入v中
	sort(v.begin(), v.end(), cmp);
	for (int i = 0; i < v.size(); i++)
	{
    
		while (v[i].second--)
			res += v[i].first;
	}
	return res;
}

bool isValidSudoku(vector<vector<char> > board)
{
    
	//规则1：数字 1-9 在每一行只能出现一次
	//规则2：数字 1-9 在每一列只能出现一次
    //规则3：数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次
	int rows[9][9];//rows[i][index]代表第i行中index出现的次数
	int columns[9][9];//columns[j][index]代表第j列中index出现的次数
	int subboxes[3][3][9];//subboxes[i][j][index]Represents the small nine-square gridindex出现的次数

	//初始化
	memset(rows, 0, sizeof(rows));
	memset(columns, 0, sizeof(columns));
	memset(subboxes, 0, sizeof(subboxes));

	//进行遍历,统计出现次数

	for (int i = 0; i < 9; i++)
	{
    
		for (int j = 0; j < 9; j++)
		{
    
			char ch = board[i][j];
			if (ch != '.')//处理数字
			{
    
				int index = ch - '0' - 1;//This is to prevent subscript overflow,将所有index减一
				rows[i][index]++;
				columns[j][index]++;
				subboxes[i/3][j/3][index]++;

				//Each time a number is processed, it is checked whether the number of occurrences of each number is otherwise the rule1-3
				if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1)
					return false;
			}

		}
	}

	return true;
}
int main()

{
    

	vector<vector<char> > board;

	char ch;

	for (int i = 0; i < 9; i++)

	{
    

		vector<char> aLine;

		for (int j = 0; j < 9; j++)

		{
    

			cin >> ch;

			aLine.push_back(ch);

		}

		board.push_back(aLine);

	}

	bool res = isValidSudoku(board);

	cout << (res ? "true" : "false") << endl;

	return 0;

}