p52

发表于 | 分类于 |

LeetCode 52 N-Queens II 题解

1.题目：

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.

题意：

N-Queens问题，输出总数。

2.解题思路:

与51题一样【捂脸】。

3.代码

[title] [] [url] [link text]
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
57
58
59
60
61
62
63
64
65
 

public class Solution {
    	

	public int totalNQueens(int n) {
		List<List<String>> ansArrayList = new ArrayList<List<String>>();

		if (n == 0)
			return 0;
		List<String> ways = new ArrayList<String>();
		StringBuilder s = new StringBuilder();
		for (int i = 0; i < n; i++) {
			s.append('.');
		}
		for (int i = 0; i < n; i++) {
			ways.add(s.toString());
		}

		dfs(n, ansArrayList, ways, 0);
		return ansArrayList.size();
	}

	public void dfs(int n, List<List<String>> ansArrayList,
			List<String> ways, int row) {
		// if (row>0) System.out.println(ways.get(row-1));

		if (row == n) {
			List<String> aList = new ArrayList<String>();
			for (int i = 0; i < ways.size(); i++) {
				// System.out.println(ways.get(i));
				aList.add(ways.get(i));
			}

			ansArrayList.add(aList);

			return;
		}

		for (int j = 0; j < n; j++) {
			if (check(n, ways, row, j)) {
				StringBuilder s = new StringBuilder(ways.get(row));
				s.setCharAt(j, 'Q');
				ways.set(row, s.toString());
				dfs(n, ansArrayList, ways, row + 1);
				s.setCharAt(j, '.');
				ways.set(row, s.toString());
			}
		}
	}

	public boolean check(int n, List<String> ways, int r, int l) {
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < n; j++) {
				if (ways.get(i).charAt(j) == 'Q'
						&& (j == l || Math.abs(r - i) == Math.abs(l - j))) {
					return false;
				}
			}
		}
		return true;

	}
}

4.一些总结：