美团8.13笔试

第一题、int数组，时间t代表送货的平均时间，nums[i]代表订单的最晚截止时间，问有几个订单不能按时送到。

例：t=5,【5，6，7，8，9，10】，5满足，10满足，答案：4，因为，第二次送货时间是10，所以6，7，8，9不满足。

解答情况：27%，我怀疑我理解错题意了。

思路：模拟

解法：

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), t = sc.nextInt();
        int[] nums = new int[n];
        int res = 0, cnt = 1;
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
            if (nums[i] < cnt * t) {
                res++;
            } else {
                cnt++;
            }
        }
        System.out.println(res);
    }

第二题、机器人打扫房间。一个int型矩阵，给出一系列指令，可以向上下左右打扫。打扫完成输出Yes和用了几条指令，没完成输出No和还有几个单元没完成。

例：2*2矩阵，初始站在00位置，指令是WSWS，答案：No，2

解答情况：过了81%，解答错误。

思路：暴力

时空复杂度：n，1

解法：

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();
        String instructions = sc.next();
        HashSet<String> set = new HashSet<>();
        int[][] matrix = new int[n][m];
        int curX = 0, curY = 0;
        matrix[curX][curY] = 1;
        int num = 0;
        for (int i = 0; i < instructions.length(); i++) {
            if (instructions.charAt(i) == 'W') {
                curX = curX - 1;
            } else if (instructions.charAt(i) == 'S') {
                curX = curX + 1;
            } else if (instructions.charAt(i) == 'A') {
                curY = curY - 1;
            } else if (instructions.charAt(i) == 'D') {
                curY = curY + 1;
            }
            matrix[curX][curY] = 1;
            StringBuilder sb = new StringBuilder();
            sb.append(curX);
            sb.append(curY);
            set.add(new String(sb));
            if (set.size() == n * m) {
                num = i;
                break;
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 0) {
                    res++;
                }
            }
        }
        if (res == 0) {
            System.out.println("Yes\n" + num);
        } else {
            System.out.println("No\n" + res);
        }
    }

第三题、模拟，将数组中首部的数放到尾部，重复两次，然后删除第一个元素，直到没有元素。给你结果，还原这个数组。

例：【1，2，3，4】，答案：【4，2，1，3】

解答情况：过了81%，解答错误。

思路：逆向思维。倒序。添加元素，将数组中尾部的元素放到首部，重复两次。

第一次：放入【4】，

第二次：放入3，【3，4】，removeLast（），addFirst（），removeLast（），addFirst（），还是【3，4】

第三次：放入2，【2，3，4】，。。。，【3，4，2】

第四次：放入1，【1，3，4，2】，。。。，【4，2，1，3】

时空复杂度：n，n

解法：

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            list.addFirst(nums[i]);
            Integer last = list.removeLast();
            list.addFirst(last);
            Integer secondeLast = list.removeLast();
            list.addFirst(secondeLast);
        }
        for (Integer integer : list) {
            System.out.println(integer);
        }
    }

第四题、求三元组，满足i<j<k&&nums【i】-2nums【j】=2*nums【j】-nums【k】

思路：暴力

解答情况：81%，超时

时空复杂度：n3，1

解法：

                public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = sc.nextInt();
            }
            int res = 0;
            for (int i = 0; i < n - 2; i++) {
                int a = nums[i];
                for (int j = i + 1; j < n - 1; j++) {
                    int b = nums[j];
                    for (int k = j + 1; k < n; k++) {
                        int c = nums[k];
                        if (a - b == 2 * b - c) {
                            res++;
                        }
                    }
                }
            }
            System.out.println(res);
        }

第五题、节点之和最大的路径

例：【1，2，3】，root=1，left=2，right=3，最大和是4.

解答情况：ac。

思路：力扣原题

时空复杂度：n，n

解法：

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n+1];
        for (int i = 1; i <= n; i++) {
            nums[i] = sc.nextInt();
        }
        int res = traverse(1, nums);
        System.out.println(res);
    }

    private static int traverse(int index, int[] nums) {
        if (index < 0 || index >= nums.length) {
            return 0;
        }
        int left = traverse(index * 2, nums);
        int right = traverse(index * 2 + 1, nums);
        return Math.max(left, right) + nums[index];
    }

#美团笔试#