sudoku-solver

题目描述

解数独。可以假设给定的数独只有唯一解。

题解

得用递归回溯了。递归之前可以先把那些只有一种可能的空填上，减少递归的次数。

set<char> line[9], column[9], area[9];
bool dfs(vector<vector<char>>& board)
{
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			if (board[i][j] == '.')
			{
				set<char> t,c;
				set_intersection(line[i].begin(), line[i].end(), column[j].begin(), column[j].end(), inserter(t, t.begin()));//交集
				set_intersection(t.begin(), t.end(), area[(i / 3) * 3 + j / 3].begin(), area[(i / 3) * 3 + j / 3].end(), inserter(c, c.begin()));
				auto it = c.begin();
				while (it != c.end())
				{
					board[i][j] = *it;
					line[i].erase(*it);
					column[j].erase(*it);
					area[(i / 3) * 3 + j / 3].erase(*it);
					if (dfs(board))
						return true;
					board[i][j] = '.';
					line[i].insert(*it);
					column[j].insert(*it);
					area[(i / 3) * 3 + j / 3].insert(*it);
					it++;
				}
				return false;
			}
		}
	}
	return true;
}
void solveSudoku(vector<vector<char>>& board) {
	//初始化剩余可用数字
	set<char> k= { '1','2','3','4','5','6','7','8','9' };
	for (int i = 0; i < 9; i++)
	{
		line[i] = k;
		column[i] = k;
		area[i] = k;
	}
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			char t1 = board[i][j];
			if (t1!='.')
			{
				line[i].erase(t1);
				column[j].erase(t1);
				area[(i / 3) * 3 + j / 3].erase(t1);
			}
		}
	}
	
	//处理唯一数字的情况
	bool changed = true;
	while (changed)
	{
		changed = false;
		for (int i = 0; i < 9; i++)
		{
			for (int j = 0; j < 9; j++)
			{
				if (board[i][j] == '.')
				{
					set<char> t,c;
					//将两个set<int>合并成一个set<int>且去重
					set_intersection(line[i].begin(), line[i].end(), column[j].begin(), column[j].end(), inserter(t, t.begin()));//交集
					set_intersection(t.begin(), t.end(), area[(i / 3) * 3 + j / 3].begin(), area[(i / 3) * 3 + j / 3].end(), inserter(c, c.begin()));
					if (c.size() == 1)
					{
						changed = true;
						char k = *c.begin();
						board[i][j] = k;
						line[i].erase(k);
						column[j].erase(k);
						area[(i / 3) * 3 + j / 3].erase(k);
					}
				}
			}
		}
	}
	
	//递归，深度优先搜索
	dfs(board);
}

set_intersection这个函数不太了解，在上面踩了两次坑。

char和int的运算时间也没什么差别，全局变量和局部变量的运行时间也没什么差别，那这程序我还真不知道怎么优化了。

但是不预处理一种可能的空，确实会慢很多。

或许用位运算会快一些，胜过用set数据结构的求交运算。

问题描述

输出外观数列的第 n 项

题解

妥妥的递归

string countAndSay(int n) {
	if (n == 1)return "1";
	string s = countAndSay(n - 1);
	int i = 0;
	string res = ""; 
	int k = s.length();
	while (i < k)
	{
		char c = s[i];
		int count = 1;
		while (i< k-1)
		{
			if (c == s[i + 1])
			{
				i++;
				count++;
			}
			else
				break;
		}
		res =res+ to_string(count) + c;
		i++;
	}
	return res;
}