力扣第 399 场周赛

比赛时间 2024-05-26。本场周赛国服共 173 人 AK。

可惜 T4 交了错解。。为什么 java 12058ms 能过啊。。

T1. 优质数对的总数 I（3 分）

解题思路

见 T3。

参考代码

略。

T2. 压缩字符串 III（4 分）

解题思路

分组循环。

时间复杂度：O(n^2)。

参考代码

class Solution {
    public String compressedString(String word) {
        int n = word.length();
        char[] s = word.toCharArray();
        int i = 0;
        StringBuilder ans = new StringBuilder();
        while (i < n) {
            // 分组循环
            int st = i;
            for (i++; i < n && i - st < 9 && s[i] == s[st]; i++) {
            }
            int cnt = i - st;
            ans.append(cnt).append(s[st]);
        }
        return ans.toString();
    }
}

T3. 优质数对的总数 II（5 分）

解题思路

统计 nums1 的因子出现次数（注意去重），再看这些因子在 nums2 中是否出现。

时间复杂度：O(n * sqrt(U/k) + m)。

参考代码

class Solution {
    public long numberOfPairs(int[] nums1, int[] nums2, int k) {
        Map<Integer, Integer> factorCntMap = new HashMap<>();
        for (int v : nums1) {
            if (v % k != 0) continue;
            int n = v / k;
            for (int i = 1; i * i <= n; i++) {
                if (n % i == 0) {
                    factorCntMap.merge(i, 1, Integer::sum);
                    if (i != n / i) {
                        factorCntMap.merge(n / i, 1, Integer::sum);
                    }
                }
            }
        }
        long ans = 0;
        for (int v : nums2) {
            if (factorCntMap.containsKey(v)) {
                ans += factorCntMap.get(v);
            }
        }
        return ans;
    }
}

T4. 不包含相邻元素的子序列的最大和（8 分）

解题思路

赛时是暴力 DP + 剪枝过的。

这题可用看作动态版的“打家劫舍”：

分治思想 + 线段树。

• f00(a)：在不选 a 的第一个数和最后一个数的情况下，计算打家劫舍的答案；
• f01(a)：在不选 a 的第一个数的情况下，计算打家劫舍的答案（最后一个数可选可不选）；
• f10(a)：在不选 a 的最后一个数的情况下，计算打家劫舍的答案（第一个数可选可不选）；
• f11(a)：计算打家劫舍的答案（第一个数可选可不选，最后一个数可选可不选）；
• p = a[:len(a)//2]
• q = a[len(a)//2:]
• f11(a) = max(f10(p) + f11(q), f11(p) + f01(q))
• 递归边界 f11(a) = max(a[0], 0)

时间复杂度：O((n + q) logn)。

参考代码

class Solution {
    private static final int MOD = (int) (1e9 + 7);

    public int maximumSumSubsequence(int[] nums, int[][] queries) {
        long ans = 0;
        SegmentTree seg = new SegmentTree(nums);
        for (int[] p : queries) {
            int pos = p[0], x = p[1];
            seg.update(pos, x);
            ans += seg.tree[1][3]; // 注意 f11 没有任何限制，也就是整个数组的打家劫舍
        }
        return (int) (ans % MOD);
    }

    static class SegmentTree {
        int n;
        // 4 个数分别保存 f00, f01, f10, f11
        long[][] tree;
        int[] nums;

        public SegmentTree(int[] nums) {
            n = nums.length;
            tree = new long[4 * n][4];
            this.nums = nums;
            build(1, 0, n - 1);
        }

        void pushUp(int p) {
            long[] a = tree[p * 2], b = tree[p * 2 + 1];
            tree[p] = new long[]{
                    Math.max(a[0] + b[2], a[1] + b[0]),
                    Math.max(a[0] + b[3], a[1] + b[1]),
                    Math.max(a[2] + b[2], a[3] + b[0]),
                    Math.max(a[2] + b[3], a[3] + b[1])
            };
        }

        void build(int p, int l, int r) {
            if (l == r) {
                tree[p][3] = Math.max(0, nums[l]);
                return;
            }
            int mid = l + (r - l) / 2;
            build(p << 1, l, mid);
            build(p << 1 | 1, mid + 1, r);
            pushUp(p);
        }

        void update(int i, int val) {
            update(1, 0, n - 1, i, val);
        }

        void update(int p, int l, int r, int i, int val) {
            if (l == r) {
                tree[p][3] = Math.max(0, val);
                return;
            }
            int mid = l + (r - l) / 2;
            if (i <= mid) update(p << 1, l, mid, i, val);
            else update(p << 1 | 1, mid + 1, r, i, val);
            pushUp(p);
        }
    }
}

（全文完）