第17节.pptx
暴力递归就是尝试
1，把问题转化为规模缩小了的同类问题的子问题
2，有明确的不需要继续进行递归的条件(base case)
3，有当得到了子问题的结果之后的决策过程
4，不记录每一个子问题的解
题目1：汉诺塔问题
打印n层汉诺塔从最左边移动到最右边的全部过程
public static void hanoi(int n) {fromLeftToRight(n);System.out.println("===================");process(n, "left", "right", "middle");}private static void fromLeftToRight(int n) {if (n == 1) {System.out.println("move 1 from left to right");return;}fromLeftToMiddle(n - 1);System.out.println("move " + n + " from left to right");fromMiddleToRight(n - 1);}private static void fromMiddleToRight(int n) {if (n == 1) {System.out.println("move 1 from middle to right");return;}fromMiddleToLeft(n - 1);System.out.println("move " + n + " from middle to right");fromLeftToRight(n - 1);}private static void fromMiddleToLeft(int n) {if (n == 1) {System.out.println("move 1 from middle to left");return;}fromMiddleToRight(n - 1);System.out.println("move " + n + " from middle to left");fromRightToLeft(n - 1);}private static void fromLeftToMiddle(int n) {if (n == 1) {System.out.println("move 1 from left to middle");return;}fromLeftToRight(n - 1);System.out.println("move " + n + " from left to middle");fromRightToMiddle(n - 1);}private static void fromRightToMiddle(int n) {if (n == 1) {System.out.println("move 1 from right to middle");return;}fromRightToLeft(n - 1);System.out.println("move " + n + " from right to middle");fromLeftToMiddle(n - 1);}private static void fromRightToLeft(int n) {if (n == 1) {System.out.println("move 1 from right to left");return;}fromRightToMiddle(n - 1);System.out.println("move " + n + " from right to left");fromMiddleToLeft(n - 1);}// 将以上递归进行抽象整合private static void process(int n, String from, String to, String other) {if (n == 1) {System.out.println("move " + n + " from " + from + " to " + to);return;}process(n - 1, from, other, to);System.out.println("move " + n + " from " + from + " to " + to);process(n - 1, other, to, from);}
题目2：打印一个字符串的全部子序列
// 返回一个字符串的全部子序列public static List<String> subSequence(String str) {if (str == null || str.length() == 0) {return null;}List<String> subString = new ArrayList<>();char[] chars = str.toCharArray();process(chars, 0, subString, "");return subString;}private static void process(char[] chars, int index, List<String> ans, String curSubString) {if (index == chars.length) {ans.add(curSubString);return;}// 没有要当前位置的字符process(chars, index + 1, ans, curSubString);// 要了当前位置的字符process(chars, index + 1, ans, curSubString.concat(String.valueOf(chars[index])));}// 返回一个字面值字符串不重复的全部子序列public static List<String> subSequenceNoRepeat(String str) {if (str == null || str.length() == 0) {return null;}HashSet<String> subString = new HashSet<>();char[] chars = str.toCharArray();process2(chars, 0, subString, "");return new ArrayList<>(subString);}private static void process2(char[] chars, int index, HashSet<String> ans, String curSubString) {if (index == chars.length) {ans.add(curSubString);return;}process2(chars, index + 1, ans, curSubString);process2(chars, index + 1, ans, curSubString.concat(String.valueOf(chars[index])));}
题目3：打印一个字符串的全部排列
// 返回一个字符串的全排列
public static List<String> allPermutation(String string) {
List<String> ans = new ArrayList<>();
if (string == null || string.length() == 0) {
return ans;
}
char[] str = string.toCharArray();
List<Character> chars = new ArrayList<>();
for (char c : str) {
chars.add(c);
}
process(chars, ans, "");
return ans;
}
private static void process(List<Character> chars, List<String> ans, String curSubString) {
if (chars.isEmpty()) {
ans.add(curSubString);
} else {
for (int i = 0; i < chars.size(); i++) {
char cur = chars.get(i);
chars.remove(i);
process(chars, ans, curSubString.concat(String.valueOf(cur)));
chars.add(i, cur);
}
}
}
public static List<String> allPermutation2(String string) {
List<String> ans = new ArrayList<>();
if (string == null || string.length() == 0) {
return ans;
}
char[] chars = string.toCharArray();
process2(chars, 0, ans);
return ans;
}
private static void process2(char[] chars, int index, List<String> ans) {
if (index == chars.length) {
ans.add(String.valueOf(chars));
} else {
for (int i = index; i < chars.length; i++) {
swap(chars, i, index);
process2(chars, index + 1, ans);
swap(chars, i, index);
}
}
}
private static void swap(char[] chars, int i, int j) {
char tmp = chars[i];
chars[i] = chars[j];
chars[j] = tmp;
}
// 去重的全排列
public static List<String> allPermutation3(String string) {
List<String> ans = new ArrayList<>();
if (string == null || string.length() == 0) {
return ans;
}
char[] chars = string.toCharArray();
process3(chars, 0, ans);
return ans;
}
private static void process3(char[] chars, int index, List<String> ans) {
if (index == chars.length) {
ans.add(String.valueOf(chars));
} else {
boolean[] visited = new boolean[256];
for (int i = index; i < chars.length; i++) {
// 剪枝 对于重复出现的字符，直接跳过
if (!visited[chars[i]]) {
visited[chars[i]] = true;
swap(chars, i, index);
process3(chars, index + 1, ans);
swap(chars, i, index);
}
}
}
}
题目4：逆序栈
给你一个栈，请你逆序这个栈，
不能申请额外的数据结构，
只能使用递归函数。 如何实现?
//给你一个栈，请你逆序这个栈，
//不能申请额外的数据结构，
//只能使用递归函数。 如何实现?
public static <T> void reverseStack(Stack<T> stack) {
if (stack == null || stack.empty()) {
return;
}
T last = precess(stack);
reverseStack(stack);
stack.push(last);
}
private static <T> T precess(Stack<T> stack) {
T cur = stack.pop();
if (stack.empty()) {
return cur;
} else {
T last = precess(stack);
stack.push(cur);
return last;
}
}
若有收获，就点个赞吧
0 人点赞
