我的代码在单线程环境中进行迭代:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
class Solution {
int res = 0;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String line;
while ((line = in.readLine()) != null) {
int n = Integer.parseInt(line);
int ret = new Solution().totalNQueens(n);
String out = String.valueOf(ret);
System.out.print(out);
}
}
public int totalNQueens(int n) {
Set<Integer> columns = new HashSet<Integer>();
Set<Integer> record1 = new HashSet<Integer>();
Set<Integer> record2 = new HashSet<Integer>();
backTrace(n, 0, columns, record1, record2);
return res;
}
private int backTrace(int n, int row, Set<Integer> columns, Set<Integer> record1, Set<Integer> record2) {
if (n == row) {
return 1;
}
for (int i = 0; i < n; i++) {
if (columns.contains(i)) {
continue;
}
int check1 = row - i;
if (record1.contains(check1)) {
continue;
}
int check2 = row + i;
if (record2.contains(check2)) {
continue;
}
columns.add(i);
record1.add(check1);
record2.add(check2);
System.out.println("res start:" + res);
res = res + backTrace(n, row + 1, columns, record1, record2);
System.out.println("res end:" + res);
columns.remove(i);
record1.remove(check1);
record2.remove(check2);
}
return 0;
}
}
代码的结果如下,看起来
res
在res = res + backTrace(n, row + 1, columns, record1, record2);
时重置
res start:0
res start:0
res end:0
res start:0
res start:0
res end:0
res end:0
res end:0
res start:0
res start:0
res start:0
res start:0
res end:1
res end:0
res end:0
res end:0
res start:0
res start:0
res start:0
res start:0
当我们更改代码时,让一个新变量来保存 backTrace 的结果,它工作正常。
package com.nbp.cdncp.vpe.api.controller;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
class Solution {
int res = 0;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String line;
while ((line = in.readLine()) != null) {
int n = Integer.parseInt(line);
int ret = new Solution().totalNQueens(n);
String out = String.valueOf(ret);
System.out.print(out);
}
}
public int totalNQueens(int n) {
Set<Integer> columns = new HashSet<Integer>();
Set<Integer> record1 = new HashSet<Integer>();
Set<Integer> record2 = new HashSet<Integer>();
backTrace(n, 0, columns, record1, record2);
return res;
}
private int backTrace(int n, int row, Set<Integer> columns, Set<Integer> record1, Set<Integer> record2) {
if (n == row) {
return 1;
}
for (int i = 0; i < n; i++) {
if (columns.contains(i)) {
continue;
}
int check1 = row - i;
if (record1.contains(check1)) {
continue;
}
int check2 = row + i;
if (record2.contains(check2)) {
continue;
}
columns.add(i);
record1.add(check1);
record2.add(check2);
System.out.println("res start:" + res);
var a = backTrace(n, row + 1, columns, record1, record2);
res += a;
System.out.println("res end:" + res);
columns.remove(i);
record1.remove(check1);
record2.remove(check2);
}
return 0;
}
}
结果:
res start:0
res start:0
res end:0
res start:0
res start:0
res end:0
res end:0
res end:0
res start:0
res start:0
res start:0
res start:0
res end:1
res end:1
res end:1
res end:1
res start:1
res start:1
res start:1
res start:1
res end:2
res end:2
res end:2
res end:2
res start:2
res start:2
res start:2
res end:2
res end:2
res start:2
res end:2
res end:2
2
为什么在单线程环境下会出现这种情况
表达式
res + backTrace(n, row + 1, columns, record1, record2)
从左到右求值。这意味着 res
的值在 before 调用 backTrace
时被读取,并且不反映在该方法调用中发生的值的变化。
如果将
backTrace(n, row + 1, columns, record1, record2) + res
的参数顺序颠倒,这可以避免问题,但这仍然可能使代码难以理解。大多数人期望加法是可交换的。在其中一个操作数的评估会影响另一个操作数的值的代码中违反了此假设。重写方法避免使用非局部变量会更清楚res
:
class Solution {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String line;
while ((line = in.readLine()) != null) {
int n = Integer.parseInt(line);
int ret = new Solution().totalNQueens(n);
String out = String.valueOf(ret);
System.out.print(out);
}
}
public int totalNQueens(int n) {
Set<Integer> columns = new HashSet<Integer>();
Set<Integer> record1 = new HashSet<Integer>();
Set<Integer> record2 = new HashSet<Integer>();
return backTrace(n, 0, columns, record1, record2);
}
private int backTrace(int n, int row, Set<Integer> columns, Set<Integer> record1, Set<Integer> record2) {
if (n == row) {
return 1;
}
int res = 0;
for (int i = 0; i < n; i++) {
if (columns.contains(i)) {
continue;
}
int check1 = row - i;
if (record1.contains(check1)) {
continue;
}
int check2 = row + i;
if (record2.contains(check2)) {
continue;
}
columns.add(i);
record1.add(check1);
record2.add(check2);
System.out.println("res start:" + res);
res += backTrace(n, row + 1, columns, record1, record2);
System.out.println("res end:" + res);
columns.remove(i);
record1.remove(check1);
record2.remove(check2);
}
return res;
}
}