算法---暴力递归
0.暴力递归的概念
暴力递归就是尝试
- 把问题转化为规模缩小了的同类问题的子问题
- 有明确的不需要继续进行递归的条件(base case)
- 有当得到了子问题的结果之后的决策过程
- 不记录每一个子问题的解（记录就是动态规划）
1.汉诺塔问题
程序员面试金典 面试题 08.06. 汉诺塔问题(easy)
LeetCode
先放题解
题解
class Solution {
public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
func(A.size(),A,B,C);
}
public static void func(int N,List<Integer> from, List<Integer> other, List<Integer> to){
if(N == 1){
to.add(from.remove(from.size()-1));
return;
}else{
func(N-1,from,to,other);
to.add(from.remove(from.size()-1));
func(N-1,other,from,to);
}
}
}讲解
汉诺塔移动盘子有如下的限制：
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。
我们设有左中右三个柱子，有三个圆盘，当三个圆盘从小到大依次排列在右侧柱子时，游戏结束。
上面的暴力递归概念中说到，我们需要将大问题转化为小的问题，也就是将上面的1 2号圆盘设想为一个圆盘，
这样我们就可一将问题抽象为：
1、将融合圆盘(N-1)移动到中间
2、N号圆盘从左移动到右边
3、将融合圆盘(N-1)从中间移动到右边
融合的部分就是要进行递归的部分
有如下代码：
public static void hanoi1(int n) {
leftToRight(n);
}
public static void leftToRight(int n) {
if (n == 1) {
System.out.println("Move 1 from left to right");
return;
}
leftToMid(n - 1);
System.out.println("Move " + n + " from left to right");
midToRight(n - 1);
}
public static void leftToMid(int n) {
if (n == 1) {
System.out.println("Move 1 from left to mid");
return;
}
leftToRight(n - 1);
System.out.println("Move " + n + " from left to mid");
rightToMid(n - 1);
}
public static void rightToMid(int n) {
if (n == 1) {
System.out.println("Move 1 from right to mid");
return;
}
rightToLeft(n - 1);
System.out.println("Move " + n + " from right to mid");
leftToMid(n - 1);
}
public static void midToRight(int n) {
if (n == 1) {
System.out.println("Move 1 from mid to right");
return;
}
midToLeft(n - 1);
System.out.println("Move " + n + " from mid to right");
leftToRight(n - 1);
}
public static void midToLeft(int n) {
if (n == 1) {
System.out.println("Move 1 from mid to left");
return;
}
midToRight(n - 1);
System.out.println("Move " + n + " from mid to left");
rightToLeft(n - 1);
}
public static void rightToLeft(int n) {
if (n == 1) {
System.out.println("Move 1 from right to left");
return;
}
rightToMid(n - 1);
System.out.println("Move " + n + " from right to left");
midToLeft(n - 1);
}此时我们可以将这个模型抽象化：
无论是从左到右还是从右到左还是从左到中还是从中到左，总是有一个from，一个to，一个other
那么就有我们一开始的代码
public static void hanoi2(int n) {
if (n > 0) {
func(n, "left", "right", "mid");
}
}
// 1~i 圆盘 目标是from -> to， other是另外一个
public static void func(int N, String from, String to, String other) {
if (N == 1) { // base
System.out.println("Move 1 from " + from + " to " + to);
} else {
func(N - 1, from, other, to);
System.out.println("Move " + N + " from " + from + " to " + to);
func(N - 1, other, to, from);
}
}2.尝试
1.打印一个字符串的全部子序列
给定一个字符串“abc”,输出全部的子序列 如下： c b bc a ac ab abc
对给定的字符串的每一个字符，都有两种可能，“要”或“不要”
那么思路逐渐清晰，如图所示：
public static List<String> subs(String s) {
char[] str = s.toCharArray();
String path = "";
List<String> ans = new ArrayList<>();
process1(str, 0, ans, path);
return ans;
}
public static void process1(char[] str, int index, List<String> ans, String path) {
if (index == str.length) {
ans.add(path);
return;
}
String no = path;
process1(str, index + 1, ans, no);
String yes = path + String.valueOf(str[index]);
process1(str, index + 1, ans, yes);
}2.打印一个字符串的全部子序列，要求不要出现重复字面值的子序列
这个和上面的一样，存储容器使用set就好了，自动去重，挺方便的
public static List<String> subsNoRepeat(String s) {
char[] str = s.toCharArray();
String path = "";
HashSet<String> set = new HashSet<>();
process2(str, 0, set, path);
List<String> ans = new ArrayList<>();
for (String cur : set) {
ans.add(cur);
}
return ans;
}
public static void process2(char[] str, int index, HashSet<String> set, String path) {
if (index == str.length) {
set.add(path);
return;
}
String no = path;
process2(str, index + 1, set, no);
String yes = path + String.valueOf(str[index]);
process2(str, index + 1, set, yes);
}3.打印一个字符串的全部排列
这个有好几种做法：
1、交换递归
public static ArrayList<String> permutation(String str) {
ArrayList<String> res = new ArrayList<>();
if (str == null || str.length() == 0) {
return res;
}
char[] chs = str.toCharArray();
process(chs, 0, res);
return res;
}
public static void process(char[] str, int i, ArrayList<String> res) {
if (i == str.length) {
res.add(String.valueOf(str));
}
for (int j = i; j < str.length; j++) {
swap(str, i, j);
process(str, i + 1, res);
swap(str, i, j);
}
}2、标记法
List<Boolean> flag =null;
List<Integer> path =null;
public List<List<Integer>> permute(int[] num) {
flag = new ArrayList<>();
path = new ArrayList<>();
List<List<Integer>> ans = new ArrayList<>();
for(int i = 0;i<num.length;i++){
flag.add(false);
}
dfs(num,0,ans);
return ans;
}
public void dfs(int[] num,int u,List<List<Integer>> ans){
if(num.length == u){
List<Integer> pathList = new ArrayList<>(path.size());
pathList.addAll(path);
ans.add(pathList);
return;
}
for(int i=0;i<num.length;i++){
if(!flag.get(i)){
flag.set(i,true);
path.add(num[i]);
dfs(num,u+1,ans);
flag.set(i,false);
path.remove(path.size()-1);
}
}
}
4.打印一个字符串的全部排列，要求不要出现重复的排列
//分支限界
public static ArrayList<String> permutationNoRepeat(String str) {
ArrayList<String> res = new ArrayList<>();
if (str == null || str.length() == 0) {
return res;
}
char[] chs = str.toCharArray();
process2(chs, 0, res);
return res;
}
public static void process2(char[] str, int i, ArrayList<String> res) {
if (i == str.length) {
res.add(String.valueOf(str));
}
boolean[] visit = new boolean[26]; // 相当于一个HashMap，保存状态
for (int j = i; j < str.length; j++) {
if (!visit[str[j] - 'a']) {
visit[str[j] - 'a'] = true;
swap(str, i, j);
process2(str, i + 1, res);
swap(str, i, j);
}
}
}3.从左往右的尝试模型
1.把数字翻译成字符串
剑指 Offer 46
2.背包问题
4.从范围上尝试的模型
给定一个整型数组arr，代表数值不同的纸牌排成一条线， 玩家A和玩家B依次拿走每张纸牌， 规定玩家A先拿，玩家B后拿， 但是每个玩家每次只能拿走最左或最右的纸牌， 玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。
public static int win1(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
return Math.max(f(arr, 0, arr.length - 1), s(arr, 0, arr.length - 1));
}
public static int f(int[] arr, int i, int j) {
if (i == j) {
return arr[i];
}
return Math.max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1));
}
public static int s(int[] arr, int i, int j) {
if (i == j) {
return 0;
}
return Math.min(f(arr, i + 1, j), f(arr, i, j - 1));
}Java开发工程师面试必知必会 文章被收录于专栏
这里包含Java工程师面试的必会知识
