- 暴力递归
- 汉诺塔问题
- 例二--打印一个字符串的全部子序列
- 例三--打印一个字符串的全部排列
- 例四
- 逆序栈
- 例六
- 例七
- 总结
暴力递归
暴力递归就是尝试
1，把问题转化为规模缩小了的同类问题的子问题
2，有明确的不需要继续进行递归的条件(base case)
3，有当得到了子问题的结果之后的决策过程，
4，不记录每一个子问题的解
打印n层汉诺塔从最左边移动到最右边的全部过程
public class hanoi {
public static void main(String[] args) {
int n =3;
hanoi(n);
}
public static void hanoi(int n){
if (n > 0){
func(n,"左","中","右");
}
}
public static void func(int i, String start, String end, String other){
if (i == 1){
System.out.println("move 1 from" + start + "to" + end);
}else {
func(i-1,start,other,end);
System.out.println("move " + i + " from" + start + "to" + end);
func(i-1,other,end,start);
}
}
}
例二–打印一个字符串的全部子序列
打印一个字符串的全部子序列，包括空字符串
public class PrintAllSubsquences {
public static void main(String[] args) {
String str = "abc";
fun(str);
PrintAllSubsquences(str);
}
public static void PrintAllSubsquences(String str){
char[] chs = str.toCharArray();
process(chs,0);
}
private static void process(char[] chs, int i) {
if (i == chs.length){
System.out.println(String.valueOf(chs));
return;
}
process(chs,i+1);//要当前字符
char temp = chs[i];
chs[i] = 0;
process(chs,i+1);
chs[i] = temp;
}
private static void fun(String str){
char[] chs = str.toCharArray();
process(chs,0,new ArrayList());
}
//来到i 要不要两种选择
//res 之前的选择形成的列表
private static void process(char[] chs, int i, List res) {
if (i == chs.length){
printList(res);
return;
}
List resKeep = copyList(res);
resKeep.add(chs[i]);
process(chs,i+1,resKeep);//要当前字符
List resNoInclude = copyList(res);
process(chs,i+1,resNoInclude);
}
private static List copyList(List res) {
List l = new LinkedList<>();
for (Character re : res) {
l.add(re);
}
return l;
}
private static void printList(List res) {
System.out.println(res);
}
}
例三–打印一个字符串的全部排列
打印一个字符串的全部排列
打印一个字符串的全部排列，要求不要出现重复的排列（排列组合）
public class code3 {
public static void main(String[] args) {
}
public static ArrayList permutation(String str){
ArrayList res = new ArrayList<>();
if (str == null || str.length() == 0) return res;
char[] chs = str.toCharArray();
process(chs,0,res);
//res.sort(null);
return res;
}
public static void process(char[] str, int i, ArrayList res){
if (i == str.length) res.add(String.valueOf(str));
boolean[] visit = new boolean[26];
for (int j = i; j < str.length; j++) {
if (!visit[str[j]-'a']){
visit[str[j]='a'] = true;
swap(str,i,j);
process(str,i+1,res);
swap(str,i,j);
}
}
}
public static void swap(char[] str, int i, int j){
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
}
例四
给定一个整型数组arr，代表数值不同的纸牌排成一条线。 玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。
[举例]
arr=[1, 2, 100, 4]。
开始时，玩家A只能拿走1或4。如果开始时玩家A拿走1，则排列变为[2, 100, 4]，接下来玩家B可以拿走2或4，然后继续轮到玩家A. …如果开始时玩家A拿走4，则排列变为[1, 2, 100]，接下来玩家B可以拿走1或100，然后继续轮到玩家A. …玩家A作为绝顶聪明的人不会先拿4，因为拿4之后，玩家B将拿走100。所以玩家A会先拿1，让排列变为[2, 100, 4]，接下来玩家B不管怎么选，100都会被玩家A拿走。玩家A会获胜,分数为101。所以返回101。
arr=[1, 100, 2]。
开始时，玩家A不管拿1还是2，玩家B作为绝项聪明的人，都会把100拿走。玩家B会获胜,分数为100。所以返回100。
public static int wim(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));
}
private 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));
}
逆序栈
给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。
如何实现?
public static void reverse(Stack例六s){ if (s.isEmpty()) return; int i = f(s); reverse(s); s.push(i); } public static int f(Stack s){ int res = s.pop(); if (s.isEmpty()){ return res; }else { int last = f(s); s.push(res); return last; } }
规定1和A对应、2和B对应、3和C对应…
那么一个数字字符串比如"111"，就可以转化为"A"、“KA” 和"AK"。
给定一个只有数字字符组成的字符串str，返回有多少种转化结果。
public class code6 {
public static void main(String[] args) {
}
public static int process(char[] str, int i){
if (i == str.length) return 1;
if (str[i] == '0') return 0;
if (str[i] == '1'){
int res = process(str,i+1); //单独一部分
if (i+1 < str.length){
res += process(str,i+2);//i和i+1作为一部分
}
return res;
}
if (str[i] == '2'){
int res = process(str,i+1);
if (i+1 < str.length && (str[i+1] >= '0' && str[i+1] <= '6')){
res += process(str,i+2);
}
return res;
}
//'3' -- '9'
return process(str,i+1);
}
}
例七
给定两个长度都为N的数组we i ghts和va lues, wei ghts[i]和va lues[i]分别代表i号物品的重量和价值。给定一一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量。返回你能装下最多的价值是多少?
public static int process(int[] weights, int[] values, int i, int alreadweight, int bag){
if (alreadweight > bag) return 0;
if (i == weights.length) return 0;
return Math.max(
process(weights,values,i+1,alreadweight,bag),
values[i]+process(weights,values,i+1,
alreadweight+weights[i],bag)
);
}
public static int process2(int[] weights, int[] values, int i, int alreadweight, int alreadvalue, int bag){
if (alreadweight > bag) return 0;
if (i == weights.length) return alreadvalue;
return Math.max(
process2(weights,values,i+1,alreadweight,alreadvalue,bag),
process2(weights,values,i+1,
alreadweight+weights[i],alreadvalue+values[i],bag)
);
}
总结
