leetcode biweekly contest 517

leetcode contest 517

本周最后的T4竟然出了不少问题，测试用例出了不少问题。

Q1. 判断 ASCII 值回文

给你一个由小写英文字母组成的字符串 s。

将 s 中的每个字符替换为其 ASCII 值对应的 8 位二进制表示，包括前导零，并保持字符原有顺序，从而构造一个二进制字符串。

如果得到的二进制字符串是一个 回文串 ，则返回 true；否则返回 false。

二进制字符串 是指仅由字符 '0' 和 '1' 组成的字符串。

回文串 是指正着读和反着读都相同的字符串。

示例 1：

输入： s = “ff”

输出： true

解释：

字符 f 的 ASCII 值为 102，其 8 位二进制表示为 01100110。
因此，得到的二进制字符串为 0110011001100110。
由于该二进制字符串是一个 回文串 ，因此输出为 true。

示例 2：

输入： s = “leet”

输出： false

解释：

字符 l、e、e 和 t 的 ASCII 值分别为 108、101、101 和 116 。
它们对应的 8 位二进制表示分别为 01101100、01100101、01100101 和 01110100。
因此，得到的二进制字符串为 01101100011001010110010101110100。
由于该二进制字符串不是一个 回文串 ，因此输出为 false。

提示：

1 <= s.length <= 100
s 仅由小写英文字母组成。

地址

https://leetcode.cn/contest/weekly-contest-516/problems/check-ascii-palindromic/description/

题意

模拟

思路

直接模拟并生成字符串，然后判断该字符串是否为回文即可。
复杂度分析：

时间复杂度：$O(n)$。
空间复杂度：$O(C)$。

代码

class Solution {
public:
    bool isPalindromic(string s) {
        auto get = [](char c) -> string {
            int x = c;
            string res;
            for (int i = 0; i < 8; i++) {
                if (x & 1) {
                    res.push_back('1');
                } else {
                    res.push_back('0');
                }
                x /= 2;
            }
            reverse(res.begin(), res.end());

            return res;
        };

        string str;
        for (char c : s) {
            str += get(c);
        }
        string rstr = str;
        reverse(rstr.begin(), rstr.end());

        return str == rstr;
    }
};

Q2. 找到所有数组中消失的数字 II

给你一个整数数组 nums，以及两个整数 lower 和 upper。

如果一个整数位于区间 [lower, upper] 内（包含两个端点），但没有出现在 nums 中，则称其为 缺失整数 。

返回一个二维整数数组，其中每个元素的形式为 [start, end]，表示一段由缺失整数组成的 连续区间 。请按递增顺序返回这些区间。如果不存在缺失整数，则返回空数组。

注意：连续的缺失整数应合并为同一个区间。

示例 1：

输入： nums = [3,9,7], lower = 1, upper = 12

输出： [[1,2],[4,6],[8,8],[10,12]]

解释：

缺失整数为 [1, 2, 4, 5, 6, 8, 10, 11, 12]。
将这些缺失整数合并成最少数量的连续区间后，得到 [1, 2]、[4, 6]、[8, 8] 和 [10, 12]。
因此，答案为 [[1, 2], [4, 6], [8, 8], [10, 12]]。

示例 2：

输入： nums = [1,1], lower = 5, upper = 7

输出： [[5,7]]

解释：

缺失整数为 [5, 6, 7]。
将这些缺失整数合并成最少数量的连续区间后，得到 [5, 7]。
因此，答案为 [[5, 7]]。

示例 3：

输入： nums = [2,3,5], lower = 2, upper = 3

输出： []

解释：

不存在缺失整数。
因此，答案为 []。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 105
1 <= lower <= upper <= 105

地址

https://leetcode.cn/contest/weekly-contest-516/problems/find-all-numbers-disappeared-in-an-array-ii/description/

题意

排序

思路

我们将给定的数组按照从小到大进行排序即可。$j$ 从 $lower$ 到 $upper$ 开始枚举，遍历每个数 $nums[i]$, 此时我们遇到三种情况：
- 如果当前 $nums[i]$ 大于 $upper$，此时即中断遍历；
- 如果当前 $nums[i]$ 小于 $j$，此时没有合法区间；
- 如果当前 $nums[i]$ 等于 $j$，此时没有合法区间，此时更新 $j = j + 1$；
- 如果当前 $nums[i]$ 大于 $j$，此时存在合法区间 $[j, \min(nums[i] - 1, upper)]$，此时更新 $j = nums[i] + 1$；
- 当遍历完成后，如果 $j$ 仍然小于等于 $upper$，此时存在的区间为 $[j,upper]$;
复杂度分析：

时间复杂度：$O(n \log n)$，其中 $n$ 表示数组的长度。
空间复杂度：$O(1)$；

代码

class Solution {
public:
    vector<vector<int>> findDisappearedNumbers(vector<int>& nums, int lower, int upper) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> res;
        int j = lower;
        for (int i = 0; i < n; i++) {
            if (nums[i] > upper) {
                break;
            }
            if (nums[i] < j) {
                continue;
            } else if (nums[i] == j) {
                j++;
            } else {
                res.push_back({j, min(nums[i] - 1, upper)});
                j = nums[i] + 1;
            }
        }
        if (j <= upper) {
            res.push_back({j, upper});
        }

        return res;
    }
};

Q3. 至多 K 个不同质因数集合的最长子数组

给你一个由正整数组成的整数数组 nums 和一个整数 k。

一个 子数组 的 质因数集合 是其所有元素的不同**质 因数的 并集**。

返回 最长子数组的长度 ，其质因数集合中包含的不同质因子数量不超过 k 。如果不存在这样的子数组，则返回 0。

子数组 是数组中一段连续非空的元素序列。

质数是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。

示例 1：

输入： nums = [7,6,10,12,11], k = 3

输出： 3

解释：

子数组 [6, 10, 12]：

6 的不同质因数是 {2, 3}。
10 的不同质因数是 {2, 5}。
12 的不同质因数是 {2, 3}。
这些集合的并集是 {2, 3, 5}，包含 3 个不同质因数。

没有更长的子数组满足条件。因此，答案是 3。

示例 2：

输入： nums = [4,6,9,18], k = 4

输出： 4

解释：

整个数组 [4, 6, 9, 18]：

4 的不同质因数是 {2}。
6 的不同质因数是 {2, 3}。
9 的不同质因数是 {3}。
18 的不同质因数是 {2, 3}。
这些集合的并集是 {2, 3}，包含 2 个不同质因数。

因为 2 <= 4，所以整个数组是有效的。因此，答案是 4。

示例 3：

输入： nums = [6,10,15], k = 2

输出： 1

解释：

所有长度至少为 2 的子数组的质因数集合均为 {2, 3, 5}，包含 3 个不同质因数。

因为 3 > 2，只有长度为 1 的子数组是有效的。因此，答案是 1。

提示：

1 <= nums.length <= 105
2 <= nums[i] <= 105
1 <= k <= 104

地址

https://leetcode.cn/contest/weekly-contest-516/problems/longest-subarray-with-at-most-k-distinct-prime-factors/description/

题意

滑动窗口

思路

题目为经典的滑动窗口。首先我们需要求出每个元素含有的质因子个数，对于给定的值 $x$，求质因子的算法需要时间 $O(\sqrt{x})$，接着我们使用经典的滑动窗口，$j$ 指向滑动窗口左侧，$i$ 指向滑动窗口右侧，同时利用哈希表统计窗口内不同质因子的数目，每次移动窗口的右侧，如果窗口内质因子数目大于 $k$,此时则移动窗口的左侧，直到素因子的数目小于等于 $k$；
复杂度分析：

时间复杂度：$𝑂(n \log M)$，其中 $n$ 表示给定数组的长度，$M$ 表示给定数组中的最大元素；
空间复杂度：$𝑂(n \log M)$,其中 $n$ 表示给定数组的长度，$M$ 表示给定数组中的最大元素；

代码

class Solution {
public:
    int longestSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<int>> factor(n);
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            for (int j = 2; j * j <= x; j++) {
                if ((x % j) == 0) {
                    factor[i].emplace_back(j);
                    while ((x % j) == 0) {
                        x /= j;
                    }
                }
            }
            if (x > 1) {
                factor[i].emplace_back(x);
            }
        }
        
        unordered_map<int, int> cnt;
        int res = 0;
        
        for (int i = 0, j = 0; i < n; i++) {
            for (int x : factor[i]) {
                cnt[x]++;
            }
            while (j <= i && cnt.size() > k) {
                for (int x : factor[j]) {
                    cnt[x]--;
                    if (cnt[x] == 0) {
                        cnt.erase(x);
                    }
                }
                j++;
            }
            res = max(res, i - j + 1);
        }
      

        return res;
    }
};

Q4. 有效 K 个不同元素子数组 I

给定一个整数数组 nums 和一个整数 k。

同时给定一个二维整数数组 queries，其中 queries[i] = [li, ri] 表示子数组 nums[li..ri]。

对于每个查询，如果子数组 nums[li..ri] 满足以下条件，则认为该 子数组 是 有效的：

它恰好包含 k 个不同的数字，并且
子数组中每个数字出现的频率都是偶数。

返回一个布尔数组 ans，其中如果 nums[li..ri] 是 有效的，则 ans[i] 为 true，否则为 false。

示例 1：

输入： nums = [1,2,2,1], k = 2, queries = [[0,1],[0,3],[1,2]]

输出： [false,true,false]

解释：

`i`	`[li, ri]`	子数组	不同的数字	频率	有效性检查
0	[0, 1]	[1, 2]	{1, 2} → 2	{1: 1, 2: 1}	`false`：元素出现的次数不是偶数。
1	[0, 3]	[1, 2, 2, 1]	{1, 2} → 2	{1: 2, 2: 2}	`true`：恰好有 `k = 2` 个不同的元素，并且所有元素出现的次数都是偶数。
2	[1, 2]	[2, 2]	{2} → 1	{2: 2}	`false`：不同元素的数量小于 `k = 2`。

因此，ans = [false, true, false]。

示例 2：

输入： nums = [3,3,3], k = 1, queries = [[1,2],[0,2]]

输出： [true,false]

解释：

`i`	`[li, ri]`	子数组	不同的数字	频率	有效性检查
0	[1, 2]	[3, 3]	{3} → 1	{3: 2}	`true`：恰好有 `k = 1` 个不同的元素，并且该元素出现的次数为偶数。
1	[0, 2]	[3, 3, 3]	{3} → 1	{3: 3}	`false`：数字 3 出现的次数不是偶数。

因此，ans = [true, false]。

提示：

2 <= n == nums.length <= 105
1 <= nums[i] <= 105
1 <= k <= n
1 <= queries.length <= 105
queries[i] == [li, ri]
0 <= li < ri <= n - 1

地址

https://leetcode.cn/contest/weekly-contest-516/problems/valid-k-unique-subarrays-i/description/

题意

线段树

思路

我们看到范围查询就会想到使用线段，题目关键在于两点如何查询：
- 范围 $[l,r]$ 内恰好包含 $k$ 个不同元素；
  - 我们可以用滑动窗口确定 $[l,r]$ 是否恰好包含 $k$ 个不同元素，我们刚好可以用滑动窗口确定每个索引 $i$，左侧起点为 $left[i]$ 使得 $[left[i],i]$ 窗口内恰好有 $k$ 个不同元素，很容易求出；
- 范围 $[l,r]$ 内包含的偶数个数元素的数目；
  - 此时我们直到一个数经过偶数次异或一定为 $0$，此时我们通过前缀和很容易求出区间 $[l,r]$ 是否满足异或是否为 $0$；
复杂度分析：

时间复杂度：$𝑂(n + q)$，其中 $n$ 表示给定的数组的长度，$q$ 表示查询次数；
空间复杂度：$𝑂(n)$，$n$ 表示给定数组的长度；

代码

class Solution {
    static inline mt19937_64 rng = mt19937_64(chrono::steady_clock::now().time_since_epoch().count());

public:
    vector<bool> validSubarrays(vector<int>& nums, int k, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<uint64_t> sum(n + 1);
        unordered_map<int, uint64_t> hash;
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            // 把 nums[i] 映射成一个随机的 uint64_t
            if (!hash.contains(x)) {
                hash[x] = rng();
            }
            sum[i + 1] = sum[i] ^ hash[x];
        }

        auto calc_left = [&](int k) -> vector<int> {
            vector<int> lefts(n);
            unordered_map<int, int> cnt;
            int l = 0;
            for (int i = 0; i < n; i++) {
                cnt[nums[i]]++;
                while (cnt.size() >= k) {
                    auto it = cnt.find(nums[l]);
                    if (--it->second == 0) {
                        cnt.erase(it); // 保证 cnt.size() 是窗口内的不同元素个数
                    }
                    l++;
                }
                lefts[i] = l;
            }
            return lefts;
        };

        auto l1 = calc_left(k + 1);
        auto l2 = calc_left(k);

        vector<bool> ans(queries.size());
        for (int i = 0; i < queries.size(); i++) {
            auto& q = queries[i];
            int l = q[0], r = q[1];
            ans[i] = sum[r + 1] == sum[l] && l1[r] <= l && l < l2[r];
        }
        return ans;
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: https://mike-box.github.io/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 哪些奋斗者

力扣周赛

#题解 #力扣周赛赛

leetcode biweekly contest 517

http://example.com/2026/09/08/力扣周赛题解/235/

Author

Mike Meng

Posted on

September 8, 2026

Licensed under

leetcode biweekly contest 516 Previous

leetcode biweekly contest 517 Next