Day30题目
写在前面
五一收假，并且这三道题都是选做，明天看一下吧。
LeetCode332.重新安排行程 ：todo
LeetCode51. N皇后
class Solution {
List<String> path = new ArrayList<>();
List<List<String>> res = new ArrayList<>();
int count = 0;
boolean[] column = new boolean[10];
public List<List<String>> solveNQueens(int n) {
help(n);
return res;
}
public void help(int n){
// count 是已经放置的皇后个数
if(count == n){
res.add(new ArrayList<>(path));
return;
}
for(int i = 0 ; i < n ; i ++){
if(valid(n,count,i)){
// 构建当前值
column[i] = true;
char[] temp = new char[n];
Arrays.fill(temp,'.');
temp[i] = 'Q';
path.add(new String(temp));
count++;
help(n);
count--;
// 使当前这一行不重复，行已经由count进行保证过了
column[i] = false;
path.removeLast();
}
}
}
// 在这里判断是否合法
public boolean valid(int n ,int x, int y){
if(column[y]) return false;
// x 是第几行
// 数学关系要推导一下
for(int i = 0 ; i < x; i ++){
if(y-(x-i) >= 0 && path.get(i).charAt(y-(x-i)) == 'Q') return false;
if(y+(x-i) < n && path.get(i).charAt(y+(x-i)) == 'Q') return false;
}
return true;
}
}