- 1 TOP101习题题解
- 1.1 有重复数字的全排列问题
- 1.2 有重复数字的子集问题
- 1.3 岛屿数量
- 1.4 括号问题
- 1.5 矩阵最长递增路径
- 2 经典问题求解
- 2.1 N皇后问题
- 总结
本文是【面试必刷101总结系列】之回溯算法第二篇文章，主要介绍牛客网面试必刷TOP101上我认为比较好的题目的题解，有助于理解回溯法框架和理解回溯法在实战中的应用。以下将分为 TOP101习题和经典问题求解两个模块分别介绍。 1 TOP101习题题解 1.1 有重复数字的全排列问题
没有重复数字的全排列、子集问题在第一篇博客中已经有非常详细的介绍了，加大点难度。有重复数字相当于解集是没有重复数字解空间的子集。因此需要特别注意重复导致的判重，可以通过set来做，也可以通过判定条件来限制。
有重复数字的全排列问题
import java.util.*;
public class Solution {
ArrayList> res = new ArrayList<>();
public ArrayList> permuteUnique(int[] num) {
Arrays.sort(num);
Boolean[] visit = new Boolean[num.length];
Arrays.fill(visit, false);
ArrayList tmp = new ArrayList<>();
recursion(num, tmp, visit);
return res;
}
public void recursion(int[] num, ArrayList tmp, Boolean[] visit) {
if (tmp.size() == num.length) {
res.add(new ArrayList(tmp));
return;
}
for (int i = 0; i < num.length; i++) {
if (visit[i]) {
continue;
}
// 上一个元素没被访问过就要跳出来，因为会出现重复的内容
if (i > 0 && num[i - 1] == num[i] && !visit[i - 1]) {
continue;
}
// 标记为使用过
visit[i] = true;
tmp.add(num[i]);
recursion(num, tmp, visit);
// 回溯
visit[i] = false;
tmp.remove(tmp.size() - 1);
}
}
}
就是通过添加判断条件来避免重复，但是整体框架还是回溯的框架。
1.2 有重复数字的子集问题NC221 集合的所有子集(二)
import java.util.*;
public class Solution {
ArrayList> res = new ArrayList<>();
public ArrayList> subsets (int[] nums) {
// write code here
Arrays.sort(nums);
dfs(nums, new ArrayList(), 0);
return res;
}
public void dfs(int []nums,ArrayList temp,int index){
// 当前加入结果集中
res.add(new ArrayList<>(temp));
for(int i=index;i
// 剪枝
if(i>index && nums[i] == nums[i-1])
continue;
temp.add(nums[i]);
dfs(nums,temp,i+1);
temp.remove(temp.size()-1);
}
}
}
1.3 岛屿数量
岛屿数量
题目很经典，需要注意的地方有：1、主函数的n*m的遍历；2、添加二维的数组判别哪些被访问了；3、返回值，因为一个入口进去可以扩展一片区域，因此返回1就好了，不符合条件的返回0就好了。（这里需要理解一下，其实入口进去之后，tag数组就记录了该入口能到达的所有地点，同一个岛屿不同的入口再次进入，返回值就是0了）
import java.util.*;
public class Solution {
int row;
int col;
public int solve (char[][] grid) {
row = grid.length;
col = grid[0].length;
boolean[][] tag = new boolean[row][col];
int res = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
res += findIland(grid, i, j, tag);
}
}
return res;
}
public int findIland(char[][] grid, int i, int j, boolean[][] tag) {
if (i < 0 || i >= row || j < 0 || j >= col) {
return 0;
}
if (grid[i][j] == '0' || tag[i][j]) {
return 0;
}
tag[i][j] = true;
findIland(grid, i + 1, j, tag);
findIland(grid, i, j + 1, tag);
findIland(grid, i - 1, j, tag);
findIland(grid, i, j - 1, tag);
return 1;
}
}
1.4 括号问题
括号生成
这题激动地我花了张图，虽然我的算法慢得很，但是我觉得这题的官方题解花里胡哨的，没我的好理解。
我的方法就是插入法，一次插入一个()。在哪插入呢？有空隙就插进去就完事了。会不会出现不合格的括号呢？不会，插入之前的已经是合格的，再插入一个合格的，还是合格的。问题在于会出现重复值，而且会出现大量重复计算，不管了，先写代码。
import java.util.*;
public class Solution {
ArrayList res = new ArrayList();
Set set = new HashSet();
public ArrayList generateParenthesis (int n) {
// 一对括号只能插入到左右两边或者已经有的一对括号内部
StringBuilder sb = new StringBuilder();
insert(n, sb);
for (String item : set) {
res.add(item);
}
return res;
}
public void insert(int n, StringBuilder sb) {
if (n <= 0) {
set.add(sb.toString());
return;
}
sb.insert(0, "()");
insert(n - 1, sb);
sb.delete(0, 2);
int size = sb.length();
for (int i = 1; i < size; i++) {
sb.insert(i, "()");
insert(n - 1, sb);
sb.delete(i, i + 2);
}
sb.append("()");
insert(n - 1, sb);
sb.delete(sb.length() - 2, sb.length());
}
}
很符合框架，但是有点慢。
1.5 矩阵最长递增路径矩阵最长递增路径
解法与上面那道岛屿数量题一样呀，但是这题可以用dp来优化，也很好理解，过去走过的路不用再走一遍。
import java.util.*;
public class Solution {
int max = 0;
public int solve (int[][] matrix) {
// write code here
int row = matrix.length;
int col = matrix[0].length;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
find(matrix, i, j, -1, 0);
}
}
return max;
}
public void find (int[][] matrix, int i, int j, int v, int cnt) {
if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length) {
return;
}
if (matrix[i][j] <= v) {
return;
}
cnt ++;
max = Math.max(max, cnt);
int tmp = matrix[i][j];
find(matrix, i + 1, j, tmp, cnt);
find(matrix, i - 1, j, tmp, cnt);
find(matrix, i, j + 1, tmp, cnt);
find(matrix, i, j - 1, tmp, cnt);
}
}
2 经典问题求解
2.1 N皇后问题
这是一种非递归实现的算法，其实还有递归版本，但是这种非递归的版本比较精妙。这个i值代表层数，第二个while循环内代表去找i行放置皇后的位置。精妙。
import java.util.*;
public class Solution {
int cnt = 0;
int[] q = new int[10]; // 用于记录i行的皇后放置的列数
public int Nqueen (int n) {
// write code here
int i = 1;
q[i] = 0;
while (i >= 1) {
q[i] ++;
while (q[i] <= n && !place(i)) {
q[i] ++;
}
if (q[i] <= n) {
if (i == n) {
cnt++;
} else {
i++;
q[i] = 0;
}
} else {
i--;
}
}
return cnt;
}
boolean place (int i) {
int j = 1;
if (i == 1) return true;
while (j < i) {
if (q[j] == q[i] || (Math.abs(q[i] - q[j]) == Math.abs(i - j))){
return false;
}
j++;
}
return true;
}
}
递归版下次再抽时间写写，
写博客挺累的。
