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

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

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

本文是 LeetCode 上分之旅系列的第 28 篇文章，往期回忆请移步到文章结束~

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 = 26
        val set = HashSet<Int>()
        var ret = 0
        for (word in words) {
            if (word.length != 2) continue
            val 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 = 0x3F3F3F3F
        val n = words.size
        val dp = Array(n) { Array(26) { IntArray(26) { INF } }}
        // 开始状况
        dp[0][words[0][0] - 'a'][words[0][words[0].length - 1] - 'a'] = words[0].length
        for (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 = INF
        for (j in 0 until 26) {
            for (k in 0 until 26) {
                ret = Math.min(ret, dp[n - 1][j][k])
            }
        }
        return ret
    }
}

复杂度剖析：

• 时刻复杂度：O(n⋅C2)O(nC^2)O(n⋅C2) C= 26
• 空间复杂度：O(n⋅C2)O(nC^2)O(n⋅C2)

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.size
        val 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.size
        val m = queries.size
        val 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 = 0
        var j = 0
        val 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) + 1
                j++
            }
            // 缩短左指针
            while (i < l && logs[i][1] <  to - x) {
                cnts[logs[i][0]] = cnts[logs[i][0]]!! - 1
                if (cnts[logs[i][0]]!! == 0) cnts.remove(logs[i][0])
                i++
            }
            ret[id] = n - cnts.size
        }
        return ret
    }
}

复杂度剖析：

• 时刻复杂度：$O(mlgm+llogl+m+l)$ 瓶颈在排序；
• 空间复杂度：$O(m+n)$ 查询索引数组空间 + 散列表空间。

推荐阅览

LeetCode 上分之旅系列往期回忆：

• LeetCode 单周赛第 348 场 数位 DP 模版学会了吗？

• LeetCode 单周赛第 347 场 二维空间上的 LIS 最长递增子序列问题

• LeetCode 双周赛第 104 场 流水的动态规划，铁打的结构化考虑

• LeetCode 双周赛第 103 场 区间求和的树状数组经典应用

⭐️ 永远相信夸姣的工作行将产生，欢迎参加小彭的 Android 交流社群~