Skip to content

第 332 场周赛

比赛链接

Date: 2023-02-12

A 找出数组的串联值

模拟，只要熟练掌握 API 即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    using ll = long long;
    long long findTheArrayConcVal(vector<int>& nums) {
        ll res = 0;
        for (int i = 0, j = nums.size() - 1; i <= j; i++, j--) {
            if (i == j) {
                res += nums[i];
            } else {
                auto s = to_string(nums[i]) + to_string(nums[j]);
                res += stoi(s);
            }
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def findTheArrayConcVal(self, nums: List[int]) -> int:
        i, j = 0, len(nums) - 1
        res = 0
        while i <= j:
            if i == j:
                res += nums[i]
            else:
                res += int(str(nums[i]) + str(nums[j]))
            i += 1
            j -= 1
        return res

复杂度分析

  • 时间复杂度：\(O(n)\)
  • 空间复杂度：\(O(1)\)

B 统计公平数对的数目

首先可以把它看做是无序对，然后求出总数之后除以 2 即可得到有序对的数量。

枚举其中一个数字 \(\textit{nums}[i]\)，然后只需求出符合要求的 \(\textit{nums}[j]\) 的数量：\(\textit{lower} - \textit{nums}[i] \le \textit{nums}[j] \le \textit{upper} - \textit{nums}[i]\)。

通过二分，找到最小的 \(x\) 满足 \(x \ge \textit{lower} - \textit{nums}[i]\)，在找到最小的 \(y\) 满足 \(y \gt \textit{upper} - \textit{nums}[i]\)。\(y\) 的位置减去 \(x\) 的位置即可得到与 \(\textit{nums}[i]\) 配对的数量。

注意，这里面可以包含 \(\textit{nums}[i]\) 自己，所以如果 \(\textit{lower} - \textit{nums}[i] \le \textit{nums}[i] \le \textit{upper} - \textit{nums}[i]\)。此时答案需要减去一。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    using ll = long long;
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        sort(nums.begin(), nums.end());
        ll res = 0;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            res += upper_bound(nums.begin(), nums.end(), upper - nums[i]) - lower_bound(nums.begin(), nums.end(), lower - nums[i]);
            if (2 * nums[i] >= lower && 2 * nums[i] <= upper) {
                res--;
            }
        }
        return res / 2;
    }
};

复杂度分析

  • 时间复杂度：\(O(n\log n)\)
  • 空间复杂度：\(O(1)\)

C 子字符串异或查询

由于题目的数字限定在 \(10^9\) 范围内，所以二进制长度不会超过 \(30\)，我们只需预处理出每一个区间长度不超过 \(30\) 的区间，将它们作为候选答案放在一个哈希表中。

注意按照左端点从小到大枚举，可以天然避免判断多个答案左端点相同的情况，只需考虑选择最短的即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<vector<int>> substringXorQueries(string s, vector<vector<int>>& queries) {
        unordered_map<int, pair<int, int>> mp;
        for (int i = 0; i < s.size(); i++) {
            int x = 0;
            for (int j = i; j < i + 30 && j < s.size(); j++) {
                x = x * 2 + (s[j] - '0');
                if (!mp.count(x)) {
                    mp[x] = make_pair(i, j);
                } else if ((j - i) < (mp[x].second - mp[x].first)) {
                    mp[x] = make_pair(i, j);
                }
            }
        }
        vector<vector<int>> res;
        for (auto &v : queries) {
            int x = v[0], y = v[1];
            if (mp.count(x ^ y)) {
                res.push_back({mp[x ^ y].first, mp[x ^ y].second});
            } else {
                res.push_back({-1, -1});
            }
        }
        return res;
    }
};

复杂度分析

  • 时间复杂度：\(O(30n)\)。
  • 空间复杂度：\(O(30n)\)。

D 最少得分子序列

思路很简单，因为考虑的删除字母下标最大值与最小值的差，所以我们只需要考虑两边的字符串能否构成 \(s\) 的子序列即可。

因此，预处理前缀 \(l\) 和后缀 \(r\) 数组，\(l[i]\) 表示 \(t[0...i]\) 最短对应到 \(s[0...l[i]]\) 的子序列。

然后双指针遍历，取 \(r - l + 1\) 最小的作为答案即可。注意边界情况的处理。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int minimumScore(string s, string t) {
        int n = s.size(), m = t.size();
        vector<int> l(m), r(m);
        int res = m;
        for (int i = 0, j = 0; i < m; i++) {
            while (j < n && s[j] != t[i]) j++;
            if (j < n) res = min(res, m - i - 1);
            l[i] = j;
            j++;
        }

        for (int i = m - 1, j = n - 1; i >= 0; i--) {
            while (j >= 0 && s[j] != t[i]) j--;
            if (j >= 0) res = min(res, i);
            r[i] = j;
            j--;
        }

        for (int i = 0, j = 1; i < m; i++) {
            while (j < m && (l[i] >= r[j] || j <= i)) j++;
            if (l[i] < n && (j == m || r[j] > l[i])) {
                res = min(res, j - i - 1);
            }
        }
        return res;
    }
};

复杂度分析

  • 时间复杂度：\(O(n)\)
  • 空间复杂度：\(O(n)\)
本文访问 次