leetcode高频题笔记之分治与回溯
Pow(x,n)（分治）
分治法
采用分治的思想，求x的n次方，可以先求x的n/2次方
如果n为偶数x^n = x^（n/2）* x^(n/2)
如果n为奇数x^n = x^（n/2）* x^(n/2) *x
public class Main {
public double myPow(double x, int n) {
if (x == 1) return 1;//特殊用例，加快速度
if (x == -1) return n % 2 == 0 ? 1 : -1;//特殊用例，加快速度
if (n == -2147483648) return 0;//一个特殊的坑人的用例
if (n < 0) {//负数次方处理
n = -n;
x = 1 / x;
}
return pow(x, n);
}
double pow(double x, int n) {
if (n == 0) return 1;
//求n/2次方的值
double half = myPow(x, n / 2);
return n % 2 == 0 ? half * half : half * half * x;
}
} 为运算表达式设计优先级（分治）
分治算法典型应用
分治法
class Solution {
public List<Integer> diffWaysToCompute(String input) {
List<Integer> ways = new ArrayList<>();
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
if (c == '+' || c == '-' || c == '*') {
List<Integer> left = diffWaysToCompute(input.substring(0, i));
List<Integer> right = diffWaysToCompute(input.substring(i + 1));
for (int l : left) {
for (int r : right) {
switch (c) {
case '+':
ways.add(l + r);
break;
case '-':
ways.add(l - r);
break;
case '*':
ways.add(l * r);
break;
}
}
}
}
}
//只有数字没有符号的情况
if (ways.size() == 0) {
ways.add(Integer.valueOf(input));
}
return ways;
}
} 子集（回溯）
回溯法
解法一：
每次遍历加一个大于原来数下标的数到集合，把集合加入到结果集
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
ans.add(new ArrayList<>());//初始化空数组
for(int i = 0;i<nums.length;i++){
List<List<Integer>> ans_tmp = new ArrayList<>();
//遍历之前的所有结果
for(List<Integer> list : ans){
List<Integer> tmp = new ArrayList<>(list);
tmp.add(nums[i]); //加入新增数字
ans_tmp.add(tmp);
}
ans.addAll(ans_tmp);
}
return ans;
} 解法二：
将添加值的问题分为加值和不加值两种
public class Main {
List<List<Integer>> res;
public List<List<Integer>> subsets(int[] nums) {
res = new ArrayList<>();
if (nums == null) return res;
dfs(nums, new ArrayList<Integer>(), 0);
return res;
}
/**
* @param nums 入参数组
* @param list 传入每层的数组
* @param level 层数
*/
private void dfs(int[] nums, List<Integer> list, int level) {
if (level == nums.length) {
res.add(new ArrayList<>(list));//因为list是传入的引用，所以需要new一个list加入
return;
}
//不需要这个参数的集合
dfs(nums, list, level + 1);
//将值加入列表，再进行下探
list.add(nums[level]);
dfs(nums, list, level + 1);
//reserve
list.remove(list.size() - 1);//真的list 引用，操作完了之后必须reserve
}
} 子集II（回溯）
思路：
- 数组排序
- 每次遍历加一个大于原来数下标的数到集合，把集合加入到结果集
- 如果两个数的值相同，第二次就不用加入遍历了，避免重复
public class Solution {
List<List<Integer>> res;
public List<List<Integer>> subsetsWithDup(int[] nums) {
res = new ArrayList<>();
if (nums == null) return res;
Arrays.sort(nums);
dfs(nums, new ArrayList<Integer>(), 0);
return res;
}
private void dfs(int[] nums, List<Integer> list, int start) {
res.add(new ArrayList<>(list));
for (int i = start;i<nums.length;i++){
//和上一个数字相同，跳过
if (i>start&&nums[i]==nums[i-1])continue;
list.add(nums[i]);
dfs(nums, list, i + 1);
//reserve
list.remove(list.size() - 1);
}
}
} 迭代法
这个题还有一个比较经典的玩法就是迭代法
遍历入参集合，每次都把已有的集合复制一份，然后把值加入到复制的集合中
public class Main {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null) return res;
res.add(new ArrayList<>());
for (int i = 0; i < nums.length; i++) {
List<List<Integer>> tmp_list = new ArrayList<>();//使用tmp_list，保证遍历时取的数都是上一轮的
for (List list : res) {
List<Integer> curlist = new ArrayList<>(list);
curlist.add(nums[i]);
tmp_list.add(curlist);
}
res.addAll(tmp_list);
}
return res;
}
} 电话号码的字母组合（回溯）
回溯法
public class Main {
Map<Character, String> map;
List<String> res;
public List<String> letterCombinations(String digits) {
if (digits.length() == 0 || digits == null) return new ArrayList<>();
//初始化
map = new HashMap<>();
map.put('2', "abc");
map.put('3', "def");
map.put('4', "ghi");
map.put('5', "jkl");
map.put('6', "mno");
map.put('7', "pqrs");
map.put('8', "tuv");
map.put('9', "wxyz");
res = new LinkedList<>();
search("", digits, 0);
return res;
}
private void search(String s, String digits, int level) {
//退出条件，长度够了
if (level == digits.length()) {
res.add(s);
return;
}
//获取第level个数字对应的字母
String cur = map.get(digits.charAt(level));
//遍历字母并依次下探
for (int i = 0; i < cur.length(); i++) {
search(s + cur.charAt(i), digits, level + 1);
}
}
} 单词搜索（回溯）
回溯法DFS解法
搜索到以word的第一个字母开头的位置，然后进行深度优先遍历
public class Solution {
int m;
int n;
public boolean exist(char[][] board, String word) {
if (word == null || word.length() == 0) return true;
if (board == null || board.length == 0 || board[0].length == 0) return false;
m = board.length;
n = board[0].length;
boolean[][] visited = new boolean[m][n];
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (board[r][c] == word.charAt(0) && dfs(0, r, c, visited, board, word))
return true;
return false;
}
private boolean dfs(int curlen, int r, int c, boolean[][] visited, char[][] board, String word) {
if (curlen == word.length()) return true;
if (r == -1 || c == -1 || r == m || c == n
|| board[r][c] != word.charAt(curlen) || visited[r][c])
return false;
visited[r][c] = true;
if (dfs(curlen + 1, r + 1, c, visited, board, word)) return true;
if (dfs(curlen + 1, r - 1, c, visited, board, word)) return true;
if (dfs(curlen + 1, r, c + 1, visited, board, word)) return true;
if (dfs(curlen + 1, r, c - 1, visited, board, word)) return true;
//reserve
visited[r][c] = false;
return false;
}
} 组合（回溯）
回溯法
public class Main {
List<List<Integer>> res;
public List<List<Integer>> combine(int n, int k) {
res = new ArrayList<>();
if (n <= 0 || k <= 0 || n < k) {
return res;
}
findCombinations(n, k, 1, new Stack<>());
return res;
}
private void findCombinations(int n, int k, int begin, Stack<Integer> pre) {
//当数目够了k就加入结果集并退出
if (pre.size() == k) {
res.add(new ArrayList<>(pre));
return;
}
//进一步下探，添加一个数，并下探它后面的数继续进行添加
for (int i = begin; i <= n; i++) {
pre.add(i);
findCombinations(n, k, i + 1, pre);
pre.pop();
}
}
} for 循环里 i 从 start 到 n，其实没必要到 n。比如，n = 5，k = 4，temp.size( ) == 1，此时代表我们还需要（4 - 1 = 3）个数字，如果 i = 4 的话，以后最多把 4 和 5 加入到 temp 中，而此时 temp.size() 才等于 1 + 2 = 3，不够 4 个，所以 i 没必要等于 4，i 循环到 3 就足够了。
所以，需要对下探条件进行修改，对整个递归树进行剪枝，减去图中绿色的数（图自题解）
推算出剪枝规则是i <= n - (k -temp.size()) + 1
于是优化后的代码如下
public class Main {
List<List<Integer>> res;
public List<List<Integer>> combine(int n, int k) {
res = new ArrayList<>();
if (n <= 0 || k <= 0 || n < k) {
return res;
}
findCombinations(n, k, 1, new Stack<>());
return res;
}
private void findCombinations(int n, int k, int begin, Stack<Integer> pre) {
//当数目够了k就加入结果集并退出
if (pre.size() == k) {
res.add(new ArrayList<>(pre));
return;
}
//进一步下探，添加一个数，并下探它后面的数继续进行添加
for (int i = begin; i <= n - (k - pre.size()) + 1; i++) {
pre.add(i);
findCombinations(n, k, i + 1, pre);
pre.pop();
}
}
} 组合总和（回溯）
public class Solution {
List<List<Integer>> res;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
res = new ArrayList<>();
backtrack(new ArrayList<>(), 0, target, candidates);
return res;
}
private void backtrack(List<Integer> tempCombination, int start, int target, int[] candidates) {
if (target == 0) {
res.add(new ArrayList<>(tempCombination));
return;
}
for (int i = start; i < candidates.length; i++) {
if (candidates[i] <= target) {
//当前层
tempCombination.add(candidates[i]);
//下探
backtrack(tempCombination, i, target - candidates[i], candidates);
//reserve
tempCombination.remove(tempCombination.size() - 1);
}
}
}
} 组合总和II（回溯）
与上一题相比，要做好防重复的准备
首先可以先到加一个标记位，然后每次检查下就好了，但是重复数字可能造成重复结果，且样例少不了变态的几十个重复的。
所以，先对入参进行排序，如果发现重复的，判断用不用得上，用不上就依次跳过
public class Solution {
List<List<Integer>> res;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
res = new ArrayList<>();
Arrays.sort(candidates);
boolean[] visited = new boolean[candidates.length];
backtrack(new ArrayList<>(), 0, target, candidates, visited);
return res;
}
private void backtrack(List<Integer> tempCombination, int start, int target, int[] candidates, boolean[] visited) {
if (target == 0) {
res.add(new ArrayList<>(tempCombination));
return;
}
for (int i = start; i < candidates.length; i++) {
//当前节点等于上一个节点，且上一个节点没有被访问过，直接跳过（如果上一个都没用上，当前这个就更没用了）
if (i != 0 && candidates[i] == candidates[i - 1] && !visited[i - 1]) continue;
if (candidates[i] <= target) {
//当前层
tempCombination.add(candidates[i]);
visited[i] = true;
//下探(因为不能重复，所以i要+1)
backtrack(tempCombination, i + 1, target - candidates[i], candidates, visited);
//reserve
visited[i] = false;
tempCombination.remove(tempCombination.size() - 1);
}
}
}
} 组合总和III（回溯）
class Solution {
List<List<Integer>> res;
public List<List<Integer>> combinationSum3(int k, int n) {
res = new ArrayList<>();
List<Integer> tmp = new ArrayList<>();
backtrack(k, n, tmp, 1);
return res;
}
private void backtrack(int k, int n, List<Integer> tmp, int start) {
//k，n都刚好终止则符合
if (k == 0 && n == 0) {
res.add(new ArrayList<>(tmp));
return;
}
//单个条件终止，说明这条路径不行
if (k == 0 || n == 0) return;
for (int i = start; i <= 9; i++) {
//当前层
tmp.add(i);
//下探
backtrack(k - 1, n - i, tmp, i + 1);
//reserve
tmp.remove(tmp.size() - 1);
}
}
} 全排列（回溯）
这个题组合一样，都是标准的回溯的模板解决
public class Main {
List<List<Integer>> res;
public List<List<Integer>> permute(int[] nums) {
res = new ArrayList<>();
backtrack(new ArrayList<>(), nums);
return res;
}
private void backtrack(List<Integer> tmpList, int[] nums) {
if (tmpList.size() == nums.length) {
res.add(new ArrayList<>(tmpList));//切记要新new一个加入
return;
}
for (int i = 0; i < nums.length; i++) {
if (tmpList.contains(nums[i])) continue;//已经存在了，就跳过
//当前层业务
tmpList.add(nums[i]);
//下探
backtrack(tmpList, nums);
//reserve
tmpList.remove(tmpList.size() - 1);
}
}
} 全排列II（回溯）
与上一个题全排列相比，本题存在两个新的问题
if(tempList.contains(nums[i])) continue;这句代码是通过比较值不同跳过的，而现在值可以相同- 如果有两个相同的值，则会产生两次一样的结果
针对上述两个问题，进行如下的升级
首先将nums进行排序，重新定义个一个old集合存放访问过的值的下标，使即使值相同也能判断是否访问过
针对重复现象，改为如下代码去重
//判断上一个元素和自己是不是一样的，一样说明上次就加进去了，不用重复操作了
// !old.contains(i - 1)是为了保证前一个数是因为回溯被还原了的才跳过，否则不能跳过
if (i > 0 && !old.contains(i - 1) && nums[i - 1] == nums[i]) {
continue;
} 视频讲解剪枝原理参考大佬的题解
public class Main {
List<List<Integer>> res;
public List<List<Integer>> permuteUnique(int[] nums) {
res = new ArrayList<>();
Arrays.sort(nums);
List<Integer> old = new ArrayList<>();
backtrack(new ArrayList<>(), nums, old);
return res;
}
private void backtrack(List<Integer> tmpList, int[] nums, List<Integer> old) {
if (tmpList.size() == nums.length) {
res.add(new ArrayList<>(tmpList));//切记要新new一个加入
return;
}
for (int i = 0; i < nums.length; i++) {
//当前下标的值已经被使用过了
if (old.contains(i)) {
continue;
}
//判断上一个元素和自己是不是一样的，一样说明上次就加进去了，不用重复操作了
// !old.contains(i - 1)是为了保证前一个数是因为回溯被还原了的才跳过，否则不能跳过
if (i > 0 && !old.contains(i - 1) && nums[i - 1] == nums[i]) {
continue;
}
//当前层业务
old.add(i);
tmpList.add(nums[i]);
//下探
backtrack(tmpList, nums, old);
//reserve
old.remove(old.size() - 1);
tmpList.remove(tmpList.size() - 1);
}
}
} N皇后（回溯）
超经典回溯题，思路见代码注解
public class Main {
List<List<String>> res;
//标记列是否被攻击
int[] rows;
//标记次对角线是否被攻击
int[] secondMain;
//标记主对角线是否被攻击
int[] main;
//存储皇后的位置
int[] queens;
//n皇后
int n;
public List<List<String>> solveNQueens(int n) {
//初始化
res = new ArrayList<>();
rows = new int[n];
secondMain = new int[2 * n - 1];
main = new int[2 * n - 1];
queens = new int[n];
this.n = n;
//回溯算法从第0行开始查找皇后的位置
backtrack(0);
return res;
}
//回溯算法放置皇后
private void backtrack(int row) {
if (row >= n) return;
//从第一列开始尝试放皇后
for (int col = 0; col < n; col++) {
//检测是否会被攻击，如果没有攻击再进行下一步操作
if (isNotUnderAttrack(row, col)) {
//在当前位置放置皇后
placeQueen(row, col);
// 放置完成判断现在是否是最后一行，如果是就存储这个方案
if (row == n - 1) addSolution();
//下探 在下一行放皇后
backtrack(row + 1);
//回溯，将上一个皇后去掉
removeQueen(row, col);
}
}
}
//回溯，去掉皇后和皇后的攻击范围
private void removeQueen(int row, int col) {
//移除row行的皇后
queens[row] = 0;
//更新列攻击范围
rows[col] = 0;
//更新主对角线攻击范围
main[row - col + n - 1] = 0;
//更新次对角线攻击范围
secondMain[row + col] = 0;
}
//将满足条件的皇后位置放入结果集
private void addSolution() {
List<String> solution = new ArrayList<>();
for (int i = 0; i < n; i++) {
//记录当前行皇后位置
int col = queens[i];
StringBuilder builder = new StringBuilder();
for (int j = 0; j < col; j++) builder.append(".");
builder.append("Q");
for (int j = 0;j<n-col-1;j++)builder.append(".");
solution.add(builder.toString());
}
res.add(solution);
}
//指定位置放置皇后
private void placeQueen(int row, int col) {
//存放皇后
queens[row] = col;
//更新列攻击范围
rows[col] = 1;
//更新主对角线攻击范围
main[row - col + n - 1] = 1;
//更新次对角线攻击范围
secondMain[row + col] = 1;
}
//检验位置是否会被攻击
private boolean isNotUnderAttrack(int row, int col) {
//对于列，直接判断列位置是否为0
//对于主对角线，row的值恒为col-n+1，所以将row - col + n - 1=0表示
//对于次对角线，row+col的值可以表示一条线
return rows[col] + main[row - col + n - 1] + secondMain[row + col] == 0;
}
} leetcode分类题集 文章被收录于专栏
按知识点分类整理leetcode的题目和解法
投递智联招聘等公司7个岗位 >