7、N皇后II

题目描述：

跟之前的那道题如出一辙，只是返回的不一样，这里就不说了，关键是那个position数组建立的要理解
代码：

class Solution {
    int result = 0;
  public int totalNQueens(int n) {
//		用以计算每行中皇后所在的位置
		int position[] = new int[n];
		gettotalNQueens(0,n,position);
		return result;
        
    }
	public void gettotalNQueens(int position,int n,int posi[]){
		if (position == n){
			result ++;
      
            return ;

		}
		for (int i = 0; i < posi.length; i++) {
			posi[position] = i;
			if(issuccess(posi, position)){
				gettotalNQueens(position + 1, n, posi);
			}
		}
		
	}
	public boolean issuccess(int position[],int row){
		for (int i = 0; i < row; i++) {
			if(position[i] == position[row] || Math.abs(row - i) == Math.abs(position[i] - position[row])){
				return false;
			}
		}
		return true;
	}
}

尝试利用位运算来进行，复杂度和空间都比较低，row表示行0-8，col表示的是该列可以放的棋子，其中0表示没有棋子，1表示可以放，pei表示的是k=1的情况，na表示的是k=-1的情况，代码如下：

	class Solution {
//	N皇后的位运算方法
	int resultbit = 0;
	public int get(int N){
		gets(0,N,0,0,0);
		return resultbit;
	}
	public void gets(int row,int N,int col,int pei,int na){
		if(row == N){
			resultbit ++;
			return ;
		}
//		看row行能放在哪几个位置
		int bit = (~(col | pei | na)) & ((1 << N) - 1);
//		对bit的那几个位置进行分别的放置
		
		while (bit != 0) {
//			取到最低位的1
			int p = bit & (-bit);
//			进行下一层的递归
			gets(row + 1, N, col | p, (pei | p) << 1, (na | p) >> 1);
//			更新bit将其最低位的1去掉
			bit = bit & (bit - 1);
		}
		
		
	}