如何进行网站营销,制造业中小微企业,wordpress 字段点击数,小型工作室创业项目一 暴力递归就是尝试 1#xff0c;把问题转化为规模缩小了的同类问题的子问题 2#xff0c;有明确的不需要继续进行递归的条件(base case) 3#xff0c;有当得到了子问题的结果之后的决策过程 4#xff0c;不记录每一个子问题的解 二 打印n层汉诺塔从最左边移动到最右边的全…一 暴力递归就是尝试 1把问题转化为规模缩小了的同类问题的子问题 2有明确的不需要继续进行递归的条件(base case) 3有当得到了子问题的结果之后的决策过程 4不记录每一个子问题的解 二 打印n层汉诺塔从最左边移动到最右边的全部过程
2.1 描述 打印n层汉诺塔从最左边移动到最右边的全部过程 2.1 分析 第一步
从以下三个步骤来进行移动补齐相应的函数 第二步
leftToMid(n - 1); 其实就是定义六个过程 总结 2.3代码
package class17;import java.util.HashSet;
import java.util.Stack;public class Code02_Hanoi {public static void hanoi1(int n) {leftToRight(n);}// 请把1~N层圆盘 从左 - 右public static void leftToRight(int n) {if (n 1) { // base caseSystem.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层圆盘 从左 - 中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);}public static void hanoi2(int n) {if (n 0) {func(n, left, right, mid);}}public static void func(int N, String from, String to, String other) {if (N 1) { // baseSystem.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);}}public static class Record {public int level;public String from;public String to;public String other;public Record(int l, String f, String t, String o) {level l;from f;to t;other o;}}// 之前的迭代版本很多同学表示看不懂// 所以我换了一个更容易理解的版本// 看注释吧好懂// 你把汉诺塔问题想象成二叉树// 比如当前还剩i层其实打印这个过程就是// 1) 去打印第一部分 - 左子树// 2) 打印当前的动作 - 当前节点// 3) 去打印第二部分 - 右子树// 那么你只需要记录每一个任务 : 有没有加入过左子树的任务// 就可以完成迭代对递归的替代了public static void hanoi3(int N) {if (N 1) {return;}// 每一个记录进栈StackRecord stack new Stack();// 记录每一个记录有没有加入过左子树的任务HashSetRecord finishLeft new HashSet();// 初始的任务认为是种子stack.add(new Record(N, left, right, mid));while (!stack.isEmpty()) {// 弹出当前任务Record cur stack.pop();if (cur.level 1) {// 如果层数只剩1了// 直接打印System.out.println(Move 1 from cur.from to cur.to);} else {// 如果不只1层if (!finishLeft.contains(cur)) {// 如果当前任务没有加入过左子树的任务// 现在就要加入了// 把当前的任务重新压回去因为还不到打印的时候// 再加入左子树任务finishLeft.add(cur);stack.push(cur);stack.push(new Record(cur.level - 1, cur.from, cur.other, cur.to));} else {// 如果当前任务加入过左子树的任务// 说明此时已经是第二次弹出了// 说明左子树的所有打印任务都完成了// 当前可以打印了// 然后加入右子树的任务// 当前的任务可以永远的丢弃了// 因为完成了左子树、打印了自己、加入了右子树// 再也不用回到这个任务了System.out.println(Move cur.level from cur.from to cur.to);stack.push(new Record(cur.level - 1, cur.other, cur.to, cur.from));}}}}public static void main(String[] args) {int n 3;hanoi1(n);System.out.println();hanoi2(n);System.out.println();hanoi3(n);}}2.4 启发 将上面的六个过程进行抽象话 增加参数如下
上面的六个过程都可以用 from to other 来代替
第一步
第二步 public static void hanoi2(int n) {if (n 0) {func(n, left, right, mid);}}//1-N 在 from
// 去to
// 宁一个 other public static void func(int N, String from, String to, String other) {if (N 1) { // baseSystem.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);}}
三 打印一个字符串的全部子序列可以不连续的 3.2 分析
3.3 代码
package class17;import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;public class Code03_PrintAllSubsquences {// s - abc -public static ListString subs(String s) {char[] str s.toCharArray();String path ;ListString ans new ArrayList();process1(str, 0, ans, path);return ans;}// str 固定参数// 来到了str[index]字符index是位置// str[0..index-1]已经走过了之前的决定都在path上// 之前的决定已经不能改变了就是path// str[index....]还能决定之前已经确定而后面还能自由选择的话// 把所有生成的子序列放入到ans里去public static void process1(char[] str, int index, ListString ans, String path) {if (index str.length) {ans.add(path);return;}// 没有要index位置的字符process1(str, index 1, ans, path);// 要了index位置的字符process1(str, index 1, ans, path String.valueOf(str[index]));}//打印一个字符串的全部子序列要求不要出现重复字面值的子序列public static ListString subsNoRepeat(String s) {char[] str s.toCharArray();String path ;HashSetString set new HashSet();process2(str, 0, set, path);ListString ans new ArrayList();for (String cur : set) {ans.add(cur);}return ans;}public static void process2(char[] str, int index, HashSetString 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);}public static void main(String[] args) {String test acccc;ListString ans1 subs(test);ListString ans2 subsNoRepeat(test);for (String str : ans1) {System.out.println(str);}System.out.println();for (String str : ans2) {System.out.println(str);}System.out.println();}}3.4 打印一个字符串的全部子序列要求不要出现重复字面值的子序列 public static ListString subsNoRepeat(String s) {char[] str s.toCharArray();String path ;HashSetString set new HashSet();process2(str, 0, set, path);ListString ans new ArrayList();for (String cur : set) {ans.add(cur);}return ans;}public static void process2(char[] str, int index, HashSetString 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);}四 打印一个字符串的全部排列
4.1 描述 4.2 分析
for 循环里面是跑支路每到下一个支路的时候都要将之前删除的加回来恢复现场 4.3 分析二 4.4代码
package class17;import java.util.ArrayList;
import java.util.List;public class Code04_PrintAllPermutations {public static ListString permutation1(String s) {ListString ans new ArrayList();if (s null || s.length() 0) {return ans;}char[] str s.toCharArray();ArrayListCharacter rest new ArrayListCharacter();for (char cha : str) {rest.add(cha);}String path ;f(rest, path, ans);return ans;}public static void f(ArrayListCharacter rest, String path, ListString ans) {if (rest.isEmpty()) {ans.add(path);} else {int N rest.size();for (int i 0; i N; i) {char cur rest.get(i);rest.remove(i);f(rest, path cur, ans);rest.add(i, cur);}}}public static ListString permutation2(String s) {ListString ans new ArrayList();if (s null || s.length() 0) {return ans;}char[] str s.toCharArray();g1(str, 0, ans);return ans;}
分析二交换的代码public static void g1(char[] str, int index, ListString ans) {if (index str.length) {ans.add(String.valueOf(str));} else {for (int i index; i str.length; i) {swap(str, index, i);g1(str, index 1, ans);swap(str, index, i);}}}public static ListString permutation3(String s) {ListString ans new ArrayList();if (s null || s.length() 0) {return ans;}char[] str s.toCharArray();g2(str, 0, ans);return ans;}public static void g2(char[] str, int index, ListString ans) {if (index str.length) {ans.add(String.valueOf(str));} else {//4.4 打印一个字符串的全部排列要求不要出现重复的排列boolean[] visited new boolean[256];//去除重复的for (int i index; i str.length; i) {if (!visited[str[i]]) {visited[str[i]] true;swap(str, index, i);g2(str, index 1, ans);swap(str, index, i);}}}}public static void swap(char[] chs, int i, int j) {char tmp chs[i];chs[i] chs[j];chs[j] tmp;}public static void main(String[] args) {String s acc;ListString ans1 permutation1(s);for (String str : ans1) {System.out.println(str);}System.out.println();ListString ans2 permutation2(s);for (String str : ans2) {System.out.println(str);}System.out.println();ListString ans3 permutation3(s);for (String str : ans3) {System.out.println(str);}}}4.4 打印一个字符串的全部排列要求不要出现重复的排列
4.4.1 分析 判断每一个支路看这个字符是否试过了 4.4.2 代码
public static ListString permutation3(String s) {ListString ans new ArrayList();if (s null || s.length() 0) {return ans;}char[] str s.toCharArray();g2(str, 0, ans);return ans;}public static void g2(char[] str, int index, ListString ans) {if (index str.length) {ans.add(String.valueOf(str));} else {boolean[] visited new boolean[256];for (int i index; i str.length; i) {if (!visited[str[i]]) {visited[str[i]] true;swap(str, index, i);g2(str, index 1, ans);swap(str, index, i);}}}}五 仰望好的尝试这个题练递归特别好
5.1 描述 给你一个栈请你逆序这个栈 不能申请额外的数据结构 只能使用递归函数。 如何实现? 5.2 分析 5.3 代码
package class17;import java.util.Stack;public class Code05_ReverseStackUsingRecursive {public static void reverse(StackInteger stack) {if (stack.isEmpty()) {return;}int i f(stack);reverse(stack);stack.push(i);}// 栈底元素移除掉// 上面的元素盖下来// 返回移除掉的栈底元素public static int f(StackInteger stack) {int result stack.pop();if (stack.isEmpty()) {return result;} else {int last f(stack);stack.push(result);return last;}}public static void main(String[] args) {StackInteger test new StackInteger();test.push(1);test.push(2);test.push(3);test.push(4);test.push(5);reverse(test);while (!test.isEmpty()) {System.out.println(test.pop());}}}5.4 不用递归代码
