LeetCode 双周赛 107（2023/06/24）滑动窗口与离散化

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

往期回顾：LeetCode 单周赛第 348 场 · 数位 DP 模版学会了吗？

T1. 最大字符串配对数目（Easy）

标签：散列表

T2. 构造最长的新字符串（Medium）

标签：模拟

T3. 字符串连接删减字母（Medium）

标签：状态 DP

T4. 统计没有收到请求的服务器数目（Medium）

标签：排序、滑动窗口、离散化

T1. 最大字符串配对数目（Easy）

https://leetcode.cn/problems/find-maximum-number-of-string-pairs/

题解（散列表）

题目说明所有字符串不相同，因此我们可以枚举每个字符串，检查其反转是否存在，模板类似于两数之和；

扩展：如果字符串存在重复，可以将配对的字符分组再按两两配对计算；
扩展：如果字符串长度很长会存在散列冲突，可以调整 U 为较大素数。

class Solution {fun maximumNumberOfStringPairs(words: Array<String>): Int {val U = 26val set = HashSet<Int>()var ret = 0for (word in words) {if (word.length != 2) continueval key = (word[0] - 'a') * U + (word[1] - 'a')val reversedKey = (word[1] - 'a') * U + (word[0] - 'a')if (set.contains(reversedKey)) ret ++set.add(key)}return ret}
}

复杂度分析：

时间复杂度： $O (L)$ 需要访问每个单词的每个字符；
空间复杂度： $O (n)$ 散列表空间。

T2. 构造最长的新字符串（Medium）

https://leetcode.cn/problems/construct-the-longest-new-string/

题解（模拟）

根据题意分析，我们总可以将 ABAB…ABAB 置于结果中间，再将 AA 或 BB 置于两边。此时所有 AB 都可选，而 AA BB 最多只能选择较少者 + 1，分类讨论即可：

class Solution {fun longestString(x: Int, y: Int, z: Int): Int {return if (x == y) {(x + y + z) * 2} else {(Math.min(x, y) * 2 + 1 + z) * 2}}
}

复杂度分析：

时间复杂度： $O (1)$
空间复杂度： $O (1)$

T3. 字符串连接删减字母（Medium）

https://leetcode.cn/problems/decremental-string-concatenation/

题解（状态 DP）

对于每个字符串 [i]，有拼接到前方或拼接到后方两种方案；
当考虑 join(i, i + 1) 时，我们只需要关心两个字符串的首尾 4 个字符，对于中间的字符是不关心的。因此在遍历到字符串 [i] 时，我们检查以 [i - 1] 为结尾的子问题的可能方案，并维护以 [i] 为结尾的子问题的所有方案。

class Solution {fun minimizeConcatenatedLength(words: Array<String>): Int {val INF = 0x3F3F3F3Fval n = words.sizeval dp = Array(n) { Array(26) { IntArray(26) { INF } }}// 起始状态dp[0][words[0][0] - 'a'][words[0][words[0].length - 1] - 'a'] = words[0].lengthfor (i in 1 until n) {val word = words[i]val x = word[0] - 'a'val y = word[word.length - 1] - 'a'// 枚举子问题状态for (j in 0 until 26) {for (k in 0 until 26) {// 拼接到前方if (y == j) {dp[i][x][k] = Math.min(dp[i][x][k], dp[i - 1][j][k] + word.length - 1)} else {dp[i][x][k] = Math.min(dp[i][x][k], dp[i - 1][j][k] + word.length)}// 拼接到后方if (x == k) {dp[i][j][y] = Math.min(dp[i][j][y], dp[i - 1][j][k] + word.length - 1)} else {dp[i][j][y] = Math.min(dp[i][j][y], dp[i - 1][j][k] + word.length)}}}}var ret = INFfor (j in 0 until 26) {for (k in 0 until 26) {ret = Math.min(ret, dp[n - 1][j][k])}}return ret}
}

复杂度分析：

时间复杂度： $O(n·C^2)$ C= 26
空间复杂度： $O(n·C^2)$

T4. 统计没有收到请求的服务器数目（Medium）

https://leetcode.cn/problems/count-zero-request-servers/

题解一（暴力）

线性扫描日志，并线性扫描查询列表，将日志记录投递到对应的查询中，同时使用散列表对相同服务器去重。

class Solution {fun countServers(n: Int, logs: Array<IntArray>, x: Int, queries: IntArray): IntArray {val m = queries.sizeval sets = Array(m) { HashSet<Int>() }val ret = IntArray(m)// 暴力for (log in logs) {for ((i, query) in queries.withIndex()) {if (log[1] in query - x .. query) {sets[i].add(log[0])}}}// 输出for (i in 0 until m) {ret[i] = n - sets[i].size}return ret}
}

复杂度分析：

时间复杂度： $O (nm)$ 超出时间限制；
空间复杂度： $O (nm)$ 散列表空间，最坏情况下每个查询中包含所有服务器记录。

题解二（排序 + 滑动窗口 + 离散化）

需要注意题目中的单调性，对于日志时间 log_i < log_j，当 log_i 时间晚于 query_k 时，那么日志时间更晚的 log_k 必然无法投递到 query_k 中，而暴力算法中没有利用单调性质。因此，我们先对 log 日志列表和 queries 查询列表按时间顺序排序，再来使用滑动窗口来维护每个查询中覆盖的日志信息。

class Solution {fun countServers(n: Int, logs: Array<IntArray>, x: Int, queries: IntArray): IntArray {val l = logs.sizeval m = queries.sizeval ret = IntArray(m)// 查询索引val indexs = Array(m) { it }// 排序Arrays.sort(logs) { i1, i2 ->i1[1] - i2[1]}Arrays.sort(indexs) { i1, i2 -> queries[i1] - queries[i2]}// 滑动窗口 + 离散化var i = 0var j = 0val cnts = HashMap<Int, Int>()for (id in indexs) {val to = queries[id]if (to <= x) throw IllegalStateException()// 拓展右指针while (j < l && logs[j][1] <= to) {cnts[logs[j][0]] = cnts.getOrDefault(logs[j][0], 0) + 1j++}// 收缩左指针while (i < l && logs[i][1] <  to - x) {cnts[logs[i][0]] = cnts[logs[i][0]]!! - 1if (cnts[logs[i][0]]!! == 0) cnts.remove(logs[i][0])i++}ret[id] = n - cnts.size}return ret}
}