算法基础之递归，java 核心技术卷
汉诺塔(Tower of Hanoi)源于印度传说中，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着 64 片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
这是示意图，a 是起始柱，c 是目标柱，b 起到中转作用
在进行转移操作时，都必须确保大盘在小盘下面，且每次只能移动一个圆盘，最终 c 柱上有所有的盘子且也是从上到下按从小到大的顺序。
举例：
三个盘子，1-2 移到中，将 3 直接移动到右。再将 1-2 移动到右
public class Code01_Hanoi {
public static void main(String[] args) {
Hanoi(4);
}
public static void Hanoi(int n) {
leftToRight(n);
}
// 请把 1-N 层圆盘 从左-》右
public static void leftToRight(int n) {
if (n == 1) { // base case
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);
}
// 请把 1-N 层圆盘 从左-》中
private 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);
}
private 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 left to mid");
leftToMid(n - 1);
}
private 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 mid");
midToLeft(n - 1);
}
private 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);
}
private 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 class Code02_Hanoi {
public static void main(String[] args) {
func(3, "left", "right", "other");
}
public static void func(int N, String from, String to, String other) {
if (N == 1) {
System.out.println("Move 1 form " + from + " to " + to);
} else {
func(N - 1, from, other, to);
System.out.println("Move" + N + " form " + from + " to " + to);
func(N - 1, other, to, from);
}
}
}
打印一个字符串的全部子序列：
==============
可以不连续的
// "abc"
// 打印一个字符串的全部子序列
public static List<String> subs(String s) {
char[] chars = s.toCharArray();
String path = "";
List<String> res = new ArrayList<>();
process(chars, 0, res, path);
return res;
}
// str 固定参数
// 来到了 str[index]字符，index 是位置
// str[0..index-1]已经走过了！之前的决定，都在 path 上
// 之前的决定已经不能改变了，就是 path
// str[index....]还能决定，之前已经确定，而后面还能自由选择的话，
// 把所有生成的子序列，放入到 ans 里去
private static void process(char[] chars, int index, List<String> res, String path) {
if (index == chars.length) {
res.add(path);
return;
}
process(chars, index + 1, res, path);
process(chars, index + 1, res, path + chars[index]);
}
打印一个字符串的全部子序列，要求不要出现重复字面值的子序列
=============================
/**
打印一个字符串的全部子序列，要求不要出现重复字面值的子序列
*/
public static List<String> subsNoRepeat(String s) {
char[] chars = s.toCharArray();
String path = "";
Set<String> set = new HashSet<>();
process1(chars, 0, set, path);
List<String> ans = new ArrayList<>();
for (String cur : set) {
ans.add(cur);
}
return ans;
}
private static void process1(char[] chars, int index, Set<String> res, String path) {
if (index == chars.length) {
res.add(path);
return;
}
process1(chars, index + 1, res, path);
process1(chars, index + 1, res, path + chars[index]);
}
打印一个字符串的全部排列
============
public static List<String> permutation(String s) {
List<String> res = new ArrayList<>();
if (s == null || s.length() == 0) {
return res;
}
char[] chars = s.toCharArray();
List<Character> list = new ArrayList<>();
for (char ch : chars) {
list.add(ch);
}
String path = "";
process(list, path, res);
return res;
}
private static void process(List<Character> rest, String path, List<String> res) {
if (rest.isEmpty()) {
res.add(path);
return;
还未添加个人签名 2021.03.18 加入
还未添加个人简介
评论