Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
A:
仅仅地把问题一,改改,拿过来,(用DFS )来做,会太慢。
下面的代码,不是自己写的,是网上copy别人的。
第一次, 让爷们儿,放弃了自己的方式。
好好学着下面的代码!!!!!!!!!!!!!!!!!!
public class Solution { public int totalNQueens(int n) { assert(n>0); return countSolution(1,new int[n]); } public int countSolution(int k, int[] pattern){ int n= pattern.length; assert(k<=n); int res = 0; main: for(int i=0;i<n;i++){ for(int j=0;j<k-1;j++){ if(pattern[j]==i||Math.abs(j-k+1)==Math.abs(pattern[j]-i)) continue main; } pattern[k-1]=i; if(k==n) return 1; else res+=countSolution(k+1,pattern); } return res; } }
上面这个例子, 包括下面的例子,都默认要求 n < 32
-------------------------方法2------------
public class Solution { static int result = 0; static int upperLimit = 0; public int totalNQueens(int n) { upperLimit = (1 << n)-1; result = 0; int row = 0; int ld = 0; int rd = 0; dfs(row,ld,rd); return result; } private static void dfs(int row, int ld, int rd) { if(row >= upperLimit){ result++; return; } int pos = upperLimit &(~(row|ld|rd)); int p = 0; while(pos > 0){ p = pos & (~pos+1); pos = pos-p; dfs(row+p,(ld+p)<<1,(rd+p)>>1); } } }
Mistakes:
背诵上面的代码吧。 人家还用了个main:
Learned:
首先是label的运用。可以直接跳出2层循环。
当然,不建议这样用,可以设置个标识,如果内层跳出了, 再跳第二层。
----------------------------3 rd Pass --------------------------
由于2D array 的值只有2个, 因此,我们可以用1D array 来表示它。
比如: int[ ] {3,1,4,2} 代表放置的地点分别为[1,3], [2,1], [3,4], [2,4] ( 第一个是index)
这么一来,我们用很简单的用数组表示了整个Board,而且在isValid函数里判断的时候会非常简洁,而且把输出Board单独隔离了出来
注意,我们刚开始的时候,在isValid中,依然去判断行,列, 对角线。 其实是不必要的。 只需要判断当前行之前的行,列即可。
因此,刚开始的时候,我们写成:
private boolean isValid(int cur) {
// no need to check col, check row
for (int i = 0; i < cur; i++)
if ( loc[i] == loc[cur])
return false;
// check diagonal \
for (int i = 0; i < cur; i++) {
int j = i + loc[cur] - cur; // new colum that is on diagonal
if ( j >= 0 && j < N && loc[j] != loc[cur])
return false;
}
// check diagonal /
for (int i = 0; i < cur; i++) {
int j = loc[cur] + cur - i;// new colum that is on diagonal /
if ( j >= 0 && j < N && loc[j] != loc[cur])
return false;
}
return true;
}
这样其实是不必要的, 只需要判断 x上的距离差和y轴上的距离差,绝对值相等即可。
public class Solution { int total = 0; public int totalNQueens(int n) { int[] loc = new int[n]; dfs(loc,0); return total; } private void dfs(int[] loc,int row) { if (row >= loc.length) { total++; return; } for (int i = 0; i < loc.length; i++) { loc[row] = i+1;// loc[i]==j, means that on board[i][j] =='Q' if (isValid( loc,row)) dfs(loc,row + 1); } } private boolean isValid(int[] loc,int cur) { for (int i = 0; i < cur; i++) if (loc[i] == loc[cur] || Math.abs(loc[i] - loc[cur]) == (cur - i)) return false; return true; } }
Learned:
1:
用1D 来代替2D array-------- 其实,退化来讲, 如果是一维的棋盘,上面只能有一个位置放Q的话。
我们也可以直接 用一个 变量 来记录其位置即可。
2:
对2D 的数组来讲, 要判断是其diagonal的值相等。只需要判断其 x 轴的差距, 是否和 y轴的差距相等即可。 (由于是2条对角线, 因此,要去 Abs)
No comments:
Post a Comment