题目四：
N-Queens && N-Queens II
这两个题目是类似的：都是N皇后问题，我之前有一篇文章写的就是总结递归问题和分治思想的，那里面对N皇后问题进行了很详细的解说，所以这里就不重复了。 博文链接：本文专注于<递归算法和分治思想>[胖虎学习算法系列]http://blog.csdn.net/ljphhj/article/details/22799189我们来看下这两题的题目和AC代码：
题目1（N-queens）：
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+CkVhY2ggc29sdXRpb24gY29udGFpbnMgYSBkaXN0aW5jdCBib2FyZCBjb25maWd1cmF0aW9uIG9mIHRoZSBuLXF1ZWVucw==" placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:
[ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]
AC代码：
package copylist;
import java.util.ArrayList;
import java.util.Arrays;
/**
* 典型的N皇后问题
* @Description: [leetcode N-Queens]
* @Author: [胖虎]
* @CreateDate: [2014-4-3 下午8:19:44]
* @CsdnUrl: [http://blog.csdn.net/ljphhj]
*/
public class Solution {
private ArrayList
result = new ArrayList
(); private int[][] conflicts; private int[] queens; //int[row] = col private int count = 0; private int n; public ArrayList
solveNQueens(int n) { if(n == 0) return result; //init conflicts = new int[n][n]; queens = new int[n]; this.n = n; solve(0); return result; } public void solve(int row){ for (int col=0; col
= 0){ conflicts[i][(col - (i - row))]++; } //"/" if ((col + (i - row)) < n){ conflicts[i][(col + (i - row))]++; } } if (row == n-1){ String[] strings = new String[n]; for(int i=0; i
= 0){ conflicts[i][(col - (i - row))]--; } //"/" if ((col + (i - row)) < n){ conflicts[i][(col + (i - row))]--; } } } } } public static void main(String[] args) { Solution s = new Solution(); ArrayList
list = s.solveNQueens(8); int i=0; for (String[] string : list) { System.out.println("解法" + ++i + "："); for (String string2 : string) { System.out.println(string2); } } } }
题目2（N-queens II）：
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
就是题目1的答案哈，只不过它要返回的值是所有解的个数，我们都能得到所有解，还怕得不到个数么？
AC代码：
public class Solution {
private int[][] conflicts;
private int count = 0;
private int n;
public void solveNQueens(int n) {
if(n == 0)
return;
//init
conflicts = new int[n][n];
this.n = n;
solve(0);
}
public void solve(int row){
for (int col=0; col
= 0){
conflicts[i][(col - (i - row))]++;
}
//"/"
if ((col + (i - row)) < n){
conflicts[i][(col + (i - row))]++;
}
}
if (row == n-1){
count++;
}else{
solve(row+1);
}
//remove conflict
for (int i=row+1; i
= 0){ conflicts[i][(col - (i - row))]--; } //"/" if ((col + (i - row)) < n){ conflicts[i][(col + (i - row))]--; } } } } } public int totalNQueens(int n) { solveNQueens(n); return count; } }
题目五：
Pow(x, n)
题目：Implement pow(x, n).
分析：要我们实现一个pow这样的函数，哈哈，用JAVA用惯了，突然要你实现api里面的其中一个函数，是不是觉得很无语哈，不过这题明显是有陷阱的
如果你用for循环，去做n次 x 的乘法运算，那肯定是会超时的，那如何算会比较快呢
我们想到初高中的数学公式
1、X^n = (X^2) ^ (n/2) [当n是偶数的时候]
2、X^n = X * (X^2) ^ ((n-1)/2) [当n是奇数的时候]
这样子我们就可以把这个问题转换成 递归或者分治思想这样的题目啦!
很奇妙吧！看AC代码哈~~
package copylist;
/**
*
* @Description: [pow(x,n)的java实现代码]
* @Author: [胖虎]
* @CreateDate: [2014-4-3 下午10:24:57]
* @CsdnUrl: [http://blog.csdn.net/ljphhj]
*/
public class Solution {
public double pow(double x, int n) {
//如果n<0 那么结果是等于 x^n的倒数,即 1/x^n
//为了方便运算，我们先把n统一成正数
int y = n > 0 n : -n;
if (n == 0){
// x^0 = 1;
return 1;
}
if (n == 1){
// x^1 = x;
return x;
}
double result;
if (y % 2 == 0){
result = pow(x*x, y / 2);
}else{
result = pow(x*x, (y-1) / 2) * x;
}
return n > 0 result : 1.0 / result;
}
public static void main(String[] args) {
System.out.println(new Solution().pow(34.00515, -3));
}
}