LeetCode-N-Queens II

N-Queens II

##题目

####N-Queens II

Follow up for N-Queens problem.

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

##解题思路
该题和N-Queens基本相同，只是最后返回的是解得个数。但是这里需要注意的是:用java写的时候，基本数据类型是值传递，因此不能用int来作为递归的结果参数。

##算法代码
代码采用JAVA实现：

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
public class Solution {
    public int totalNQueens(int n) {
        ArrayList<Integer> res = new ArrayList<Integer>(); //这里不能用int类型
        res.add(0);
        helper(n,0,new int[n],res);
        return res.get(0);
    }
    //columnForRow 记录每一行中皇后的位置
    void helper(int n,int row,int[] columnForRow, ArrayList<Integer> res) 
    {	
    	if(row==n)
    	{
    		int num=res.get(0)+1;
    		res.set(0,num);
    		return;
    	}else{
    		for(int i=0;i<n;i++)
    		{
    			columnForRow[row]=i;
    			if(check(row,columnForRow))
		        {
		            helper(n,row+1,columnForRow,res);
		        }
    		}
    	}
    }

    boolean check(int row,int[] columnForRow)
    {
    	for(int i=0;i<row;i++)
    	{
    		if(columnForRow[row]==columnForRow[i] || Math.abs(columnForRow[row]-columnForRow[i])==(row-i))
    			return false;
    	}
    	return true;
    }
}

Comments

▲