第4周
Algorithm:
n 皇后问题研究的是如何将 n个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
解：
package algo.leetcode;
import java.util.List;
import java.util.ArrayList;
import java.lang.Math;
public class NQueens {
private int checkNum = 0;
public boolean isConflict(int[] qCol, int rowNum) {
if ( rowNum < 1) {
return false;
}
for (int i = 0; i < rowNum; ++i) {
for (int j = i + 1; j <= rowNum; ++j) {
++checkNum;
if (isTwoConflict(i, qCol[i], j, qCol[j])) {
return true;
}
}
}
return false;
}
public boolean isTwoConflict(int row1, int col1, int row2, int col2) {
if ((row1 == row2) || (col1 == col2) || (Math.abs(row2 - row1) == Math.abs(col2 - col1))) {
return true;
}
return false;
}
public void printRslt(int[] qCol) {
for (int i = 0; i < qCol.length; i++) {
System.out.println("第" + (i + 1) + "行皇后的列位置: " + qCol[i]);
}
}
public ArrayList<String> genChessBoardStr(int[] qCol) {
ArrayList<String> l = new ArrayList<String>();
int n = qCol.length;
for(int i=0; i<n; i++) {
String chessLineStr = "";
for(int j=0; j<n; j++) {
chessLineStr += (j == qCol[i])? 'Q' : '.';
}
l.add(chessLineStr);
}
return l;
}
public List<List<String>> solveNQueens(int n) {
int N = n;
List<List<String>> l = new ArrayList<List<String>>();
if (n <= 3 && n != 1)
return l;
if (n == 1) {
ArrayList<String> strList = new ArrayList<String>();
strList.add("Q");
l.add(strList);
return l;
}
// 每个皇后对应棋盘的一行，每个栈存储这一行的位置
int QCol[] = new int[N];
int solutionNum = 0;
int recycleNum = 0;
int i = 1; //从第2行开始检测冲突
boolean endFlag = false;
while (true) {
++recycleNum;
System.out.print("当前棋盘: ");
for(int x=0; x<=i; x++) {
System.out.print(QCol[x] + ", ");
}
System.out.print("尝试第" + (i+1) + "行, ");
if ( endFlag ) break;
if (isConflict(QCol, i)) {
System.out.println("冲突");
if (QCol[i] == N-1 ) {
System.out.println("第" + (i+1) + "行为空");
while( i>0 ) {
for(int j=i; j<N; j++) {
QCol[j] = 0;
}
--i; // 回溯
if ( QCol[i] < N-1 ) {
QCol[i]++;
break;
} else {
if ( i== 0 ) {
if ( QCol[i] < N-1 ) {
QCol[i]++;
break;
} else {
System.out.println("第一行为空，结束");
endFlag = true;
break; //结束
}
}
}
} // end of while()
} else {
QCol[i]++;
System.out.println("第" + (i+1) + "行尝试：" + QCol[i]);
}
} else {
System.out.println("不冲突");
if (i < N - 1) {
++i;
System.out.println("尝试行数：" + (i+1) );
} else {
// 找到一个正确组合，输出
++solutionNum;
System.out.println("*****************");
System.out.println("找到第"+solutionNum+"个解:");
printRslt(QCol);
l.add(genChessBoardStr(QCol));
if ( QCol[i] < N-1 ) {
QCol[i]++;
} else {
QCol[i] = 0;
--i;
QCol[i]++;;
}
}
}
}
System.out.println("一共"+recycleNum+"次循环,"+checkNum+"次检查");
System.out.println("一共找到"+solutionNum+"个解。");
return l;
}
public void printChessBoard(List<List<String>> l) {
for(int i=0; i<l.size(); ++i) {
System.out.println();
System.out.println("Solution No." + (i+1) +":");
for(int j=0; j<l.get(i).size(); ++j) {
System.out.println(l.get(i).get(j));
}
}
}
public static void main(String[] args) {
int N;
if (args.length < 1) {
N = 8;
} else {
N = Integer.parseInt(args[0]);
}
System.out.println("N= " + N);
List<List<String>> l = new NQueens().solveNQueens(N);
new NQueens().printChessBoard(l);
}
}
用“回溯”法来做。提交的时候，要把打印语句删除，提高一些性能。留着是为了容易看懂程序。
后续：这个算法的复杂度应该是接近全排列了，O(n^n)。n=8时，要判断1600多万次。提交后显示性能也是比较靠后的，后续考虑实现一下优化算法。这次主要是实现了回溯算法。
Review:
Erlang语言的作者鄙视面向对象设计思想和语言的文章。虽然是大牛的文章，也得用批判的眼光来看。其实我不太同意此文的观点，但是既然是大牛的观点，不得不重视、学习。OO在操作系统、编译器等底层应用中可能确实开销太大、用处不大，但对于大量具有复杂业务逻辑的应用系统来说，面向对象的抽象、封装、继承等思想对于构建应用还是很有效和高效的，虽然它有时也有叠床架屋、晦涩难懂的缺点——特别是对初学者来说。不然，开源社区那么多运用面向对象思想和语言开发的精良的软件是怎么来的呢？
Tips:
工作中碰到Ajax跨域问题，以下文章可参考：
https://www.jianshu.com/p/7662b04ce42d
https://www.cnblogs.com/laixiangran/p/9064769.html#top
http://www.ruanyifeng.com/blog/2016/04/same-origin-policy.html
http://www.ruanyifeng.com/blog/2016/04/cors.html
Share:
耗子哥的绩效观，相当认同。
网友评论