5.9美团笔试5道算法题

本人的战绩如下：

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));
        }
    }
}

t2：100%

思路：滑动窗口。

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

#美团##笔试题目#