dfs+回溯写题两种思路
主要框架
public void dfs(选择列表){
//1.找到结束条件
//2.遍历所有可能性
//2.1做选择
//2.2 递归调用自己进一步深度遍历
//3.回撤选择
}
- dfs函数的参数变量我觉得是越少越好，所以将一些不怎么改变的变量设置为全局变量更容易理清思路
1.遍历的过程不停的往中间变量添加数据
剑指 Offer 38. 字符串的排列
static Set<String> res;
static char[] ch;
static boolean[] ch_helper;
public static String[] permutation(String s) {
res = new HashSet<>();
ch = s.toCharArray();
ch_helper = new boolean[ch.length];
dfs("");
return res.toArray(new String[res.size()]);
}
private static void dfs(String str) {
//1.结束条件
if(str.length() == ch.length){
res.add(str);
}
//2.遍历所有可能性
for(int i = 0; i < ch.length; i++){
if(ch_helper[i] != true){
ch_helper[i] = true;
dfs(str + ch[i]);
ch_helper[i] = false;
}
}
}
46. 全排列
static List<List<Integer>> res;
static LinkedList<Integer> tmp;
public static List<List<Integer>> permute(int[] nums) {
res = new LinkedList<>();
tmp = new LinkedList<>();
dfs(nums);
return res;
}
private static void dfs(int[] nums) {
if(tmp.size() == nums.length){
res.add(new ArrayList<>(tmp));
return;
}
for(int num : nums){
if(tmp.contains(num)){
continue;
}
tmp.add(num);
dfs(nums);
tmp.removeLast();
}
2. 遍历的过程改变原列表,这种一般会从下标0开始
剑指 Offer 38. 字符串的排列
static List<String> res;
static char[] ch;
public static String[] permutation(String s) {
res = new LinkedList<>();
ch = s.toCharArray();
dfs(0);
return res.toArray(new String[res.size()]);
}
private static void dfs(int i) {
//1.结束条件
if (i == ch.length - 1){
res.add(String.valueOf(ch));
return;
}
//2.选择列表
Set<Character> set = new HashSet<>();
for(int idx = i; idx < ch.length; idx++){
if(set.contains(ch[idx]))
continue;
set.add(ch[idx]);
//2.1选择
swap(ch, idx, i);
//2.2 进一步
dfs(i + 1);
//3.回溯
swap(ch, idx, i);
}
}
private static void swap(char[] ch, int idx, int i) {
char tmp = ch[idx];
ch[idx] = ch[i];
ch[i] = tmp;
}
46. 全排列
- 么有剪枝
static List<String> res;
static char[] ch;
public static String[] permutation(String s) {
res = new LinkedList<>();
ch = s.toCharArray();
dfs(0);
return res.toArray(new String[res.size()]);
}
private static void dfs(int i) {
//1.结束条件
if (i == ch.length - 1){
res.add(String.valueOf(ch));
return;
}
//2.选择列表
for(int idx = i; idx < ch.length; idx++){
set.add(ch[idx]);
//2.1选择
swap(ch, idx, i);
//2.2 进一步
dfs(i + 1);
//3.回溯
swap(ch, idx, i);
}
}
private static void swap(char[] ch, int idx, int i) {
char tmp = ch[idx];
ch[idx] = ch[i];
ch[i] = tmp;
}
- 带剪枝
static List<String> res;
static char[] ch;
public static String[] permutation(String s) {
res = new LinkedList<>();
ch = s.toCharArray();
dfs(0);
return res.toArray(new String[res.size()]);
}
private static void dfs(int i) {
//1.结束条件
if (i == ch.length - 1){
res.add(String.valueOf(ch));
return;
}
//2.选择列表
Set<Character> set = new HashSet<>();
for(int idx = i; idx < ch.length; idx++){
if(set.contains(ch[idx]))
continue;
set.add(ch[idx]);
//2.1选择
swap(ch, idx, i);
//2.2 进一步
dfs(i + 1);
//3.回溯
swap(ch, idx, i);
}
}
private static void swap(char[] ch, int idx, int i) {
char tmp = ch[idx];
ch[idx] = ch[i];
ch[i] = tmp;
}
2 dfs问题