8000 refactor 51 · ashish53v/Leetcode@b2dc7f3 · GitHub
[go: up one dir, main page]
Skip to content

Commit b2dc7f3

Browse files
fishercoder1534fishercoder1534
committed
refactor 51
1 parent 0e23581 commit b2dc7f3

File tree

3 files changed

+73
-85
lines changed

3 files changed

+73
-85
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -623,7 +623,7 @@ Your ideas/fixes/algorithms are more than welcome!
623623
|54|[Spiral Matrix](https://leetcode.com/problems/spiral-matrix/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_54.java)|O(m*n)|O(m*n)||Medium| Array
624624
|53|[Maximum Subarray](https://leetcode.com/problems/maximum-subarray/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_53.java)|O(n)|O(1)||Easy|
625625
|52|[N-Queens II](https://leetcode.com/problems/n-queens-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_52.java)|O(?)|O(?)||Hard|
626-
|51|[N-Queens](https://leetcode.com/problems/n-queens/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_51.java)|O(?)|O(?)||Hard|
626+
|51|[N-Queens](https://leetcode.com/problems/n-queens/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_51.java)|O(n!)|O(n)||Hard|
627627
|50|[Pow(x, n)](https://leetcode.com/problems/powx-n/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_50.java)|O(logn)|O(logn)||Medium|
628628
|49|[Group Anagrams](https://leetcode.com/problems/group-anagrams/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_49.java)|O(m*klogk)|O(m*k)||Medium| HashMap
629629
|48|[Rotate Image](https://leetcode.com/problems/rotate-image/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_48.java)|O(n^2)|O(1)| |Medium | Array

‎src/main/java/com/fishercoder/solutions/_51.java

Lines changed: 47 additions & 58 deletions
Original file line numberDiff line numberDiff line change
@@ -4,12 +4,11 @@
44
import java.util.List;
55

66
/**
7+
* 51. N-Queens
8+
*
79
* The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
810
9-
10-
1111
Given an integer n, return all distinct solutions to the n-queens puzzle.
12-
1312
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
1413
1514
For example,
@@ -29,76 +28,66 @@
2928
*/
3029
public class _51 {
3130

31+
public static class Solution1 {
32+
3233
public List<List<String>> solveNQueens(int n) {
33-
List<List<String>> result = new ArrayList<>();
34-
if (n <= 0) {
35-
return result;
36-
}
37-
search(n, new ArrayList<>(), result);
34+
List<List<String>> result = new ArrayList<>();
35+
if (n <= 0) {
3836
return result;
37+
}
38+
search(n, new ArrayList<>(), result);
39+
return result;
3940
}
4041

4142
private void search(int n, ArrayList<Integer> col, List<List<String>> result) {
42-
if (col.size() == n) {
43-
result.add(drawChessBoard(col));
44-
return;
45-
}
46-
47-
for (int i = 0; i < n; i++) {
48-
if (!isValid(col, i)) {
49-
continue;
50-
}
51-
col.add(i);
52-
search(n, col, result);
53-
col.remove(col.size() - 1< 8000 /span>);
43+
if (col.size() == n) {
44+
result.add(drawChessBoard(col));
45+
return;
46+
}
47+
48+
for (int i = 0; i < n; i++) {
49+
if (!isValid(col, i)) {
50+
continue;
5451
}
52+
col.add(i);
53+
search(n, col, result);
54+
col.remove(col.size() - 1);
55+
}
5556
}
5657

5758
private boolean isValid(ArrayList<Integer> col, int next) {
58-
int row = col.size();
59-
for (int i = 0; i < row; i++) {
60-
if (next == col.get(i)) {
61-
return false;
62-
}
63-
64-
if (i - row == col.get(i) - next) {
65-
return false;
66-
}
67-
68-
if (i - row == next - col.get(i)) {
69-
return false;
70-
}
59+
int row = col.size();
60+
for (int i = 0; i < row; i++) {
61+
if (next == col.get(i)) {
62+
return false;
7163
}
72-
return true;
73-
}
7464

75-
private ArrayList<String> drawChessBoard(ArrayList<Integer> col) {
76-
ArrayList<String> chessBoard = new ArrayList<>();
65+
if (i - row == col.get(i) - next) {
66+
return false;
67+
}
7768

78-
for (int i = 0; i < col.size(); i++) {
79-
String row = "";
80-
for (int j = 0; j < col.size(); j++) {
81-
if (col.get(j) == i) {
82-
row += "Q";
83-
} else {
84-
row += ".";
85-
}
86-
}
87-
chessBoard.add(row);
69+
if (i - row == next - col.get(i)) {
70+
return false;
8871
}
89-
return chessBoard;
72+
}
73+
return true;
9074
}
9175

92-
public static void main(String...args) {
93-
_51 test = new _51();
94-
95-
ArrayList<Integer> col = new ArrayList<>();
96-
col.add(0);//false, false, true, true,
97-
// col.add(1);//false, false, false, true,
98-
// col.add(2);//true, false, false, false,
99-
// col.add(3);//true, true, false, false,
100-
for (int x = 0; x < 4; x++) {
101-
System.out.print(test.isValid(col, x) + ", ");
76+
private ArrayList<String> drawChessBoard(ArrayList<Integer> col) {
77+
ArrayList<String> chessBoard = new ArrayList<>();
78+
79+
for (int i = 0; i < col.size(); i++) {
80+
String row = "";
81+
for (int j = 0; j < col.size(); j++) {
82+
if (col.get(j) == i) {
83+
row += "Q";
84+
} else {
85+
row += ".";
86+
}
10287
}
88+
chessBoard.add(row);
89+
}
90+
return chessBoard;
10391
}
92+
}
10493
}

‎src/test/java/com/fishercoder/_51Test.java

Lines changed: 25 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -12,30 +12,29 @@
1212
import static junit.framework.Assert.assertEquals;
1313

1414
public class _51Test {
15-
private static _51 test;
16-
private static List<List<String>> expected;
17-
private static List<List<String>> actual;
18-
private static int n;
19-
20-
@BeforeClass
21-
public static void setup() {
22-
test = new _51();
23-
}
24-
25-
@Before
26-
public void setupForEachTest() {
27-
expected = new ArrayList<>();
28-
actual = new ArrayList<>();
29-
}
30-
31-
@Test
32-
public void test1() {
33-
n = 4;
34-
expected = new ArrayList<>();
35-
expected.add(Arrays.asList("..Q.", "Q...", "...Q", ".Q.."));
36-
expected.add(Arrays.asList(".Q..", "...Q", "Q...", "..Q."));
37-
actual = test.solveNQueens(n);
38-
assertEquals(expected, actual);
39-
40-
}
15+
private static _51.Solution1 solution1;
16+
private static List<List<String>> expected;
17+
private static List<List<String>> actual;
18+
private static int n;
19+
20+
@BeforeClass
21+
public static void setup() {
22+
solution1 = new _51.Solution1();
23+
}
24+
25+
@Before
26+
public void setupForEachTest() {
27+
expected = new ArrayList<>();
28+
actual = new ArrayList<>();
29+
}
30+
31+
@Test
32+
public void test1() {
33+
n = 4;
34+
expected = new ArrayList<>();
35+
expected.add(Arrays.asList("..Q.", "Q...", "...Q", ".Q.."));
36+
expected.add(Arrays.asList(".Q..", "...Q", "Q...", "..Q."));
37+
actual = solution1.solveNQueens(n);
38+
assertEquals(expected, actual);
39+
}
4140
}

0 commit comments

Comments
 (0)
0