admin管理员组文章数量:1530053
目录
暴力递归
打印n层汉诺塔从最左边移动到最右边的全部过程
给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。如何实现？
补充：二叉树的序列化和反序列化，中序遍历不能反序列化 （有歧义） 不能成套
打印一个字符串的全部子序列
打印一个字符串的全部子序列，要求不要出现重复字面值的子序列
打印一个字符串的全部排列
打印一个字符串的全部排列，要求不要出现重复的排列
从左往右的尝试模型
规定1和A对应、2和B对应、3和C对应...那么一个数字字符串比如“111”就可以转换为：AAA、KA、AK，给定一个只有数字字符串组成的字符串str，返回有多少种转化结果
给定俩个长度都为N的数组weights和values，weight[i]和value[i]分别代表i号物品的重量和价值。给定一个正数bag，表示一个载重bag的袋子，你装的物品不能超过这个重量，返回你能装下最多的价值是多少？
编辑
范围上尝试的模型
给定一个整形数组arr，代表数值不同的纸牌排成一条线，玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。
思路拓展-博弈论
博弈一：编辑
博弈论二：
博弈论三：
N皇后问题
斐波那契数列
什么暴力递归可以继续优化
题目一：假设有排成一行的N个位置，记为1~N，N一定大于或等于2，
暴力递归
记忆化搜索
动态规划
暴力递归-->记忆化搜索-->动态规划
一个arr数组，数组中是货币的面值，每一种面值都可以用任意张，arr都是正数且没有重复值。Aim = 1000，用arr中的面值返回达到1000的多少种方法
暴力递归
记忆化搜索
动态规划
给定一个字符串str，给定一个字符串类型的数组arr，arr里的每一字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str。返回需要至少多少张贴纸可以完成这个任务。
理论输出
什么样的暴力递归可以继续优化
暴力递归和动态规划的关系
面试题和动态规划的关系
如何找到某个问题的动态规划方式
面试中设计暴力递归过程的原则
其他原则汇总
多样本位置全对应的尝试模型
俩个字符串的最长公共子序列问题
//给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
寻找业务限制的尝试模型
给定一个数组，代表每个人喝完咖啡准备刷杯子的时间，只有一台咖啡机，一次只能洗一个杯子，时间耗费a，洗完才能洗下一个杯，每个咖啡杯也可以自己挥发干净，时间耗费b咖啡杯可以并行挥发，返回所有咖啡杯变干净的最早完成时间。三个参数arr、a、b
暴力递归
暴力递归就是尝试
1）把问题转化为规模缩小了的同类问题的子问题
2）有明确的不需要继续进行递归的条件（base case）
3）有当得到了子问题的结果之后的决策过程
4）不记录每一个子问题的解
打印n层汉诺塔从最左边移动到最右边的全部过程
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) { // base
System.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);
}
}给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。如何实现？
package class12;
import java.util.Stack;
public class Code02_ReverseStackUsingRecursive {
public static void reverse(Stack<Integer> stack) {
if (stack.isEmpty()) {
return;
}
int i = f(stack);
reverse(stack);
stack.push(i);
}
// 栈底元素移除掉
// 上面的元素盖下来
// 返回移除掉的栈底元素
public static int f(Stack<Integer> 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) {
Stack<Integer> test = new Stack<Integer>();
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());
}
}
}
动态规划是某一类的暴力递归 优化后的问题
补充：二叉树的序列化和反序列化，中序遍历不能反序列化 （有歧义） 不能成套
package class12;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Code03_SerializeAndReconstructTree {
/*
* 二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化，
* 以下代码全部实现了。
* 但是，二叉树无法通过中序遍历的方式实现序列化和反序列化
* 因为不同的两棵树，可能得到同样的中序序列，即便补了空位置也可能一样。
* 比如如下两棵树
* __2
* /
* 1
* 和
* 1__
* \
* 2
* 补足空位置的中序遍历结果都是{ null, 1, null, 2, null}
*
* */
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static Queue<String> preSerial(Node head) {
Queue<String> ans = new LinkedList<>();
pres(head, ans);
return ans;
}
public static void pres(Node head, Queue<String> ans) {
if (head == null) {
ans.add(null);
} else {
ans.add(String.valueOf(head.value));
pres(head.left, ans);
pres(head.right, ans);
}
}
public static Queue<String> inSerial(Node head) {
Queue<String> ans = new LinkedList<>();
ins(head, ans);
return ans;
}
public static void ins(Node head, Queue<String> ans) {
if (head == null) {
ans.add(null);
} else {
ins(head.left, ans);
ans.add(String.valueOf(head.value));
ins(head.right, ans);
}
}
public static Queue<String> posSerial(Node head) {
Queue<String> ans = new LinkedList<>();
poss(head, ans);
return ans;
}
public static void poss(Node head, Queue<String> ans) {
if (head == null) {
ans.add(null);
} else {
poss(head.left, ans);
poss(head.right, ans);
ans.add(String.valueOf(head.value));
}
}
public static Node buildByPreQueue(Queue<String> prelist) {
if (prelist == null || prelist.size() == 0) {
return null;
}
return preb(prelist);
}
public static Node preb(Queue<String> prelist) {
String value = prelist.poll();
if (value == null) {
return null;
}
Node head = new Node(Integer.valueOf(value));
head.left = preb(prelist);
head.right = preb(prelist);
return head;
}
public static Node buildByPosQueue(Queue<String> poslist) {
if (poslist == null || poslist.size() == 0) {
return null;
}
// 左右中 -> stack(中右左)
Stack<String> stack = new Stack<>();
while (!poslist.isEmpty()) {
stack.push(poslist.poll());
}
return posb(stack);
}
public static Node posb(Stack<String> posstack) {
String value = posstack.pop();
if (value == null) {
return null;
}
Node head = new Node(Integer.valueOf(value));
head.right = posb(posstack);
head.left = posb(posstack);
return head;
}
public static Queue<String> levelSerial(Node head) {
Queue<String> ans = new LinkedList<>();
if (head == null) {
ans.add(null);
} else {
ans.add(String.valueOf(head.value));
Queue<Node> queue = new LinkedList<Node>();
queue.add(head);
while (!queue.isEmpty()) {
head = queue.poll(); // head 父 子
if (head.left != null) {
ans.add(String.valueOf(head.left.value));
queue.add(head.left);
} else {
ans.add(null);
}
if (head.right != null) {
ans.add(String.valueOf(head.right.value));
queue.add(head.right);
} else {
ans.add(null);
}
}
}
return ans;
}
public static Node buildByLevelQueue(Queue<String> levelList) {
if (levelList == null || levelList.size() == 0) {
return null;
}
Node head = generateNode(levelList.poll());
Queue<Node> queue = new LinkedList<Node>();
if (head != null) {
queue.add(head);
}
Node node = null;
while (!queue.isEmpty()) {
node = queue.poll();
node.left = generateNode(levelList.poll());
node.right = generateNode(levelList.poll());
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
return head;
}
public static Node generateNode(String val) {
if (val == null) {
return null;
}
return new Node(Integer.valueOf(val));
}
// for test
public static Node generateRandomBST(int maxLevel, int maxValue) {
return generate(1, maxLevel, maxValue);
}
// for test
public static Node generate(int level, int maxLevel, int maxValue) {
if (level > maxLevel || Math.random() < 0.5) {
return null;
}
Node head = new Node((int) (Math.random() * maxValue));
head.left = generate(level + 1, maxLevel, maxValue);
head.right = generate(level + 1, maxLevel, maxValue);
return head;
}
// for test
public static boolean isSameValueStructure(Node head1, Node head2) {
if (head1 == null && head2 != null) {
return false;
}
if (head1 != null && head2 == null) {
return false;
}
if (head1 == null && head2 == null) {
return true;
}
if (head1.value != head2.value) {
return false;
}
return isSameValueStructure(head1.left, head2.left) && isSameValueStructure(head1.right, head2.right);
}
// for test
public static void printTree(Node head) {
System.out.println("Binary Tree:");
printInOrder(head, 0, "H", 17);
System.out.println();
}
public static void printInOrder(Node head, int height, String to, int len) {
if (head == null) {
return;
}
printInOrder(head.right, height + 1, "v", len);
String val = to + head.value + to;
int lenM = val.length();
int lenL = (len - lenM) / 2;
int lenR = len - lenM - lenL;
val = getSpace(lenL) + val + getSpace(lenR);
System.out.println(getSpace(height * len) + val);
printInOrder(head.left, height + 1, "^", len);
}
public static String getSpace(int num) {
String space = " ";
StringBuffer buf = new StringBuffer("");
for (int i = 0; i < num; i++) {
buf.append(space);
}
return buf.toString();
}
public static void main(String[] args) {
int maxLevel = 5;
int maxValue = 100;
int testTimes = 1000000;
System.out.println("test begin");
for (int i = 0; i < testTimes; i++) {
Node head = generateRandomBST(maxLevel, maxValue);
Queue<String> pre = preSerial(head);
Queue<String> pos = posSerial(head);
Queue<String> level = levelSerial(head);
Node preBuild = buildByPreQueue(pre);
Node posBuild = buildByPosQueue(pos);
Node levelBuild = buildByLevelQueue(level);
if (!isSameValueStructure(preBuild, posBuild) || !isSameValueStructure(posBuild, levelBuild)) {
System.out.println("Oops!");
}
}
System.out.println("test finish!");
}
}
打印一个字符串的全部子序列
public static List<String> subs(String s) {
char[] str = s.toCharArray();
String path = "";
List<String> ans = new ArrayList<>();
process1(str, 0, ans, path);
return ans;
}
// str 固定参数
// index此时来到的位置，要 or 不要
// 什么是终止位置，最后一个字符。后面的位置
// 如果index来到了str中的终止位置，把沿途路径所形成的答案，放入ans中
// 之前做出的选择，就是path
// 来到了str[index]字符，index是位置
// str[0..index-1]已经走过了！之前的决定，都在path上
// 之前的决定已经不能改变了，就是path
// str[index....]还能决定，之前已经确定，而后面还能自由选择的话，
// 把所有生成的子序列，放入到ans里去
public static void process1(char[] str, int index, List<String> 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 List<String> subsNoRepeat(String s) {
char[] str = s.toCharArray();
String path = "";
HashSet<String> set = new HashSet<>();
process2(str, 0, set, path);
List<String> ans = new ArrayList<>();
for (String cur : set) {
ans.add(cur);
}
return ans;
}
public static void process2(char[] str, int index, HashSet<String> 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 List<String> permutation2(String s) {
List<String> ans = new ArrayList<>();
if (s == null || s.length() == 0) {
return ans;
}
char[] str = s.toCharArray();
g1(str, 0, ans);
return ans;
}
// str[0...i-1]已经做好决定的
// str[i...]都有机会来到i位置
// index 终止位置，str当前的样子，就是一种结果，放入到ans中
public static void g1(char[] str, int index, List<String> ans) {
if (index == str.length) {
ans.add(String.valueOf(str));
} else {
// 如果i没有终止，i.... 版权声明：本文标题：暴力递归记忆化搜索动态规划 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/xitong/1726763209a1083336.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论