Day24 回溯算法

LeetCode77.组合：给出1-n之间每k个数的所有组合

核心思想：回溯，维护一个当前的元素集。注意结束条件

java">class Solution {// path存放当前元素List<Integer> path = new ArrayList<>();// 结果集resList<List<Integer> > res = new ArrayList<>(); public List<List<Integer>> combine(int n, int k) {// 回溯help(1,n,k);return res;}public void help(int start,int n ,int k ){// 如果从start开始到末尾的元素不足k个，则直接返回if(n-start +1< k)  return;if(k == 1){// k记录还 需要几个数字，如果只需要一个for(int i = start ; i <= n ; i ++){// 构建结果集path.add(i);res.add(new ArrayList(path));// 每一个结果都要回溯path.removeLast();}}else{// 否则就继续执行递归for(int i = start; i <= n ; i ++){path.add(i);help(i+1,n,k-1);//回溯path.removeLast();}}}}

LeetCode 51：N皇后问题，额外做的

核心思想：判断斜线是否存在皇后，这点需要画图想想关系。可以使用Boolean数组存储，也可使用for遍历已有元素查询斜线是否满足。Boolean数组我尝试失败了，目前使用for进行了遍历获取。

java">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;// 构建 . . . Q 的形式char[] temp = new char[n];Arrays.fill(temp,'.');temp[i] = 'Q';// 加入pathpath.add(new String(temp));// 当前行数++count++;// 进行下一行的遍历help(n);// 下面都是回溯部分count--;column[i] = false;path.removeLast(); }}}public boolean valid(int n ,int x, int y){// 在这里判断当前这个点的 列、斜线 是否有元素// 行不用判断，因为我每一行固定只放一个元素，count作为行的索引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;}
}