n個皇后，不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法
我自己的拙見，確實是拙見，因為雖然內(nèi)存消耗比較小，但是耗時很長，在這個用空間換時間的時代里，那就是差的解法，但是畢竟完全是自己想的，寫的，哈哈，有感情
主要是考慮兩個點：
- 在nxn棋盤（數(shù)組[n][n]）中，共n個皇后，每個皇后的（i, j）都不相同，其實就是每一行都有個皇后，當(dāng)然它把他想象為每一列也行，比較轉(zhuǎn)一轉(zhuǎn)就行。那么我們只需要考慮 j 不相同即可
- 每個皇后的 j 不能是連續(xù)的，就像 2 ,4 ,0 ,3 ,1 就不可以，因為 2 和 0 是連續(xù)的，雖然有中間的 4，但是也不行，因為 2 1 0 , 已經(jīng)有連續(xù)，這種連續(xù)再加上 i 遞增，那么就會構(gòu)成對角線。
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> lists = new ArrayList<List<String>>();
for (int i = 0; i < n; i++){
int[] a = new int[n];
a[0] = i;
step(1, n , a, lists);
}
return lists;
}
static void step(int step, int n, int[] a, List<List<String>> lists){
if(step < n){
for(int j = 0; j < n; j++){
a[step] = j;
// 解決相鄰列和對角線，你當(dāng)然也可以下面的解決雙重for，好像是這個是多慮的
// 但是這個可以提前過濾掉一些大循環(huán)，減少很多的運算量
if(Math.abs(a[step-1] - a[step]) > 1){
// 解決所有點的列和對角線問題，這里的目的是為了不相鄰的列和對角線
boolean xie = true;
for(int w = 0; w < = step; w++){
int s = 1;
for (int z = w + 1; z < = step; z++){
if(Math.abs(a[w]-a[z]) == s++){
xie = false;
}
}
}
if(xie) {
step(step + 1, n, a, lists);
}
}
}
}
else{
Set set = new HashSet();
for(int x = 0; x < n; x++){
set.add(a[x]);
}
if(set.size() == n){
List<String> list = new ArrayList<String>();
for(int y = 0; y < n; y++){
StringBuilder s = new StringBuilder();
for(int k = 0; k < n; k++){
if(k == a[y]){
s.append("Q");
}else {
s.append(".");
}
}
list.add(s.toString());
}
lists.add(list);
}
}
}
}
解決思路：遞歸遍歷每個皇后的點，過濾掉已確定的皇后的 j 是否滿足不相同，不連續(xù)，即不同列和不在對角線，最后當(dāng)n個皇后都成功滿足條件，確定后，輸入保存。
2 ,4 ,0 ,3 ,1 怎么判斷是否有連續(xù)
1.上面所寫的雙for，s其實就是因為順序造成的差值，當(dāng)兩點的值差等于這個插值s，那么就是連續(xù)
boolean xie = true;
for(int w = 0; w < = step; w++){
int s = 1;
for (int z = w + 1; z < = step; z++){
if(Math.abs(a[w]-a[z]) == s++){
xie = false;
}
}
}
if(xie) {
}
2.補充每個點的因順序造成的差值，這樣連續(xù)的就會相等，再利用set去重性質(zhì)檢測
Set ascSet = new HashSet();
Set descSet = new HashSet();
for(int x = 0;x <= step; x++){
ascSet.add(a[x] + (step - x));
descSet.add(a[x] + (x - step));
}
if(ascSet.size() == step+1 && descSet.size() == step+1){
}
練習(xí)算法題，其實為了加深思考的深度與寬度，你的一切想法，就算是不正確，不夠優(yōu)秀，都是對你有益的，都是有利于下個問題的解決。所以不要 簡單想想，不會，就去看別人正確的思路和答案，由于你自己沒有太多思考，所以很容易跟著別人思路，只能模仿，不能遇變則變，思考的時候會考慮到很多其他問題，這些同樣也是很好的財富，再加上與他人思想的碰撞才能讓你更好的得到鍛煉。當(dāng)然這不是說沒有用，這個就像早上吃蘋果是金，中午是銀，晚上是銅，都是有益的。
