LeetCode 周赛 332（2023/02/12）在套路

⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。

学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在这个专栏里，小彭与你分享每场 LeetCode 周赛的解题报告，一起体会上分之旅。

本文是 LeetCode 上分之旅系列的第 1 篇文章，往期回顾请移步到文章末尾~

大家好，我是小彭。

上周是 LeetCode 第 332 场周赛，你参加了吗？算法解题思维需要长时间锻炼，加入我们一起刷题吧~

找出数组的串联值（Easy）

题目地址

leetcode.cn/problems/fi…

题目描述

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

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

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

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

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

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

题解

简单模拟题，使用双指针向中间逼近即可。

kotlin复制代码
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(n)O(n)
空间复杂度：O(1)O(1)O(1)

统计公平数对的数目（Medium）

题目地址

leetcode.cn/problems/co…

题目描述

给你一个下标从 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(n2)O(n^2)O(n2)，但在这道题中会超出时间限制。

kotlin复制代码// 组合模板
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][4+4] 组合不满足条件后，选择一个比 444 更大的 [4+5][4 + 5][4+5] 组合显得没有必要。从这里容易想到使用 “排序” 剪去不必要的组合方案：我们可以先对输入数据进行排序，当内层循环的 nums[j] 不再可能满足条件时提前终止内层循环：

kotlin复制代码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+n2)O(nlgn + n^2)O(nlgn+n2) 快速排序 + 组合的时间，其中 O(n2)O(n^2)O(n2) 是一个比较松的上界。
空间复杂度：O(lgn)O(lgn)O(lgn) 快速排序占用的递归栈空间。

题解二（排序 + 二分查找）

使用排序优化后依然无法满足题目要求，我们发现：内层循环并不需要线性扫描，我们可以使用 O(lgn)O(lgn)O(lgn) 二分查找寻找：

第一个大于等于 min 的数
最后一个小于等于 max 的数

再使用这 2 个边界数的下标相减，即可获得内层循环中的目标组合个数。

kotlin复制代码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(nlgn + nlgn)O(nlgn+nlgn) 快速排序 + 组合的时间，内层循环中每次二分查找的时间是 O(lgn)O(lgn)O(lgn)。
空间复杂度：O(lgn)O(lgn)O(lgn) 快速排序占用的递归栈空间。

子字符串异或查询（Medium）

题目地址

leetcode.cn/problems/su…

题目描述

给你一个 二进制字符串 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 最小的方案，所以需要在每次寻找到答案后提前中断。

kotlin复制代码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)O(mn)O(mn)，其中 m 是 queries 数组的长度，n 是字符串的长度，在这道题中会超时。
空间复杂度：O(1)O(1)O(1)，不考虑结果数组。

题解二（滑动窗口 + 分桶预处理）

事实上，如果每次都单独处理 queries 数组中的每个查询，那么题目将查询设置为数组就没有意义了，而且在遇到目标异或值 target 的二进制长度 len 相同时，会存在大量重复计算。因此，容易想到的思路是：我们可以预先将 queries 数组中所有二进制长度 len 相同的查询划分为一组，使相同长度的滑动窗口只会计算一次。

另一个细节是题目的测试用例中存在相同的查询，所以我们需要在映射表中使用 LinkedList 记录相同目标异或值 target 到查询下标 index 的关系。

kotlin复制代码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)O(m + Ln)O(m+Ln)，其中 n 是字符串的长度， m 是 queries 数组的长度，L 是不同长度的窗口个数，O(m)O(m)O(m) 是预处理的时间。根据题目输入满足 109<23010^9 < 2^{30}109<230 可知 L 的最大值是 30。
空间复杂度：O(m)O(m)O(m)，散列表总共需要记录 m 个查询的映射关系。

题解三（滑动窗口 + 预处理字符串）

这道题的思路也是通过预处理过滤相同长度的滑动窗口，区别在于预处理的是输入字符串，我们直接计算字符串 s 中所有可能出现的数字以及对应的 [left,right] 下标，再利用这份数据给予 queries 数组进行 O(1)O(1)O(1) 打表查询。

kotlin复制代码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)O(Ln + m)O(Ln+m)，其中 n 是字符串的长度， m 是 queries 数组的长度，L 是不同长度的窗口个数。O(Ln)O(Ln)O(Ln) 是预处理的时间，根据题目输入满足 109<23010^9 < 2^{30}109<230 可知 L 的最大值是 30。
空间复杂度：O(nL)O(nL)O(nL)，散列表总共需要记录 nL 个数的映射关系。

最少得分子序列（Hard）

题目地址

leetcode.cn/problems/su…

题目描述

给你两个字符串 s 和 t 。

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

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

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

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

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

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

题解（前后缀分解）

这道题第一感觉是 LCS 最长公共子序列的衍生问题，我们可以使用朴素 LCS 模板求解字符串 s 和字符串 t 的最长公共子序列，再使用 t 字符串的长度减去公共部分长度得到需要删除的字符个数。

然而，这道题目的输出得分取决于最左边被删除的字符下标 indexleftindex_{left}indexleft 和最右边被删除字符的下标 indexrightindex_{right}indexright，常规套路显得无从下手。所以，我们尝试对原问题进行转换：

思考 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 的后缀，计算匹配后需要减去的子串长度，将所有枚举方案的解取最小值就是原题目的解。

思路参考视频讲解：www.bilibili.com/video/BV1GY… —— 灵茶山艾府著

kotlin复制代码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)O(n)O(n)，其中 n 是字符串 s 的长度，预处理和枚举的时间复杂度都是 O(n)O(n)O(n)。
空间复杂度：O(n)O(n)O(n)，前后缀数组的空间。

我们下周见，有用请点赞关注！

推荐阅读
LeetCode 上分之旅系列往期回顾：

LeetCode 单周赛第 343 场 · 结合「下一个排列」的贪心构造问题

LeetCode 单周赛第 342 场 · 把问题学复杂，再学简单

LeetCode 双周赛第 102 场· 这次又是最短路。

LeetCode 双周赛第 101 场 · 是时候做出改变了！

⭐️ 永远相信美好的事情即将发生，欢迎加入小彭的 Android 交流社群~

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有