leetcode weekly contest 332

周赛的题目竟然越来越偏向于思维的题目，第四题会的话就非常简单，不会的会就容易卡住，难得又AK一次。

6354. 找出数组的串联值

给你一个下标从 0 开始的整数数组 nums 。

现定义两个数字的串联是由这两个数值串联起来形成的新数字。

例如，15 和 49 的串联是 1549 。

nums 的 串联值 最初等于 0 。执行下述操作直到 nums 变为空：

如果 nums 中存在不止一个数字，分别选中 nums 中的第一个元素和最后一个元素，将二者串联得到的值加到 nums 的 串联值 上，然后从 nums 中删除第一个和最后一个元素。
如果仅存在一个元素，则将该元素的值加到 nums 的串联值上，然后删除这个元素。

返回执行完所有操作后 nums 的串联值。

示例 1：

输入：nums = [7,52,2,4]
输出：596
解释：在执行任一步操作前，nums 为 [7,52,2,4] ，串联值为 0 。
 - 在第一步操作中：
我们选中第一个元素 7 和最后一个元素 4 。
二者的串联是 74 ，将其加到串联值上，所以串联值等于 74 。
接着我们从 nums 中移除这两个元素，所以 nums 变为 [52,2] 。
 - 在第二步操作中： 
我们选中第一个元素 52 和最后一个元素 2 。 
二者的串联是 522 ，将其加到串联值上，所以串联值等于 596 。
接着我们从 nums 中移除这两个元素，所以 nums 变为空。
由于串联值等于 596 ，所以答案就是 596 。

示例 2：

输入：nums = [5,14,13,8,12]
输出：673
解释：在执行任一步操作前，nums 为 [5,14,13,8,12] ，串联值为 0 。 
- 在第一步操作中： 
我们选中第一个元素 5 和最后一个元素 12 。 
二者的串联是 512 ，将其加到串联值上，所以串联值等于 512 。 
接着我们从 nums 中移除这两个元素，所以 nums 变为 [14,13,8] 。
- 在第二步操作中：
我们选中第一个元素 14 和最后一个元素 8 。
二者的串联是 148 ，将其加到串联值上，所以串联值等于 660 。
接着我们从 nums 中移除这两个元素，所以 nums 变为 [13] 。 
- 在第三步操作中：
nums 只有一个元素，所以我们选中 13 并将其加到串联值上，所以串联值等于 673 。
接着我们从 nums 中移除这个元素，所以 nums 变为空。 
由于串联值等于 673 ，所以答案就是 673 。

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 104

地址

https://leetcode.cn/contest/weekly-contest-332/problems/find-the-array-concatenation-value/

题意

直接模拟

思路

简单题目，我们直接模拟即可，每次对数组的首和尾取出元素然后拼接相加即可；
复杂度分析：

时间复杂度：$O(n + \log u)$，其中 $n$ 为数组的长度，$u$ 为数组中最大的元素。
空间复杂度：$O(1)$。

代码

class Solution {
public:
    long long findTheArrayConcVal(vector<int>& nums) {
        long long ans = 0;
        int n = nums.size();
        for (int i = 0, j = n - 1; i <= j; i++, j--) {
            if (i != j) {
                ans += stoi(to_string(nums[i]) + to_string(nums[j]));
            } else {
                ans += nums[i];
            }
        }
        return ans;
    }
};

6355. 统计公平数对的数目

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。

如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：

0 <= i < j < n，且
lower <= nums[i] + nums[j] <= upper

示例 1：

输入：nums = [0,1,7,4,4,5], lower = 3, upper = 6
输出：6
解释：共计 6 个公平数对：(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和 (1,5) 。

示例 2：

输入：nums = [1,7,9,2,5], lower = 11, upper = 11
输出：1
解释：只有单个公平数对：(2,3) 。

提示：

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

地址

https://leetcode.cn/contest/weekly-contest-332/problems/count-the-number-of-fair-pairs/

题意

二分查找、双指针

思路

典型的二分查找，不过查找范围为左右两个端点，首先对数组进行排序，对于每个元素 $nums[i]$ 我们查找处在区间 $[lower - nums[i],upper-nums[i]]$ 中的元素数目即可。
复杂度分析：

时间复杂度：$O(n \log n)$，其中 $n$ 为数组的长度。每次二分查找需要的时间为 $\log n$。
空间复杂度：$O(\log n)$，主要为排序需要空间。

代码

二分查找

class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        sort(nums.begin(), nums.end());
        long long ans = 0;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            int x = lower_bound(nums.begin(), nums.begin() + i, lower - nums[i]) - nums.begin();
            int y = upper_bound(nums.begin(), nums.begin() + i, upper - nums[i]) - nums.begin();
            ans += y - x;
        }
        return ans;
    }
};

双指针

6356. 子字符串异或查询

给你一个 二进制字符串 s 和一个整数数组 queries ，其中 queries[i] = [firsti, secondi] 。

对于第 i 个查询，找到 s 的 最短子字符串 ，它对应的 十进制值 val 与 firsti 按位异或 得到 secondi ，换言之，val ^ firsti == secondi 。

第 i 个查询的答案是子字符串 [lefti, righti] 的两个端点（下标从 0 开始），如果不存在这样的子字符串，则答案为 [-1, -1] 。如果有多个答案，请你选择 lefti 最小的一个。

请你返回一个数组 ans ，其中 ans[i] = [lefti, righti] 是第 i 个查询的答案。

子字符串 是一个字符串中一段连续非空的字符序列。

示例 1：

输入：s = "101101", queries = [[0,5],[1,2]]
输出：[[0,2],[2,3]]
解释：第一个查询，端点为 [0,2] 的子字符串为 "101" ，对应十进制数字 5 ，且 5 ^ 0 = 5 ，所以第一个查询的答案为 [0,2]。第二个查询中，端点为 [2,3] 的子字符串为 "11" ，对应十进制数字 3 ，且 3 ^ 1 = 2 。所以第二个查询的答案为 [2,3] 。

示例 2：

输入：s = "0101", queries = [[12,8]]
输出：[[-1,-1]]
解释：这个例子中，没有符合查询的答案，所以返回 [-1,-1] 。

示例 3：

输入：s = "1", queries = [[4,5]]
输出：[[0,0]]
解释：这个例子中，端点为 [0,0] 的子字符串对应的十进制值为 1 ，且 1 ^ 4 = 5 。所以答案为 [0,0] 。

提示：

1 <= s.length <= 104
s[i] 要么是 '0' ，要么是 '1' 。
1 <= queries.length <= 105
0 <= firsti, secondi <= 109

地址

https://leetcode.cn/contest/weekly-contest-332/problems/substring-xor-queries/

题意

贪心

思路

题目几个重要的提示:
- val ^ firsti == secondi,此时我们可以通过交换得到 $val = firsti \oplus secondi$,此时我们只需要找到最短的字符串使得其转换后的整数值等于 $val$ 即可；
- 由于整数最多只含有 $32$ 位二进制数，因此我们只需要计算长度小于等于 $32$ 的字符串转换后的数字，并记录其起始位置与结束位置；
- 由于二进制数有前导 $0$ 的存在，因此我们每次从最短的位开始查找即可；
通过以上分析，我们计算出所有长度 $1-32$ 长的子串的值即可，然后查找每个转换后的值等于查询的值的最小区间即可。
复杂度分析

时间复杂度：时间复杂度为 $O(Cn)$，$n$ 表示数组的长度，$C$ 表示给定的常数。
空间复杂度：时间复杂度为 $O(Cn)$。

代码

class Solution {
public:
    vector<vector<int>> substringXorQueries(string s, vector<vector<int>>& queries) {
        int n = s.size();
        int m = queries.size();
        vector<unordered_map<long long, pair<int, int>>> cnt(33);
        for (int i = 0; i < n; i++) {
            long long curr = 0;
            for (int j = 1; j <= 32 && i + j <= n; j++) {
                curr = curr * 2 + s[i + j - 1] - '0';
                if (!cnt[j].count(curr)) {
                    cnt[j][curr] = make_pair(i, i + j - 1);
                }
            }
        }
        vector<vector<int>> ans;
        for (int i = 0; i < m; i++) {
            long long x = queries[i][0] ^ queries[i][1];
            int len = to_string(x).size();
            bool found = false;
            for (int j = len; j <= 32; j++) {
                if (cnt[j].count(x)) {
                    auto [a, b] = cnt[j][x];
                    ans.push_back({a, b});
                    found = true;
                    break;
                }
            }
            if (!found) {
                ans.push_back({-1, -1});
            }
        }
        return ans;
    }
};

6357. 最少得分子序列

给你两个字符串 s 和 t 。

你可以从字符串 t 中删除任意数目的字符。

如果没有从字符串 t 中删除字符，那么得分为 0 ，否则：

令 left 为删除字符中的最小下标。
令 right 为删除字符中的最大下标。

字符串的得分为 right - left + 1 。

请你返回使 t 成为 s 子序列的最小得分。

一个字符串的 子序列 是从原字符串中删除一些字符后（也可以一个也不删除），剩余字符不改变顺序得到的字符串。（比方说 "ace" 是 "***a\***b***c\***d***e\***" 的子序列，但是 "aec" 不是）。

示例 1：

输入：s = "abacaba", t = "bzaa"
输出：1
解释：这个例子中，我们删除下标 1 处的字符 "z" （下标从 0 开始）。
字符串 t 变为 "baa" ，它是字符串 "abacaba" 的子序列，得分为 1 - 1 + 1 = 1 。
1 是能得到的最小得分。

示例 2：

输入：s = "cde", t = "xyz"
输出：3
解释：这个例子中，我们将下标为 0， 1 和 2 处的字符 "x" ，"y" 和 "z" 删除（下标从 0 开始）。
字符串变成 "" ，它是字符串 "cde" 的子序列，得分为 2 - 0 + 1 = 3 。
3 是能得到的最小得分。

提示：

1 <= s.length, t.length <= 105
s 和 t 都只包含小写英文字母。

地址

https://leetcode.cn/contest/weekly-contest-332/problems/subsequence-with-the-minimum-score/

题意

二分查找或者双指针

思路

二分查找：题目典型的问题可以用前后缀加二分的思路来解决:

设当前字符串 $t$ 的前缀 $t[0\cdots j]$ 可以匹配到字符 $s$ 的前 $i$ 个字符，此时我们只需要找到字符串 $s$ 的后缀 $s[(i + 1) \cdots (m-1)]$ 最多可以匹配到 $t$ 的后缀 $t[(j + 1) \cdots (n -1)]$ 的最大长度即可，假设 $s[i \cdots (m-1)]$ 可以匹配 $t[k \cdots (n -1)]$，此时我们只需要删除的字符串为 $t[(j + 1) \cdots (k-1)]$，此时的得分为 $(k - 1) - (j + 1) + 1$。
如果找到两个后缀 $s[(i + 1) \cdots (m-1)]$ 与 $t[k \cdots (n -1)]$ 的最长匹配即可。
- 如果 $t$ 不能完全匹配 $s$ 时，我们可以推出的是后缀 $s[i \cdots (m-1)]$ 最多可以匹配到 $t$ 的第 $j+1$ 个字符，否则一定完全匹配；
- 如果 $s$ 与 $t$ 可以完全匹配，直接返回 $0$；
- 我们利用二分查找直接找到后缀 $s[(i + 1) \cdots (m-1)]$ 与 $t$ 的最长匹配即可；

双指针: 删除 $t$ 的中间部分后，剩余部分是 $t$ 的一个前缀和一个后缀，设前缀与后缀分别为 $t[0 \cdots l]$ 与 $t[r \cdots (n-1)]$，则 $t[0 \cdots l]$ 一定可以匹配 $s[0 \cdots i]$，$t[r \cdots (n-1)]$ 一定可以匹配 $s[(i + 1) \cdots (m-1)]$，此时我们枚举 $i$，分别求出 $s[0 \cdots i]$ 与 $t$ 前缀的最长匹配，$s[(i + 1) \cdots (m-1)]$ 与 $t$ 的后缀的最长匹配，剩余的部分即为去掉的最小部分。
复杂度分析：

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

代码

二分查找：

class Solution {
public:
    int minimumScore(string s, string t) {
        int m = s.size(), n = t.size();
        map<int, int> cnt;
        int ans = n;
        for (int i = m - 1, j = n - 1; i >= 0 ; i--) {
            if (s[i] == t[j]) {
                cnt[i] = j--;            
            }
            if (j < 0) {
                return 0;
            }
            ans = min(ans, j + 1);
        }
        for (int i = 0, j = 0; i < m; i++) {
            if (s[i] == t[j]) {
                j++;
                auto it = cnt.upper_bound(i);
                if (it != cnt.end() && it->second >= j) {
                    ans = min(ans, it->second - j);
                } else {
                    ans = min(ans, n - j);
                }
            }
        }
        return ans;
    }
};

双指针:

class Solution {
public:
    int minimumScore(string s, string t) {
        int m = s.size(), n = t.size();
        vector<int> prefix(m + 1), suffix(m + 1);
        for (int i = 0, j = 0; i < m; i++) {
            if (j < n && s[i] == t[j]) {
                j++;
            }
            prefix[i] = j;
        }
        if (prefix[m - 1] == n) {
            return 0;
        }
        for (int i = m - 1, j = n - 1; i >= 0; i--) {
            if (j >= 0 && s[i] == t[j]) {
                j--;
            }
            suffix[i] = n - j - 1;
        }
        int ans = min(n - prefix[m - 1], n - suffix[0]);
        for (int i = 0; i < m; i++) {
            ans = min(ans, n - prefix[i] - suffix[i + 1]);
        }
        return ans;
    }
};

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

关注我的博客: http://whistle-wind.com/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 力扣周赛题解

← leetcode weekly contest 331 leetcode biweekly contest 98 →

扫描二维码，分享此文章