N-Queens II, Leetcode 解题笔记

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

看完题感觉解法是完全一样的,只是最后的返回值有所不同,于是直接写了下面的代码,结果跳进了这道题唯一的陷阱。
错误代码:

public class Solution {
    
    public int totalNQueens(int n) {
        int[] sol = new int[n];
        int count = 0;
        placeQ(sol, 0, n, count);
        return count;
    }
    public void placeQ(int[] sol, int cur, int n, int count){
        if(cur == n){
            count++;
        }
        else{
            for(int i = 0; i < n; i++){
                sol[cur] = i;
                if(check(sol, cur)){
                    placeQ(sol, cur+1, n, count);
                }
            }
        }
    }
    public boolean check(int[] sol, int cur){
        for(int i = 0; i < cur; i++){
            if(sol[cur] == sol[i] || Math.abs(sol[cur] - sol[i]) == cur - i){
                return false;
            }
        }
        return true;
    }
}

为什么结果不对呢?这是因为java中所有的传参都是按值传递,所以如果你直接传int count在里面改变count的值是不会影响count在外面的值的。怎么办呢?有两个方法,一个是定义count为一个全局变量,另一个是传递一个只有一个元素的数组,因为数组的传递是pass by reference的。
正确代码:

public class Solution {
    
    int count = 0;
    public int totalNQueens(int n) {
        int[] sol = new int[n];
        placeQ(sol, 0, n);
        return count;
    }
    public void placeQ(int[] sol, int cur, int n){
        if(cur == n){
            count++;
        }
        else{
            for(int i = 0; i < n; i++){
                sol[cur] = i;
                if(check(sol, cur)){
                    placeQ(sol, cur+1, n);
                }
            }
        }
    }
    public boolean check(int[] sol, int cur){
        for(int i = 0; i < cur; i++){
            if(sol[cur] == sol[i] || Math.abs(sol[cur] - sol[i]) == cur - i){
                return false;
            }
        }
        return true;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s