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

leetcode,双周,滑动,窗口,离散 · 浏览次数 : 35

小编点评

**代码分析** **算法 1:暴力枚举** - 使用 HashSet 存储已访问的服务器记录。 - 对日志和查询列表进行遍历,并为每个查询更新服务器列表。 - 最终,返回每个查询对应服务器数的总和。 **算法 2:排序 + 滑动窗口 + 离散化** - 将日志和查询列表排序。 - 使用滑动窗口技术,以维护每个查询的覆盖范围。 - 使用离散化技术,存储每个服务器在所有查询中出现的次数。 - 返回每个查询对应服务器数的总和。 **复杂性分析** **算法 1:暴力枚举** - 时间复杂度:$O(nm)$ - 空间复杂度:$O(nm)$ **算法 2:排序 + 滑动窗口 + 离散化** - 时间复杂度:$O(mlgm + llogl + m + l)$ - 空间复杂度:$O(m + n)$ **主要瓶颈** **算法 1:暴力枚举** - 时间瓶颈:对日志和查询列表进行遍历。 - 空间瓶颈:存储已访问的服务器记录。 **算法 2:排序 + 滑动窗口 + 离散化** - 时间瓶颈:排序日志和查询列表。 - 空间瓶颈:维护滑动窗口和离散化数据结构。 **其他** * 算法 2 可以通过使用 HashMap 等数据结构优化时间复杂度。 * 算法 1 可以使用 Set 等数据结构来优化空间复杂度。 * 算法 2 可以根据具体情况调整滑动窗口的大小。

正文

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

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·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.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 双周赛 107(2023/06/24)滑动窗口与离散化相似的内容:

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

> **本文已收录到 [AndroidFamily](https://github.com/pengxurui/AndroidFamily),技术和职场问题,请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。** - 往期回顾:[LeetCode 单周赛第 348 场 · 数

LeetCode 双周赛 98,脑筋急转弯转不过来!

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 昨晚是 LeetCode 第 98 场双周赛,你参加了吗?这场周赛需要脑筋急转弯,转不过来 Medium 就会变成 Hard,转得过来就变成 Easy。 小彭的 Android 交流群 0

LeetCode 双周赛 99,纯纯送分场!

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 昨晚是 LeetCode 第 99 场双周赛,你参加了吗?这场周赛整体难度很低,第 4 题评论区普遍认为是 1 字头,纯纯手速场。 小彭的 Android 交流群 02 群来了,公众号回复

LeetCode 双周赛 101,DP/中心位贪心/裴蜀定理/Dijkstra/最小环

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 这周比较忙,上周末的双周赛题解现在才更新,虽迟但到哈。上周末这场是 LeetCode 第 101 场双周赛,整体有点难度,第 3 题似乎比第 4 题还难一些。 周赛大纲 2605. 从两个

LeetCode 双周赛 102,模拟 / BFS / Dijkstra / Floyd

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,欢迎来到小彭的 LeetCode 周赛解题报告。 昨晚是 LeetCode 双周赛第 102 场,你参加了吗?这场比赛比较简单,拼的是板子手速,继上周掉大分后算是回了一口血 😁。 2618. 查询网

LeetCode 双周赛 103(2023/04/29)区间求和的树状数组经典应用

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 这场周赛是 LeetCode 双周赛第 103 场,难得在五一假期第一天打周赛的人数也没有少太多。这场比赛前 3 题比较简单,我们把篇幅留给最后一题。 往期周赛回顾:LeetCode 单周

LeetCode 双周赛 104(2023/05/13)流水的动态规划,铁打的结构化思考

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 往期回顾:LeetCode 单周赛第 344 场 · 手写递归函数的通用套路 T1. 老人的数目(Easy) 标签:模拟、计数 T2. 矩阵中的和(Medium) 标签:模拟、排序 T3. 最大或值(Medi

LeetCode 双周赛 106(2023/06/10)两道思维题

> **本文已收录到 [AndroidFamily](https://github.com/pengxurui/AndroidFamily),技术和职场问题,请关注公众号 [彭旭锐] 加入知识星球提问。** - 往期回顾:[LeetCode 单周赛第 348 场 · 数位 DP 模版学会了吗?](h

刷爆 LeetCode 双周赛 100,单方面宣布第一题最难

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 上周末是 LeetCode 第 100 场双周赛,你参加了吗?这场周赛整体没有 Hard 题,但是也没有 Easy 题。第一题国服前百名里超过一半人 wa,很少见。 小彭的技术交流群 02

LeetCode 周赛 345(2023/05/14)体验一题多解的算法之美

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 往期回顾:LeetCode 双周赛第 104 场 · 流水的动态规划,铁打的结构化思考 周赛概览 T1. 找出转圈游戏输家(Easy) 标签:模拟、计数 T2. 相邻值的按位异或(Medium) 标签:模拟、