本人的战绩如下：
100%、100%，45%，100%，64%
第三题和第五题超时，有哪位ac的大佬欢迎在评论区讨论一下
求美团爸爸一次面试机会，非常非常非常想去美团，球球了
t1：100%
trick：将坐标“拉直”， 注意去重，不然卡82%
package meituan.t1;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
static int n, m, tot;
static List<Integer>[] link, cost;
static int[] dis;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
m = in.nextInt();
n = in.nextInt();
tot = m * n - 1;
int k = in.nextInt();
link = new ArrayList[n * m];
cost = new ArrayList[n * m];
dis = new int[n * m];
for (int i = 0; i < n * m; i++) {
link[i] = new ArrayList<>();
cost[i] = new ArrayList<>();
dis[i] = Integer.MAX_VALUE;
}
int x, y, u, v, w;
for (int i = 1; i <= k; i++) {
x = in.nextInt() - 1;
y = in.nextInt() - 1;
u = in.nextInt() - 1;
v = in.nextInt() - 1;
w = in.nextInt();
if (x == u && y == v) continue; //注意去重，不然卡82%
link[x * n + y].add(u * n + v);
cost[x * n + y].add(w);
}
//初始值为0
dis[0] = 0;
dfs(0);
System.out.println(dis[tot] == Integer.MAX_VALUE ? -1 : dis[tot]);
}
static void dfs(int cur) {
if (cur == tot) return;
for (int i = 0; i < link[cur].size(); i++) {
dis[link[cur].get(i)] = Math.min(dis[link[cur].get(i)], dis[cur] + cost[cur].get(i));
dfs(link[cur].get(i));
}
}
}
思路：滑动窗口。
package meituan.t2;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), m = in.nextInt(), h = in.nextInt();
int height;
Queue<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
height = in.nextInt();
if (height <= h) queue.add(i);
if (queue.size() > 0) {
if (i - queue.peek() + 1 == m) {
if (queue.size() == m) {
System.out.println(queue.peek() + 1);
return;
} else queue.remove();
}
}
}
System.out.println(-1);
}
}
t3：45% ->TLE 思路：记忆化暴力搜索。。。
package meituan.t3;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.Scanner;
//t3
public class Main {
static int x, a, b, n;
static Map<Node, Long> map;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
while (t-- > 0) {
x = in.nextInt();
a = in.nextInt();
b = in.nextInt();
n = in.nextInt();
map = new HashMap<>();
System.out.println(dfs(0, x));
}
}
//记录两个值，cur 和 status
static long dfs(int cur, int status) {
if (status <= 0 || cur == n) return 0;
Node node = new Node(cur, status);
if (map.containsKey(node)) return map.get(node);
long res = Math.max(dfs(cur + 1, status > a ? status - a : 0) + status, dfs(cur + 1, status + b));
map.put(node, res);
return res;
}
}
class Node {
int time, status;
public Node(int time, int status) {
this.time = time;
this.status = status;
} public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node node = (Node) o;
return time == node.time &&
status == node.status;
}
public int hashCode() {
return Objects.hash(time, status);
}
} t4：100% 思路：广搜，多一维记录即可
package meituan.t4;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
//t4
public class Main {
static int n, m;
static int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
static char[][] map;
static int[][][] dis;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
m = in.nextInt();
n = in.nextInt();
in.nextLine();
map = new char[m][n];
//1表示有一次机会破坏，0表示没有机会破坏了
dis = new int[m][n][2];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dis[i][j][0] = dis[i][j][1] = Integer.MAX_VALUE;
}
}
dis[0][0][0] = dis[0][0][1] = 0;
for (int i = 0; i < m; i++) map[i] = in.nextLine().toCharArray();
Queue<Node> queue = new ArrayDeque<>();
queue.add(new Node(0, 0, 1));
Node root;
while (!queue.isEmpty()) {
root = queue.remove();
for (int i = 0; i < 4; i++) {
int dx = root.x + dir[i][0];
int dy = root.y + dir[i][1];
if (check(dx, dy)) {
if (map[dx][dy] == '*' && root.cnt == 1 && dis[dx][dy][0] > dis[root.x][root.y][1] + 1) {
dis[dx][dy][0] = dis[root.x][root.y][1] + 1;
queue.add(new Node(dx, dy, 0));
}
if (map[dx][dy] == '.' && dis[dx][dy][root.cnt] > dis[root.x][root.y][root.cnt] + 1) {
dis[dx][dy][root.cnt] = dis[root.x][root.y][root.cnt] + 1;
queue.add(new Node(dx, dy, root.cnt));
}
}
}
}
//拥有破坏一次障碍物的机会
int res = Math.min(dis[m - 1][n - 1][0], dis[m - 1][n - 1][1]);
System.out.println(res == Integer.MAX_VALUE ? -1 : res);
}
static boolean check(int x, int y) {
return x >= 0 && y >= 0 && x < m && y < n;
}
}
class Node {
int x, y, cnt;
Node(int x, int y, int cnt) {
this.x = x;
this.y = y;
this.cnt = cnt;
}
} t5：64% 思路：有点像力扣上的一道hard题，这里采用它的做法：记忆化暴力搜索。
package meituan.t5;
import java.util.Scanner;
//t5
public class Main {
static long[] pre1, pre2;
static long[] cost;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
cost = new long[26];
for (int i = 0; i < 26; i++) cost[i] = in.nextLong();
in.nextLine();
String s = in.nextLine();
String t = in.nextLine();
int len1 = s.length(), len2 = t.length();
pre1 = new long[len1];
pre2 = new long[len2];
for (int i = 0; i < len1; i++) pre1[i] = (i > 0 ? pre1[i - 1] : 0) + cost[s.charAt(i) - 'a'];
for (int i = 0; i < len2; i++) pre2[i] = (i > 0 ? pre2[i - 1] : 0) + cost[t.charAt(i) - 'a'];
long[][] dp = new long[len1][len2];
//删除的代价最少，那么剩余字符的价值总和应该是最大的
long res = dfs(s, 0, len1, t, 0, len2, dp);
System.out.println(pre1[len1 - 1] + pre2[len2 - 1] - res);
}
static long dfs(String s, int cur1, int len1, String t, int cur2, int len2, long[][] dp) {
if (cur1 == len1) return pre2[len2 - 1] - (cur2 > 0 ? pre2[cur2 - 1] : 0);
if (cur2 == len2) return pre1[len1 - 1] - (cur1 > 0 ? pre1[cur1 - 1] : 0);
if (dp[cur1][cur2] > 0) return dp[cur1][cur2];
long change;
if (s.charAt(cur1) == t.charAt(cur2)) change = dfs(s, cur1 + 1, len1, t, cur2 + 1, len2, dp);
else {
//删除s[cur1] 或者 删除t[cur2]
change = Math.min(dfs(s, cur1 + 1, len1, t, cur2, len2, dp) + cost[s.charAt(cur1) - 'a'],
dfs(s, cur1, len1, t, cur2 + 1, len2, dp) + cost[t.charAt(cur2) - 'a']);
}
return dp[cur1][cur2] = change;
}
}
//7 -5 4 6 2 5 8 -4 -8 4 10 -1 3 3 -5 10 7 0 -5 -4 -9 3 8 0 8 -3
//nygfh
//lixawy 
全部评论
(30) 回帖