力扣第460场周赛

https://leetcode.cn/contest/weekly-contest-460/

第一题

链接

3627. 中位数之和的最大值

题解

翻译一下题意：给一个 nums 数组，可以正好分成若干个元素个数为 3 的子数组，将子数组升序排序，求每个子数组中间元素相加之和的最大值。

看一下数据范围，nums.length 在 10^6 左右，所以大概要用 O(nlogn) 内的算法，可以先排除暴力枚举了。

我是从子数组的角度下手的，按照升序排序再选中间元素，说明对于一个组合，我们总是只能选择第二大的元素，而第一大的元素总是无法选择的，因为组合一个子数组后，需要删除初始数组 3 个元素。

可以得到这样一个贪心策略：

对初始数组升序排序，从大到小，两个元素一个组合，组合中较大元素不能选，较小元素为能选择的最大元素。依次相加 nums.length / 3 个较小元素，得到中位数之和的最大值。

代码

public long maximumMedianSum(int[] nums) {
    Arrays.sort(nums);
    int n = nums.length / 3;
    long res = 0;
    for (int i = 1; i <= n; i++) {
        res += nums[nums.length - i * 2];
    }
    return res;
}

第二题

链接

3628. 插入一个字母的最大子序列数

题解

枚举插入，再统计子序列个数，求最大值。

有两个需要优化掉暴力的点：

第一点：'L' 插入开头总是最优解，'T' 插入结尾总是最优解。

'C' 插入一个位置 i 所增加的子序列数为：i 前 L 个数 乘 i 后 T 个数，所以可以预处理求出最佳索引。

第二点：对 LCT 子序列的计数要将 O(n^3) 优化到 O(n)，用前缀计数的技巧，见下方 clct 函数。

代码

public long numOfSubsequences(String s) {
    // 长度为1的直接返回
    if (s.length() < 2)
        return 0;
    int n = s.length();
    int[] l = new int[n + 1], t = new int[n + 1];

    for (int i = 1; i <= n; i++) {
        l[i] = l[i - 1];
        if (s.charAt(i - 1) == 'L')
            l[i]++;
    }

    for (int i = n - 1; i >= 0; i--) {
        t[i] = t[i + 1];
        if (s.charAt(i) == 'T')
            t[i]++;
    }

    long max = 0;
    int idx = -1;
    for (int i = 0; i <= n; i++) {
        long tmp = (long) l[i] * t[i];
        if (tmp > max) {
            max = tmp;
            idx = i;
        }
    }

    long res = clct('L' + s);
    // 说明 L 和 T 中少一个，不可能插入 C
    if (idx != -1) {
        res = Math.max(res, clct(s.substring(0, idx) + 'C' + s.substring(idx)));
    }
    res = Math.max(res, clct(s + 'T'));
    return res;
}

// 子序列统计常用技巧
private long clct(String s) {
    long l = 0, lc = 0, lct = 0;
    for (char c : s.toCharArray()) {
        if (c == 'L') {
            l++;
        } else if (c == 'C') {
            lc += l;
        } else if (c == 'T') {
            lct += lc;
        }
    }
    return lct;
}

第三题

链接

3629. 通过质数传送到达终点的最少跳跃次数

题解

总结题意：给一个长度为 n 的整数数组 nums，下标 0 为起点，下标 n - 1 为终点。

假设此时在下标 i 处，移动方式有两个：

• 左右移动：移动到 i - 1 或 i + 1 处；
• 质数传送：nums[i] 为质数，可传送到以 nums[i] 为质因数的元素的位置。

求最小移动次数。

前半部分埃式筛法和分解质因数可以看 质数筛 和 试除法分解质因数，接下来可以看作有向无权图的问题。

数组元素作为节点，节点的出度有三种：分别是左移动，右移动，质数传送。

质数判断和找边都需要通过查表优化时间才能过。

然后在图上 BFS 找最短路径，需要注意标记访问，避免死循环。

代码

private static final int MAX = 1_000_001;
private static final boolean[] isPrime = new boolean[MAX];

// 预处理: 埃式筛法
static {
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i < MAX; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < MAX; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

// 试除法分解质因数(无重复)
public List<Integer> getPrimeList(int num) {
    List<Integer> factors = new ArrayList<>();
    for (int prime = 2; prime < isPrime.length; prime++) {
        if (!isPrime[prime]) continue;
        if (prime * prime > num) break;
        if (num % prime == 0) {
            factors.add(prime);
            while (num % prime == 0) num /= prime;
        }
    }
    if (num > 1) factors.add(num);
    return factors;
}

// 提交方法
public int minJumps(int[] nums) {
    int n = nums.length;
    if (n < 2) return 0;

    // 预处理表，用于质数跳跃时 O(1) 找到路径
    Map<Integer, List<Integer>> pLs = new HashMap<>();
    for (int i = 0; i < n; i++) {
        int num = nums[i];
        if (num < 2) continue;
        List<Integer> fs = getPrimeList(num);
        for (Integer f : fs) {
            pLs.computeIfAbsent(f, k -> new ArrayList<>()).add(i);
        }
        pLs.computeIfAbsent(num, k -> new ArrayList<>()).add(i);
    }

    // 先访问到的一定是最短路径，避免成环无限循环
    boolean[] v = new boolean[n];
    Queue<int[]> q = new LinkedList<>();

    // 设计节点携带信息: 原数组索引和当前步数
    q.offer(new int[]{0, 0});
    v[0] = true;

    // BFS 框架代码
    while (!q.isEmpty()) {
        int[] curr = q.poll();
        int index = curr[0], steps = curr[1];

        // 向前一步
        if (index + 1 < n && !v[index + 1]) {
            if (index + 1 == n - 1) return steps + 1;
            v[index + 1] = true;
            q.offer(new int[]{index + 1, steps + 1});
        }
        // 向后一步
        if (index - 1 >= 0 && !v[index - 1]) {
            v[index - 1] = true;
            q.offer(new int[]{index - 1, steps + 1});
        }
        // 质数传送
        int p = nums[index];
        if (p > 1 && p <= MAX && isPrime[p]) {
            List<Integer> pL = pLs.getOrDefault(p, new ArrayList<>());
            for (int i : pL) {
                if (!v[i] && i != index) {
                    if (i == n - 1) return steps + 1;
                    v[i] = true;
                    q.offer(new int[]{i, steps + 1});
                }
            }
        }
    }

    return -1;
}

代码参考: 力扣题解

第四题

链接

3630. 划分数组得到最大异或运算和与运算之和

题解

看不懂，没招了

代码

前面的区域，以后再来探索吧。