本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。
大家好，今天是 3T 选手小彭。
上周是 LeetCode 第 332 场周赛，你参加了吗？算法解题思维需要长时间锻炼，加入我们一起刷题吧~
小彭的 Android 交流群 02 群已经建立啦，公众号回复 “加群” 加入我们~
2562. 找出数组的串联值（Easy）
题目地址
https://leetcode.cn/problems/find-the-array-concatenation-value/
题目描述
给你一个下标从 0 开始的整数数组 nums 。
现定义两个数字的 串联 是由这两个数值串联起来形成的新数字。
- 例如，
15和49的串联是1549。
nums 的 串联值 最初等于 0 。执行下述操作直到 nums 变为空：
- 如果
nums中存在不止一个数字，分别选中nums中的第一个元素和最后一个元素，将二者串联得到的值加到nums的 串联值 上，然后从nums中删除第一个和最后一个元素。 - 如果仅存在一个元素，则将该元素的值加到
nums的串联值上，然后删除这个元素。
返回执行完所有操作后 nums 的串联值。
题解
简单模拟题，使用双指针向中间逼近即可。
class Solution {
fun findTheArrayConcVal(nums: IntArray): Long {
var left = 0
var right = nums.size - 1
var result = 0L
while (left <= right) {
result += if (left == right) {
nums[left]
} else{
Integer.valueOf("${nums[left]}${nums[right]}")
}
left++
right--
}
return result
}
}
复杂度分析：
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$
2563. 统计公平数对的数目（Medium）
题目地址
https://leetcode.cn/problems/count-the-number-of-fair-pairs/
题目描述
给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。
如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：
-
0 <= i < j < n，且 lower <= nums[i] + nums[j] <= upper
题解一（排序 + 枚举组合）
题目要求寻找 2 个目标数 nums[i] 和 nums[j] 满足两数之和处于区间 [lower, upper] 。虽然题目强调了下标 i 和下标 j 满足 0 <= i < j < n，但事实上两个数的顺序并不重要，我们选择 nums[2] + nums[4] 与选择 nums[4] + nums[2] 的结果是相同的。因此，第一反应可以使用 “朴素组合模板”，时间复杂度是 $O(n^2)$，但在这道题中会超出时间限制。
// 组合模板
class Solution {
fun countFairPairs(nums: IntArray, lower: Int, upper: Int): Long {
val n = nums.size
var result = 0L
for (i in 0 until nums.size - 1) {
for (j in i + 1 until nums.size) {
val sum = nums[i] + nums[j]
if (sum in lower..upper) result++
}
}
return result
}
}
以示例 1 来说，我们发现在外层循环选择 nums[i] = 4 的一趟循环中，当内层循环选择 $[4 + 4]$ 组合不满足条件后，选择一个比 $4$ 更大的 $[4 + 5]$ 组合显得没有必要。从这里容易想到使用 “排序” 剪去不必要的组合方案：我们可以先对输入数据进行排序，当内层循环的 nums[j] 不再可能满足条件时提前终止内层循环：
class Solution {
fun countFairPairs(nums: IntArray, lower: Int, upper: Int): Long {
// 排序 + 枚举组合
var result = 0L
nums.sort()
for (i in 0 until nums.size - 1) {
for (j in i + 1 until nums.size) {
val sum = nums[i] + nums[j]
if (sum < lower) continue
if (sum > upper) break
result++
}
}
return result
}
}
复杂度分析：
- 时间复杂度：$O(nlgn + n^2)$ 快速排序 + 组合的时间，其中 $O(n^2)$ 是一个比较松的上界。
- 空间复杂度：$O(lgn)$ 快速排序占用的递归栈空间。
题解二（排序 + 二分查找）
使用排序优化后依然无法满足题目要求，我们发现：内层循环并不需要线性扫描，我们可以使用 $O(lgn)$ 二分查找寻找：
- 第一个大于等于 min 的数
- 最后一个小于等于 max 的数
再使用这 2 个边界数的下标相减，即可获得内层循环中的目标组合个数。
class Solution {
fun countFairPairs(nums: IntArray, lower: Int, upper: Int): Long {
// 排序 + 二分查找
var result = 0L
nums.sort()
for (i in 0 until nums.size - 1) {
// nums[i] + x >= lower
// nums[i] + x <= upper
// 目标数的范围：[lower - nums[i], upper - nums[i]]
val min = lower - nums[i]
val max = upper - nums[i]
// 二分查找优化：寻找第一个大于等于 min 的数
var left = i + 1
var right = nums.size - 1
while (left < right) {
val mid = (left + right - 1) ushr 1
if (nums[mid] < min) {
left = mid + 1
} else {
right = mid
}
}
val minIndex = if (nums[left] >= min) left else continue
// 二分查找优化：寻找最后一个小于等于 max 的数
left = minIndex
right = nums.size - 1
while (left < right) {
val mid = (left + right + 1) ushr 1
if (nums[mid] > max) {
right = mid - 1
} else {
left = mid
}
}
val maxIndex = if (nums[left] <= max) left else continue
result += maxIndex - minIndex + 1
}
return result
}
}
复杂度分析：
- 时间复杂度：$O(nlgn + nlgn)$ 快速排序 + 组合的时间，内层循环中每次二分查找的时间是 $O(lgn)$。
- 空间复杂度：$O(lgn)$ 快速排序占用的递归栈空间。
2564. 子字符串异或查询（Medium）
题目地址
https://leetcode.cn/problems/substring-xor-queries/
题目描述
给你一个 二进制字符串 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 个查询的答案。
子字符串 是一个字符串中一段连续非空的字符序列。
前置知识
记 ⊕ 为异或运算，异或运算满足以下性质：
- 基本性质：x ⊕ y = 0
- 交换律：x ⊕ y = y ⊕ x
- 结合律：(x ⊕ y) ⊕ z = x ⊕ (y ⊕ z)
- 自反律：x ⊕ y ⊕ y = x
题解一（滑动窗口）
题目要求字符串 s 的最短子字符串，使其满足其对应的数值 val ⊕ first = second，根据异或的自反律性质可知（等式两边同异或 first），题目等价于求满足 val = first ⊕ second 的最短子字符串。
容易想到的思路是：我们单独处理 queries 数组中的每个查询，并计算目标异或值 target = first ⊕ second，而目标字符串的长度一定与 target 的二进制数的长度相同。所以，我们先获取 target 的有效二进制长度 len，再使用长度为 len 的滑动窗口寻找目标子字符串。由于题目要求 [left 最小的方案，所以需要在每次寻找到答案后提前中断。
class Solution {
fun substringXorQueries(s: String, queries: Array<IntArray>): Array<IntArray> {
// 寻找等于目标值的子字符串
// 滑动窗口
val n = s.length
val result = Array(queries.size) { intArrayOf(-1, -1) }
for ((index, query) in queries.withIndex()) {
val target = query[0] xor query[1]
// 计算 target 的二进制长度
var len = 1
var num = target
while (num >= 2) {
num = num ushr 1
len++
}
for (left in 0..n - len) {
val right = left + len - 1
if (s.substring(left, right + 1).toInt(2) == target) {
result[index][0] = left
result[index][1] = right
break
}
}
}
return result
}
}
复杂度分析：
- 时间复杂度：$O(mn)$，其中 m 是
queries数组的长度，n 是字符串的长度，在这道题中会超时。 - 空间复杂度：$O(1)$，不考虑结果数组。
题解二（滑动窗口 + 分桶预处理）
事实上，如果每次都单独处理 queries 数组中的每个查询，那么题目将查询设置为数组就没有意义了，而且在遇到目标异或值 target 的二进制长度 len 相同时，会存在大量重复计算。因此，容易想到的思路是：我们可以预先将 queries 数组中所有二进制长度 len 相同的查询划分为一组，使相同长度的滑动窗口只会计算一次。
另一个细节是题目的测试用例中存在相同的查询，所以我们需要在映射表中使用 LinkedList 记录相同目标异或值 target 到查询下标 index 的关系。
class Solution {
fun substringXorQueries(s: String, queries: Array<IntArray>): Array<IntArray> {
// 寻找等于目标值的子字符串
// 根据长度分桶：len to <target,index>
val lenMap = HashMap<Int, HashMap<Int, LinkedList<Int>>>()
for ((index, query) in queries.withIndex()) {
val target = query[0] xor query[1]
// 计算 target 的二进制长度
var len = 1
var num = target
while (num >= 2) {
num = num ushr 1
len++
}
lenMap.getOrPut(len) { HashMap<Int, LinkedList<Int>>() }.getOrPut(target) { LinkedList<Int>() }.add(index)
}
// 滑动窗口
val n = s.length
val result = Array(queries.size) { intArrayOf(-1, -1) }
for ((len, map) in lenMap) {
for (left in 0..n - len) {
val right = left + len - 1
val curValue = s.substring(left, right + 1).toInt(2)
if (map.containsKey(curValue)) {
for (index in map[curValue]!!) {
result[index][0] = left
result[index][1] = right
}
map.remove(curValue)
// 该长度搜索结束
if (map.isEmpty()) break
}
}
}
return result
}
}
复杂度分析：
- 时间复杂度：$O(m + Ln)$，其中 n 是字符串的长度， m 是
queries数组的长度，L 是不同长度的窗口个数，$O(m)$ 是预处理的时间。根据题目输入满足 $10^9 < 2^{30}$ 可知 L 的最大值是 30。 - 空间复杂度：$O(m)$，散列表总共需要记录 m 个查询的映射关系。
题解三（滑动窗口 + 预处理字符串）
这道题的思路也是通过预处理过滤相同长度的滑动窗口，区别在于预处理的是输入字符串，我们直接计算字符串 s 中所有可能出现的数字以及对应的 [left,right] 下标，再利用这份数据给予 queries 数组进行 $O(1)$ 打表查询。
class Solution {
fun substringXorQueries(s: String, queries: Array<IntArray>): Array<IntArray> {
val n = s.length
// 预处理
val valueMap = HashMap<Int, IntArray>()
for (len in 1..Math.min(n,31)) {
for (left in 0..n - len) {
val right = left + len - 1
val num = s.substring(left, right + 1).toInt(2)
if (!valueMap.containsKey(num)) {
valueMap[num] = intArrayOf(left, right)
}
}
}
val result = Array(queries.size) { intArrayOf(-1, -1) }
for ((index, query) in queries.withIndex()) {
val target = query[0] xor query[1]
if (valueMap.containsKey(target)) {
result[index] = valueMap[target]!!
}
}
return result
}
}
复杂度分析：
- 时间复杂度：$O(Ln + m)$，其中 n 是字符串的长度， m 是
queries数组的长度，L 是不同长度的窗口个数。$O(Ln)$ 是预处理的时间，根据题目输入满足 $10^9 < 2^{30}$ 可知 L 的最大值是 30。 - 空间复杂度：$O(nL)$，散列表总共需要记录 nL 个数的映射关系。
2565. 最少得分子序列（Hard）
题目地址
https://leetcode.cn/problems/subsequence-with-the-minimum-score/
题目描述
给你两个字符串 s 和 t 。
你可以从字符串 t 中删除任意数目的字符。
如果没有从字符串 t 中删除字符，那么得分为 0 ，否则：
- 令
left为删除字符中的最小下标。 - 令
right为删除字符中的最大下标。
字符串的得分为 right - left + 1 。
请你返回使 t 成为 s 子序列的最小得分。
一个字符串的 子序列 是从原字符串中删除一些字符后（也可以一个也不删除），剩余字符不改变顺序得到的字符串。（比方说 "ace" 是 "acde" 的子序列，但是 "aec" 不是）。
题解（前后缀分解）
这道题第一感觉是 LCS 最长公共子序列的衍生问题，我们可以使用朴素 LCS 模板求解字符串 s 和字符串 t 的最长公共子序列 ，再使用 t 字符串的长度减去公共部分长度得到需要删除的字符个数。
然而，这道题目的输出得分取决于最左边被删除的字符下标 $index_{left}$ 和最右边被删除字符的下标 $index_{right}$，常规套路显得无从下手。所以，我们尝试对原问题进行转换：
-
思考 1： 假设删除
left和right两个字符后能够满足条件，那么删除[left,right]中间所有字符也同样能满足条件（贪心思路：删除更多字符后成为子序列的可能性更大）； -
思考 1 结论： 原问题等价于求删除字符串
t中的最短字符串[i,j]，使得剩余部分[0, i - 1]和[j + 1, end]合并后成为字符串s的一个子序列。 -
思考 2： 如果字符串 t 删除
[i, j]区间的字符后能够满足条件，那么一定存在剩余部分[0, i - 1]与字符串s的前缀匹配，而[j + 1, end]与字符串s的后缀匹配，而且这两段匹配的区域一定 “不存在” 交集。 -
思考 2 结论： 我们可以枚举字符串 s 中的所有分割点，分别位于分割点的
s前缀匹配t的前缀，用s的后缀匹配t的后缀，计算匹配后需要减去的子串长度，将所有枚举方案的解取最小值就是原题目的解。
思路参考视频讲解：https://www.bilibili.com/video/BV1GY411i7RP/ —— 灵茶山艾府 著
class Solution {
fun minimumScore(s: String, t: String): Int {
// 前后缀分解
val n = s.length
val m = t.length
// s 的后缀和 t 的后缀匹配的最长子串的起始下标
val sub = IntArray(n + 1).apply {
var right = m - 1
for (index in n - 1 downTo 0) {
if (right >= 0 && s[index] == t[right]) right--
this[index] = right + 1
}
this[n] = m
}
// s 的前缀和 t 的前缀匹配的最长子串的终止下标
val pre = IntArray(n).apply {
var left = 0
for (index in 0..n - 1) {
if (left < m && s[index] == t[left]) left++
this[index] = left - 1
}
}
// 枚举分割点
var result = sub[0]
if (0 == result) return 0 // 整个 t 是 s 的子序列
for (index in 0 until n) {
result = Math.min(result, m - (m - sub[index + 1]) - (pre[index] + 1))
}
return result
}
}
复杂度分析：
- 时间复杂度：$O(n)$，其中 n 是字符串 s 的长度，预处理和枚举的时间复杂度都是 $O(n)$。
- 空间复杂度：$O(n)$，前后缀数组的空间。
我们下周见，有用请赞赏上榜！想看小彭的更多题解代码，可关注 Github：https://github.com/pengxurui/LeetCode-Kotlin/tree/main/leetcode