Decade
Leetcode 332场周赛
Zhongjun Qiu 元婴开发者
  2025-02-12 15:08:33   2025-04-29 21:27:59    2.1k Words  9 Mins  

Q1 6354. 找出数组的串联值 - 力扣（Leetcode） [Easy] 题解

Q2 6355. 统计公平数对的数目 - 力扣（LeetCode） [Medium] 题解

Q3 6356. 子字符串异或查询 - 力扣（Leetcode） [Medium] 题解

Q4 6357. 最少得分子序列 - 力扣（Leetcode） [Hard] 题解

Q1

6354. 找出数组的串联值 - 力扣（Leetcode）

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

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

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

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

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

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

示例 1：

1
2
输入：nums = [7,52,2,4]
输出：596

示例 2：

1
2
输入：nums = [5,14,13,8,12]
输出：673

提示：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 10^4

思路

​ 遍历模拟

代码

1
2
3
4
5
6
7
8
9
10
class Solution:
    def findTheArrayConcVal(self, nums: List[int]) -> int:
        ans = 0
        n = len(nums)
        for i in range(n//2):
            tp = str(nums[i])+str(nums[n-i-1])
            ans += int(tp)
        if n%2 == 1:
            ans += nums[n//2]
        return ans

复杂度分析

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

Q2

6355. 统计公平数对的数目 - 力扣（LeetCode）

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

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

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

示例 1：

1
2
3
输入：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：

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

提示：

  • 1 <= nums.length <= 10^5
  • nums.length == n
  • -109 <= nums[i] <= 10^9
  • -109 <= lower <= upper <= 10^9

思路

😅😅😅

最初想法就是，顺序遍历，对于遍历到的nums[i], 找到前面在 [lower − nums[i], upper − nums[i]]范围中的数：离散化+树状数组。

但，这是Q2。。。随即又想到了SortedList，但不知道有没有这种数据结构。（得单独写个API使用文档👨‍🦲）

写完第三题，回来看才想到排序。。。因为最后要求的是数对数量，和元素顺序没有关系。

这样就不用SortedList了，直接排序后两次二分就行了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public long countFairPairs(int[] nums, int lower, int upper) {
        long ans = 0;
        int n = nums.length;
        Arrays.sort(nums);
        for(int i = 0;i < n;i++){
            int lo = lower-nums[i], up = upper-nums[i];
            int l = i+1, r = n-1;
            while (l <= r){
                int m = l+r >> 1;
                if (nums[m] >= lo) r = m-1;
                else l = m+1;
            }
            int l1 = i+1, r1 = n-1;
            while (l1 <= r1){
                int m = l1+r1 >> 1;
                if (nums[m] <= up) l1 = m+1;
                else r1 = m-1;
            }
            if (l<=n-1 && r1 > i) ans += (r1-l+1);
        }
        return ans;
    }
}

复杂度分析

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

Q3

6356. 子字符串异或查询 - 力扣（Leetcode）

给你一个 二进制字符串 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：

1
2
3
输入：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：

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

提示：

  • 1 <= s.length <= 104
  • s[i] 要么是 '0' ，要么是 '1' 。
  • 1 <= queries.length <= 10^5
  • 0 <= firsti, secondi <= 10^9

思路

异或性质val ^ firsti = secondi => val == secondi ^ firsti

所以对于每个查询，找到两个数异或值有没有在s中出现就行。

但s长度很大，要预处理。对于查询中的任何两个数异或都是32位范围内，所以枚举每一个s[i]作为起点，再枚举二进制数的长度1~31，暴力求出所有可能的值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def substringXorQueries(self, s: str, q: List[List[int]]) -> List[List[int]]:
        m = len(q)
        n = len(s)
        ans = [[-1, -1] for i in range(m)]
        dic = {}
        for i in range(n):
            for j in range(i, min(i+32, n)):
                v = s[i:j+1]
                if v not in dic or j-i < dic[v][1]-dic[v][0]:
                    dic[v] = [i, j]
        for i in range(m):
            v = q[i][0]^q[i][1]
            x = bin(v)[2:]
            if x in dic:
                ans[i] = dic[x]
        return ans

复杂度分析

  • 时间复杂度：O(nlog m), m = max (nums[i])
  • 空间复杂度：O(nlog m)

Q4

6357. 最少得分子序列 - 力扣（Leetcode）

给你两个字符串 s 和 t 。你可以从字符串 t 中删除任意数目的字符。

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

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

字符串的得分为 right - left + 1 。请你返回使 t 成为 s 子序列的最小得分。

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

示例 1：

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

示例 2：

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

提示：

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

思路

因为得分是 right − left + 1，只与两端的位置有关。所以为了更可能删除后能匹配s的子序列，我们需要把 left, right 间所有字符删除。于是，题目变成删除t中的子字符串 s[left, right] 后能与s子序列匹配。

即若 t[0, left − 1] 是 s[0, k] 子序列， t[right + 1, m − 1] 是 s[k + 1, n − 1] 子序列，则答案是right − left + 1

则我们需要预处理 s[ : i] 对应的 t 的最长前缀的结束下标，s[i : ] 对应的 t 的最长后缀的开始下标​。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def minimumScore(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        pre, suf = [0]*n, [0]*n
        p, ans = 0, m
        # 预处理前缀 pre[i] = k: t[0:k-1]是s[0:i]的子序列
        for i in range(n):
            if p < m and s[i] == t[p]: p += 1
            pre[i] = p
        p = m-1
        # 预处理前缀 suf[i] = k: t[k+1:m-1]是s[i:n-1]的子序列
        for i in range(n-1, -1, -1):
            if p >= 0 and s[i] == t[p]: p -= 1
            suf[i] = p
        for i in range(n-1):
            x, y = pre[i], suf[i+1]
            ans = min(ans, y-x+1)
        # 单独处理 边界情况 全是前缀和全是后缀
        ans = min(ans, m-pre[n-1], suf[0]+1)
        return max(ans, 0) #负数代表不用删，就是0

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
Leetcode 332场周赛
2025/02/12/Leetcode-332场周赛/
Author
Zhongjun Qiu
Published
2025-02-12 15:08
License
 REWARD AUTHOR
 Comments
Comment plugin failed to load
Loading comment plugin
  1. Q1
    1. 思路
    2. 代码
    3. 复杂度分析
  2. Q2
    1. 思路
    2. 代码
    3. 复杂度分析
  3. Q3
    1. 思路
    2. 代码
    3. 复杂度分析
  4. Q4
    1. 思路
    2. 代码
    3. 复杂度分析
  1. Q1
    1. 思路
    2. 代码
    3. 复杂度分析
  2. Q2
    1. 思路
    2. 代码
    3. 复杂度分析
  3. Q3
    1. 思路
    2. 代码
    3. 复杂度分析
  4. Q4
    1. 思路
    2. 代码
    3. 复杂度分析