LeetCode 周赛 332，在套路里摸爬滚打~-六虎

我正在参与「启航计划」

大家好，今天是 3T 选手小彭。

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

小彭的 Android 沟通群 02 群现已建立啦，大众号回复 “加群” 加入咱们~

2562.找出数组的串联值（Easy）

标题地址

leetcode.cn/problems/fi…

标题描绘

给你一个下标从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）

标题地址

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(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 (l g n)$ 快速排序占用的递归栈空间。

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

运用排序优化后依然无法满意标题要求，咱们发现：内层循环并不需求线性扫描，咱们能够运用 $O (l g n)$ 二分查找寻觅：

榜首个大于等于 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 (n l g n + n l g n)$ 快速排序 + 组合的时刻，内层循环中每次二分查找的时刻是 $O (l g n)$ 。
空间复杂度： $O (l g n)$ 快速排序占用的递归栈空间。

2564.子字符串异或查询（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 最小的计划，所以需求在每次寻觅到答案后提前中止。

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 + L n)$ ，其间 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 (L n + m)$ ，其间 n 是字符串的长度， m 是 queries 数组的长度，L 是不同长度的窗口个数。 $O (L n)$ 是预处理的时刻，依据标题输入满意 $10^9 < 2^{30}$ 可知 L 的最大值是 30。
空间复杂度： $O (n L)$ ，散列表总共需求记载 nL 个数的映射联系。

2565.最少得分子序列（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 字符串的长度减去公共部分长度得到需求删去的字符个数。

但是，这道标题的输出得分取决于最左面被删去的字符下标 $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 的后缀，核算匹配后需求减去的子串长度，将一切枚举计划的解取最小值便是原标题的解。

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

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)$ ，前后缀数组的空间。

咱们下周见，有用请点赞重视！

本文已收录到 AndroidFamily，技能和职场问题，请重视大众号 [彭旭锐] 提问。

LeetCode 周赛 332，在套路里摸爬滚打~

2562.找出数组的串联值（Easy）

标题地址

标题描绘

题解

2563.核算公正数对的数目（Medium）

标题地址

标题描绘

题解一（排序 + 枚举组合）

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

2564.子字符串异或查询（Medium）

标题地址

标题描绘

前置常识

题解一（滑动窗口）

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

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

2565.最少得分子序列（Hard）

标题地址

标题描绘

题解（前后缀分化）

相关文章

决策树算法：原理与python实现案例

「MarketingGPT」掀翻全球千亿美金市场！国内首个带货AI全家桶，不玩你就out了

实时切换 Core Data 的云同步状态

DataBinding——使用Kotlin 委托优化

作者信息