三个盘子，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;
}
mid 《一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》无偿开源 威信搜索公众号【编程进阶路】 ToLeft(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 subs(String s) {
char[] chars = s.toCharArray();
String path = “”;
List 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 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 subsNoRepeat(String s) {
char[] chars = s.toCharArray();
String path = “”;
Set set = new HashSet<>();
process1(chars, 0, set, path);
List ans = new ArrayList<>();
for (String cur : set) {
ans.add(cur);
}
return ans;
}
private static void process1(char[] chars, int index, Set 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 permutation(String s) {
List res = new ArrayList<>();
if (s == null || s.length() == 0) {
return res;
}
char[] chars = s.toCharArray();
List list = new ArrayList<>();
for (char ch : chars) {
list.add(ch);
}
String path = “”;
process(list, path, res);
return res;
}
private static void process(List rest, String path, List res) {
if (rest.isEmpty()) {
res.add(path);
return;
}
for (int i = 0; i < rest.size(); i++) {
char ch = rest.get(i);
rest.remove(i);
process(rest, path + ch, res);
rest.add(i, ch);
}
}
