2024.8.23饿了么后端笔试ak

秋招第二次ak！还好第三题没考什么高级数据结构......

1）贪心，删除第一个严格递减的位置。注意爆int。复杂度O(n*lgC)

2）dp。dp[i]表示前i个数的最大权值和，有dp[i] = max{ dp[i - j] + w( arr[i-j : i-1] ) } (1≤j≤(i-1))。注意爆int。复杂度O(n^2)

3）有亿点麻烦的bfs。

• 创建一个网格grid[10][9]，0表示空，1-5表示卒的编号，6表示对面九宫（对面九宫的范围是grid[0:2][3:5]）。
• 用一个整数state表示当前卒的存活情况，第(i-1)个二进制位表示编号为i的卒是否已消灭，例如30=(11110)_2表示除1号卒外均已被消灭。
• 定义状态为(x, y, state)，xy为当前马的位置。
• 定义哈希函数h(x, y, state) = (state<<7) + 9*x + y。
• 预处理移动方向：directions = {{1, 2}, {1, -2}, ...}。
• 预处理每个移动方向对应的蹩马腿点位: leg = {{0, 1}, {0, -1}, ...}。
• 注意输入的下标是从1开始，要手动减1。

单组用例最坏复杂度 O(方向数(8)*格子数(10*9)*卒的状态数(32))

等下贴代码。

public class Q1 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long ans = 0;
        for (int i = 0; i < n; i++) {
            int num = in.nextInt();
            if (num < 10) {
                continue;
            }
            char[] arr = String.valueOf(num).toCharArray();
            int len = arr.length;
            int k = 0;
            while (k < len - 1 && arr[k] <= arr[k + 1]) {
                k++;
            }
            StringBuilder builder = new StringBuilder().append(num);
            builder.deleteCharAt(k);
            ans += Integer.parseInt(builder.toString());
        }
        System.out.println(ans);
    }
}

public class Q2 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        long[] dp = new long[n + 1];
        int MAX = 1_000_000_001;
        for (int i = 0; i < n; i++) {
            int max = 0, min = MAX;
            for (int j = i; j < n; j++) {
                max = Math.max(arr[j], max);
                min = Math.min(arr[j], min);
                dp[j + 1] = Math.max(dp[j + 1], max - min + dp[i]);
            }
        }
        System.out.println(dp[n]);
    }
}

public class Q3 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for (int t = 0; t < T; t++) {
            int[][] grid = new int[10][9];
            for(int i = 0; i < 3; i++) {
                for (int j = 3; j < 6; j++) {
                    grid[i][j] = 6; // 九宫范围
                }
            }
            int x0 = in.nextInt() - 1, y0 = in.nextInt() - 1;
            for (int i = 1; i <= 5; i++) {
                grid[in.nextInt() - 1][in.nextInt() - 1] = i;   // 卒的位置
            }
            System.out.println(solve(x0, y0, grid));
        }
    }

    private static int[][] dirs = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
    private static int[][] leg = {{0, 1}, {0, -1}, {0, 1}, {0, -1}, {1, 0}, {1, 0}, {-1, 0}, {-1, 0}};

    private static int hash(int x, int y, int state) {
        return (state << 7) + 9 * x + y;
    }

    private static int solve(int x0, int y0, int[][] grid) {
        Set<Integer> visited = new HashSet<>();
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{x0, y0, 0});
        visited.add(hash(x0, y0, 0));
        int step = 0;
        while (!q.isEmpty()) {
            step++;
            int n = q.size();
            for (int i = 0; i < n; i++) {
                int[] cur = q.poll();
                int x = cur[0], y = cur[1], state = cur[2];
                for (int j = 0; j < 8; j++) {
                    int xx = x + dirs[j][0], yy = y + dirs[j][1];
                    if (xx < 0 || xx > 9 || yy < 0 || yy > 8) {
                        continue;
                    }
                    int legPos = grid[x + leg[j][0]][y + leg[j][1]];
                    if (legPos > 0 && legPos < 6 && ((state >> (legPos - 1)) & 1) == 0) {
                        continue;
                    }
                    int target = grid[xx][yy];
                    if (target > 0 && target < 6) {
                        state |= (1 << (target - 1));
                    }
                    if (target == 6 && state == 31) {
                        return step;
                    }
                    int h = hash(xx, yy, state);
                    if (visited.contains(h)) {
                        continue;
                    }
                    visited.add(h);
                    q.offer(new int[]{xx, yy, state});
                }
            }
        }
        return -1;
    }
}