Joyce' Blog
0%

powx-n & n-queens

发表于 更新于

题目描述

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

题解

还是2的幂次比较好用。

1
2
3
4
5
6
7
8
9
10
double myPow(double x, int n) {
	if (x == 1)return 1;
	double res = 1;
	for (int i = n; i != 0; i /= 2)
	{
		if (i % 2)res *= x;
		x *= x;
	}
	return n < 0 ? 1 / res : res;
}

题目描述

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

题解

终究躲不过。

n=1时返回1，n皇后问题当n大于等于4才有讨论意义，而且不只有一个解决方案；递归回溯找到每一种解决方案；

行数要记得往下移，不要走回头路，不然会死循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
bool *heng, *shu, *pie, *na;
vector<string> model;

void dfs(vector<vector<string>>& res,int count,int n,int row)
{

	if(count==n){
		res.push_back(model);
		return;
	}
	for (int i = row; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (heng[i])
			{
				if (shu[j] && pie[i + j] && na[n - 1 - i + j])
				{
					model[i][j] = 'Q';
					heng[i] = false; shu[j] = false; pie[i + j] = false; na[n - 1 - i + j] = false;
					dfs(res, count + 1, n,i+1);
					model[i][j] = '.';
					heng[i] = true; shu[j] = true; pie[i + j] = true; na[n - 1 - i + j] = true;
				}
			}
			else
				break;
		}
	}
}
vector<vector<string>> solveNQueens(int n) {
	if (n == 1)return {{"Q"}};
	if (n < 4)return{};
	vector<vector<string>> res;

	string s = "";
	for (int i = 0; i < n; i++)
		s = s + '.';
	for (int i = 0; i < n; i++)
		model.push_back(s);
	heng = new bool[n];
	shu = new bool[n];
	int t = 2 * n - 1;
	pie = new bool[t];
	na = new bool[t];
	for (int i = 0; i < n; i++)
	{
		heng[i] = true; shu[i] = true;
	}
	for (int i = 0; i < t; i++)
	{
		pie[i] = true; na[i] = true;
	}
	dfs(res, 0, n, 0);
	return res;
}

执行用时 :108 ms, 在所有 C++ 提交中击败了6.45%的用户

内存消耗 :9.7 MB, 在所有 C++ 提交中击败了98.99%的用户

时间复杂度太差了，再剪剪枝。

本地没错，交到网上就报错：Heap-buffer-overflow。最后发现是斜线数量没注意。LeetCode对数组越界检查的比较严。

还是位运算效率最高。明天学吧。

题目描述

给定一个整数 n，返回 n 皇后不同的解决方案的数量。

题解

棋盘上棋子的位置信息用一个一维数组来表示就好了，下标表示行数，值表示列数。如果两个格子处在同一斜线上，他们的横纵坐标满足：abs(row1-row2)=abs(col1-col2)。

非递归方法的一个重要问题时何时回溯及如何回溯的问题。程序首先对N行中的每一行进行探测，寻找该行中可以放置皇后的位置，具体方法是对该行的每一列进行探测，看是否可以放置皇后，如果可以，则在该列放置一个皇后，然后继续探测下一行的皇后位置。如果已经探测完所有的列都没有找到可以放置皇后的列，此时就应该回溯，把上一行皇后的位置往后移一列，如果上一行皇后移动后也找不到位置，则继续回溯直至某一行找到皇后的位置或回溯到第一行，如果第一行皇后也无法找到可以放置皇后的位置，则说明已经找到所有的解程序终止。如果该行已经是最后一行，则探测完该行后，如果找到放置皇后的位置，则说明找到一个结果，打印出来。但是此时并不能再此处结束程序，因为我们要找的是所有N皇后问题所有的解，此时应该清除该行的皇后，从当前放置皇后列数的下一列继续探测。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
int totalNQueens(int n) {
	int* a;
	a = new int[n];
	for (int i = 0; i < n; i++)
		a[i] = -20;
	int res = 0;

	int i = 0, j = 0;
	while (i < n)
	{
		while (j < n)
		{
			bool valid = true;
			for (int k = 0; k < n; k++)
			{
				if (j == a[k] || abs(i - k) == abs(j - a[k]))
				{
					valid = false;
					break;
				}
			}

			if (valid)
			{
				a[i] = j;
				j = 0;
				break;
			}
			++j;
		}
		if (a[i] == -20)
		{
			if (i == 0)
				break;
			--i;
			j = a[i] + 1;
			a[i] = -20;
			continue;
		}
		if (i == n - 1)
		{
			res++;
			j = a[i] + 1;
			a[i] = -20;
			continue;

		}
		i++;
	}
	return res;
}

需要注意初始化a[i]的值时，a[i]的绝对值要比n大，否则在判断该位置是否有效的abs函数处会出现错误。

参考：https://blog.csdn.net/sinat_34166518/article/details/80096219