力扣第 302 场周赛

比赛时间 2022-07-17。本场周赛国服共 2271 人 AK。刷新了周赛 AK 人数记录。。

T1. 数组能形成多少数对（3 分）

解题思路

模拟。

时间复杂度：O(n)。

参考代码

class Solution {
    public int[] numberOfPairs(int[] nums) {
        // 统计频次
        Map<Integer, Integer> cntMap = new HashMap<>();
        for (int num : nums) {
            cntMap.put(num, cntMap.getOrDefault(num, 0) + 1);
        }

        int[] answer = new int[2];
        for (Map.Entry<Integer, Integer> entry : cntMap.entrySet()) {
            int cnt = entry.getValue();
            // 形成的数对数目
            answer[0] += cnt / 2;
            if (cnt % 2 != 0) {
                // 剩下的整数数目
                answer[1] += 1;
            }
        }
        return answer;
    }
}

T2. 数位和相等数对的最大和（4 分）

解题思路

贪心。预处理所有数位和对应的元素，枚举每个数位和找 top2 元素更新最大值。

时间复杂度：O(nlogn)。

参考代码

class Solution {
    public int maximumSum(int[] nums) {
        Map<Integer, List<Integer>> cntMap = new HashMap<>();
        for (int num : nums) {
            int digitsSum = getDigitsSum(num);
            cntMap.computeIfAbsent(digitsSum, key -> new ArrayList<>()).add(num);
        }

        int max = -1;
        for (Map.Entry<Integer, List<Integer>> entry : cntMap.entrySet()) {
            List<Integer> list = entry.getValue();
            int size = list.size();
            if (size > 1) {
                // 取 top1 top2
                Collections.sort(list);
                max = Math.max(max, list.get(size - 1) + list.get(size - 2));
            }
        }
        return max;
    }

    // 数位和
    private int getDigitsSum(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}

T3. 裁剪数字后查询第 K 小的数字（5 分）

解题思路

数据范围不大，直接模拟。

时间复杂度：O((mn + nlogn) * l)。其中 n 为 nums.length，m 为 nums[i].length，l 为 queries.length。

也可用基数排序。

参考代码

class Solution {
    public int[] smallestTrimmedNumbers(String[] nums, int[][] queries) {

        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            res[i] = calc(nums, queries[i]);
        }
        return res;
    }

    private int calc(String[] nums, int[] query) {
        int k = query[0];
        int trim = query[1];

        List<Node> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int len = nums[i].length();
            String subStr = nums[i].substring(len - trim);
            // idx, num
            list.add(new Node(i, subStr));
        }
        list.sort((o1, o2) -> {
            if (o1.num.equals(o2.num)) {
                return Integer.compare(o1.idx, o2.idx);
            }
            return o1.num.compareTo(o2.num);
        });
        return list.get(k - 1).idx;
    }

    static class Node {
        int idx;
        String num;

        public Node(int idx, String num) {
            this.idx = idx;
            this.num = num;
        }
    }
}

T4. 使数组可以被整除的最少删除次数（6 分）

解题思路

只有 numsDivide 的最大公约数的因数才能整除 numsDivide 中的所有数。

时间复杂度：O(nlogA + nlogn)。其中 A 是 numsDivide 中的最大元素。

参考代码

class Solution {
    public int minOperations(int[] nums, int[] numsDivide) {
        int divideGCD = numsDivide[0];
        for (int i = 1; i < numsDivide.length; i++) {
            divideGCD = getGCD(divideGCD, numsDivide[i]);
        }

        Arrays.sort(nums);
        for (int i = 0; i < nums.length && nums[i] <= divideGCD; i++) {
            if (divideGCD % nums[i] == 0) {
                return i;
            }
        }
        return -1;
    }

    private int getGCD(int num1, int num2) {
        if (num1 == 0) {
            return num2;
        }
        return getGCD(num2 % num1, num1);
    }
}

（全文完）