秋招美团笔试

第一道

public class FirstProblem {

    public static void main(String[] args) {
        String[] strArrays = {"abc", "ab", "ac", "ac", "abcd"};
        String s = "abcd";
        long[] sum = getSum(strArrays, s);
        System.out.println(sum[0] + " " + sum[1]);
    }

    private static long[] getSum(String[] strArrays, String s) {
        long[] reslut = new long[2];
        int n = s.length();
        // TreeMap是有序的，按照key升序排序
        Map<Integer, Set<String>> queryMap = new TreeMap<>();

        // 遍历字符串数组，将字符串数组中的字符串按照长度分组
        for (String str : strArrays) {
            int len = str.length();
            if (!queryMap.containsKey(len)) {
                queryMap.put(len, new HashSet<>());
            }
            queryMap.get(len).add(str);
        }

        long preSum = 0;
        // 遍历queryMap的key
        for (int len : queryMap.keySet()) {
            if (len == n) {
                reslut[0] = preSum + 1;
                reslut[1] = preSum + queryMap.get(len).size();
                break;
            }
            preSum += queryMap.get(len).size();
        }

        return reslut;
    }
}

第二道

public class SecondProblem {

    static long minValue = Long.MAX_VALUE;

    public static void main(String[] args) {

        int[] nums = {4, 5, 2, 3, 1, 0};
        long k = 3l;
        long x = 3l;

        getMinValue(0, nums, k, x);
        System.out.println(minValue);
    }

    private static void getMinValue(long curVal,int[] nums, long k, long x) {
        if (nums.length == 0) {
            return;
        }
        // 删除整个元素的花销
        int[] nums1 = new int[nums.length];
        System.arraycopy(nums, 0, nums1, 0, nums.length);
        long value1 = curVal + k * missingPositive(nums1);

        // 删除第一个元素的花销
        int[] newNums = new int[nums.length - 1];
        System.arraycopy(nums, 1, newNums, 0, nums.length - 1);
        int[] nums2 = newNums;
        long value2 = curVal + x + k * missingPositive(nums2);

        minValue = Math.min(minValue, Math.min(value1, value2));
        getMinValue(minValue, newNums, k, x);
    }

    private static int missingPositive(int[] nums) {
        int len = nums.length;

        for (int i = 0; i < len; i++) {
            while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
                swap(nums, i, nums[i] - 1);
            }
        }
        for (int i = 0; i < len; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        return len + 1;
    }

    private static void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}