Leetcode 第 399 场周赛题解

题目1：3162. 优质数对的总数 I

思路

暴力。

代码

/*
 * @lc app=leetcode.cn id=3162 lang=cpp
 *
 * [3162] 优质数对的总数 I
 */

// @lc code=start
class Solution
{
public:
    int numberOfPairs(vector<int> &nums1, vector<int> &nums2, int k)
    {
        int count = 0;
        for (int i = 0; i < nums1.size(); i++)
            for (int j = 0; j < nums2.size(); j++)
                if (nums1[i] % (nums2[j] * k) == 0)
                    count++;
        return count;
    }
};
// @lc code=end

复杂度分析

时间复杂度：O(n*m)，其中 n 是数组 nums1 的长度，m 是数组 nums2 的长度。

空间复杂度：O(1)。

题目2：3163. 压缩字符串 III

思路

分组循环。

每次循环都能得到 word 的单字符前缀，题目要求我们对前缀每 9 个字符就切分一次，按规则构造 comp 字符串即可。

代码

/*
 * @lc app=leetcode.cn id=3163 lang=cpp
 *
 * [3163] 压缩字符串 III
 */

// @lc code=start
class Solution
{
public:
    string compressedString(string word)
    {
        string comp;
        // 分组循环
        int i = 0;
        while (i < word.length())
        {
            int j = i + 1;
            while (j < word.length() && word[i] == word[j])
                j++;
            int len = j - i;
            for (int k = 0; k < len / 9; k++)
            {
                comp.push_back('9');
                comp.push_back(word[i]);
            }
            if (len % 9)
            {
                comp.push_back(len % 9 + '0');
                comp.push_back(word[i]);
            }
            i = j;
        }
        return comp;
    }
};
// @lc code=end

复杂度分析

时间复杂度：O(n)，其中 n 是字符串 word 的长度。

空间复杂度：O(1)。

题目3：3164. 优质数对的总数 II

思路

遍历 nums1，统计所有元素的因子个数，记录到哈希表 cnt 中。

遍历 nums2，那么有 cnt[nums2[i]*k] 个数可以被 nums2[i]*k 整除，加入答案。

代码

/*
 * @lc app=leetcode.cn id=3164 lang=cpp
 *
 * [3164] 优质数对的总数 II
 */

// @lc code=start
class Solution
{
public:
    long long numberOfPairs(vector<int> &nums1, vector<int> &nums2, int k)
    {
        unordered_map<int, int> cnt; // 统计因子的出现次数
        for (int &x : nums1)
            for (int i = 1; i * i <= x; i++)
                if (x % i == 0)
                {
                    cnt[i]++;
                    if (i * i < x)
                        cnt[x / i]++;
                }

        long long ans = 0LL;
        for (int &x : nums2)
            if (cnt.contains(x * k))
                ans += cnt[x * k];
        return ans;
    }
};
// @lc code=end

复杂度分析

时间复杂度：O(n*sqrt(U)+m)，其中 n 是 nums1 的长度，m 是 nums2 的长度，U=max⁡(nums1)。

空间复杂度：O(U)，其中 U=max⁡(nums1)。

题目4：3165. 不包含相邻元素的子序列的最大和

思路

分治思想 + 线段树。

题解：分治思想+线段树（Python/Java/C++/Go）

代码

/*
 * @lc app=leetcode.cn id=3165 lang=cpp
 *
 * [3165] 不包含相邻元素的子序列的最大和
 */

// @lc code=start
class Solution
{
    // 4 个数分别保存 f00, f01, f10, f11
    vector<array<unsigned int, 4>> t;

    void maintain(int o)
    {
        auto &a = t[o * 2], b = t[o * 2 + 1];
        t[o] = {
            max(a[0] + b[2], a[1] + b[0]),
            max(a[0] + b[3], a[1] + b[1]),
            max(a[2] + b[2], a[3] + b[0]),
            max(a[2] + b[3], a[3] + b[1]),
        };
    }

    // 用 nums 初始化线段树
    void build(vector<int> &nums, int o, int l, int r)
    {
        if (l == r)
        {
            t[o][3] = max(nums[l], 0);
            return;
        }
        int m = (l + r) / 2;
        build(nums, o * 2, l, m);
        build(nums, o * 2 + 1, m + 1, r);
        maintain(o);
    };

    // 把 nums[i] 改成 val
    void update(int o, int l, int r, int i, int val)
    {
        if (l == r)
        {
            t[o][3] = max(val, 0);
            return;
        }
        int m = (l + r) / 2;
        if (i <= m)
        {
            update(o * 2, l, m, i, val);
        }
        else
        {
            update(o * 2 + 1, m + 1, r, i, val);
        }
        maintain(o);
    };

public:
    int maximumSumSubsequence(vector<int> &nums, vector<vector<int>> &queries)
    {
        int n = nums.size();
        t.resize(2 << (32 - __builtin_clz(n)));
        build(nums, 1, 0, n - 1);
        long long ans = 0;
        for (auto &q : queries)
        {
            update(1, 0, n - 1, q[0], q[1]);
            ans += t[1][3]; // 注意 f11 没有任何限制，也就是整个数组的打家劫舍
        }
        return ans % 1'000'000'007;
    }
};

// @lc code=end

复杂度分析