第一题：游戏通关的最短时间，描述太复杂了，看懵了。应该是一道动态规划题。
解题思路：
就是进入到每一关卡时会有三种状态，记为
：
- 手上持有道具（
）
- 上一关卡使用过道具（
）
- 啥也没有（
）
我们使用
表示来到第
关且为状态时，过关包括关以后所有后续关卡的最短时间。有
- 当前是
；
- 当前是
；
- 当前是
。
那么不多说，上代码：
public class No1 {
public static class State {
static int HAND = 0, USED = 1, NONE = 2;
}
public static int dpSolver(int[] games) {
if (games.length == 0) return 0;
int[][] dp = new int[games.length + 1][3];
int completeTime, halfTime;
for (int i = games.length - 1; i >= 0; i--) {
completeTime = games[i];
halfTime = completeTime / 2;
dp[i][State.HAND] = Math.min(
dp[i + 1][State.HAND] + completeTime,
dp[i + 1][State.USED] + halfTime
);
dp[i][State.USED] = Math.min(
dp[i + 1][State.HAND] + completeTime,
dp[i + 1][State.NONE] + halfTime
);
dp[i][State.NONE] = dp[i + 1][State.HAND] + completeTime;
}
return dp[0][State.HAND];
}
public static void main(String[] args) {
// Scanner scanner = new Scanner(System.in);
//
// while (scanner.hasNext()) {
// int n = scanner.nextInt();
// int[] games = new int[n];
//
// for (int i = 0; i < n; i++) {
// games[i] = scanner.nextInt();
// }
//
// System.out.println(dfs(games, 0, State.HAND));
// }
System.out.println(dpSolver(new int[]{5, 4, 1, 6, 6}));
System.out.println(dpSolver(new int[]{5, 4, 6, 100, 1000}));
}
}
第二题：给定一串二叉树的先序序列化后的结果。例如“abc##d###”（字母表示节点值，#表示空姐点），输入反序列化后的树的中序遍历结果，即“cbda”。这道题简单，甚至无需构造二叉树，直接上代码：
import java.util.Scanner;
public class Main {
public static int ptr;
public static void handler(String codes, StringBuilder sb) {
if (ptr == codes.length()) return;
char val = codes.charAt(ptr++);
if (val == '#') return;
handler(codes, sb);
sb.append(val);
handler(codes, sb);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
String codes = scanner.next();
ptr = 0;
StringBuilder sb = new StringBuilder();
handler(codes, sb);
System.out.println(sb.toString());
}
}
} 先发这两道题出来把，第三题只a了一半，惭愧。。第四题根本没看。。
全部评论
(1) 回帖