251011 去哪儿AI面的笔试

侥幸做出来，分享一下

第一题

求nums中被三整除且不含三的数字个数

其中，可以对区间[l, r]进行一次操作，都+1或-1，也可以不操作。

求可能的个数的最大值和最小值

思路：分别计算+1和-1的差值数组后，计算它们最大连续子数组之和，得到最大值和最小值

import java.util.Scanner;


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int nums[] = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = in.nextInt();
            }
            // valid[0]表示原来nums数组的对应数字是否成立
            // valid[1]和valid[2]表示nums对应数字+1和-1后是否还成立
            int cnt = 0, valid[][] = new int[3][n];
            for (int i = 0; i < n; i++) {
                int x = nums[i], sum = 0;
                if (check(nums[i])) {
                    valid[0][i] = 1;
                    cnt++;
                }
                if (check(nums[i]+1)) {
                    valid[1][i] = 1;
                }
                if (check(nums[i]-1)) {
                    valid[2][i] = 1;
                }
            }
            int max = cnt, min = cnt;
            for (int i = 0; i < n; i++) {  // 分别计算+1和-1后的差值
                valid[1][i] -= valid[0][i];
                valid[2][i] -= valid[0][i];
            }
            int add1 = getBigest(valid[1]), add2 = getBigest(valid[2]);  // 计算差值的最大值
            for (int i = 0; i < n; i++) {
                valid[1][i] = -valid[1][i];
                valid[2][i] = -valid[2][i];
            }
            int del1 = -getBigest(valid[1]), del2 = -getBigest(valid[2]);  // 计算差值的最小值（即计算负数的最大值的相反数）
            int res[] = new int[2];
            res[0] = cnt + Math.max(add1, add2);
            res[1] = cnt + Math.min(del1, del2);
            System.out.println(res[0] + " " + res[1]);
        }
    }
    private static int getBigest(int nums[]) {  // 获得nums的最大连续子数组之和
        int n = nums.length;
        int cur = 0, res = -(int)1e9;
        for (int i = 0; i < n; i++) {
            cur += nums[i];
            res = Math.max(res, cur);
            if (cur < 0) cur = 0;
        }
        return res;
    }
    private static boolean check(int x) {  // x这个数字是否成立
        int sum = 0;
        while (x > 0) {
            int cur = x % 10;
            if (cur == 3) break;
            sum += cur;
            x /= 10;
        }
        return x == 0 && sum % 3 == 0;
    }
}

第二题

对于一个区间[l,r]，g(b)表示这个区间的中位数，min(l,r)表示区间的最小值

计算所有区间的g(b) － min(l,r)的最大值

思路：遍历每一个可能的中位数，贪心可以想到，这个中位数所在的区间越大越好，直到边界，可以拿到最小的min(l,r)。用两个方向的前缀最小值避免重复计算

import java.util.Scanner;


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int T = in.nextInt();
            for (int t = 0; t < T; t++) {
                int n = in.nextInt(), nums[] = new int[n];
                for (int i = 0; i < n; i++) nums[i] = in.nextInt();
                // 两个方向的前缀最小值
                int leftMin[] = new int[n], rightMin[] = new int[n];
                leftMin[0] = nums[0]; rightMin[n-1] = nums[n-1];
                for (int i = 1; i < n; i++) {
                    leftMin[i] = Math.min(leftMin[i-1], nums[i]);
                }
                for (int i = n-2; i >= 0; i--) {
                    rightMin[i] = Math.min(rightMin[i+1], nums[i]);
                }
                // 0 1 2 -> 
                // 0 1 2 3 4-> 
                int res = 0;
                for (int i = 0; i < n; i++) {
                    if (i <= n/2) {  // 中位数在左边，找到区间的右边界
                        int r = Math.min(n-1, i*2);
                        res = Math.max(res, nums[i] - leftMin[r]);
                    } else {  // 中位数在右边，找到区间的左边界
                        int l = i - (n-i);
                        res = Math.max(res, nums[i] - rightMin[l]);
                    }
                }
                System.out.println(res);
            }
        }
    }
}