LeetCode 周赛上分之旅 #44 同余前缀和问题与经典倍增 LCA 算法

T1. 统计对称整数的数目(Easy)

  • 标签:模拟

T2. 生成特殊数字的最少操作(Medium)

  • 标签:思维、回溯、双指针

T3. 统计趣味子数组的数目(Medium)

  • 标签:同余定理、前缀和、散列表

T4. 边权重均等查询(Hard)

  • 标签:图、倍增、LCA、树上差分

T1. 统计对称整数的数目(Easy)

https://leetcode.cn/problems/count-symmetric-integers/

题解(模拟)

根据题意模拟,亦可以使用前缀和预处理优化。

class Solution {
    fun countSymmetricIntegers(low: Int, high: Int): Int {
        var ret = 0
        for (x in low..high) {
            val s = "$x"
            val n = s.length
            if (n % 2 != 0) continue
            var diff = 0
            for (i in 0 until n / 2) {
                diff += s[i] - '0'
                diff -= s[n - 1 - i] - '0'
            }
            if (diff == 0) ret += 1
        }
        return ret
    }
}

复杂度分析:

  • 时间复杂度:O((high-low)lg^{high}) 单次检查时间为 O(lg^{high})
  • 空间复杂度:O(1) 仅使用常量级别空间。

T2. 生成特殊数字的最少操作(Easy)

https://leetcode.cn/problems/minimum-operations-to-make-a-special-number/

题解一(回溯)

思维题,这道卡了多少人。

  • 阅读理解: 在一次操作中,您可以选择 num 的任意一位数字并将其删除,求最少需要多少次操作可以使 num 变成 25 的倍数;
  • 规律: 对于 25 的倍数,当且仅当结尾为「00、25、50、75」这 4 种情况时成立,我们尝试构造出尾部符合两个数字能被 25 整除的情况。

可以用回溯解决:

class Solution {
    fun minimumOperations(num: String): Int {
        val memo = HashMap<String, Int>()

        fun count(x: String): Int {
            val n = x.length
            if (n == 1) return if (x == "0") 0 else 1
            if (((x[n - 2] - '0') * 10 + (x[n - 1]- '0')) % 25 == 0) return 0
            if(memo.containsKey(x))return memo[x]!!
            val builder1 = StringBuilder(x)
            builder1.deleteCharAt(n - 1)
            val builder2 = StringBuilder(x)
            builder2.deleteCharAt(n - 2)
            val ret = 1 + min(count(builder1.toString()), count(builder2.toString()))
            memo[x]=ret
            return ret
        }
        
        return count(num)
    }
}

复杂度分析:

  • 时间复杂度:O(n^2·m) 最多有 n^2 种子状态,其中 m 是字符串的平均长度,O(m) 是构造中间字符串的时间;
  • 空间复杂度:O(n) 回溯递归栈空间。

题解二(双指针)

初步分析:

  • 模拟: 事实上,问题的方案最多只有 4 种,回溯的中间过程事实在尝试很多无意义的方案。我们直接枚举这 4 种方案,删除尾部不属于该方案的字符。以 25 为例,就是删除 5 后面的字符以及删除 2 与 5 中间的字符;
  • 抽象: 本质上是一个最短匹配子序列的问题,即 「找到 nums 中最靠后的匹配的最短子序列」问题,可以用双指针模拟。

具体实现:

  • 双指针: 我们找到满足条件的最靠左的下标 i,并删除末尾除了目标数字外的整段元素,即 ret = n - i - 2
  • 特殊情况: 在 4 种构造合法的特殊数字外,还存在删除所有非 0 数字后构造出 0 的方案;
  • 是否要验证数据含有前导零: 对于构造「00」的情况,是否会存在删到最后剩下多个 0 的情况呢?其实是不存在的。因为题目说明输入数据 num 本身是不包含前导零的,如果最后剩下多个 0 ,那么在最左边的 0 左侧一定存在非 0 数字,否则与题目说明矛盾。
class Solution {
    fun minimumOperations(num: String): Int {
        val n = num.length
        var ret = n
        for (choice in arrayOf("00", "25", "50", "75")) {
            // 双指针
            var j = 1
            for (i in n - 1 downTo 0) {
                if (choice[j] != num[i]) continue
                if (--j == -1) {
                    ret = min(ret, n - i - 2)
                    break
                }
            }
        }
        // 特殊情况
        ret = min(ret, n - num.count { it == '0'})
        return ret
    }
}

复杂度分析:

  • 时间复杂度:O(n) 4 种方案和特殊方案均是线性遍历;
  • 空间复杂度:O(1) 仅使用常量级别空间。

T3. 统计趣味子数组的数目(Medium)

https://leetcode.cn/problems/count-of-interesting-subarrays/

题解(同余 + 前缀和 + 散列表)

初步分析:

  • 问题目标: 统计数组中满足目标条件的子数组;
  • 目标条件: 在子数组范围 [l, r] 内,设 cnt 为满足 nums[i] % m == k 的索引 i 的数量,并且 cnt % m == k。大白话就是算一下有多少数的模是 k,再判断个数的模是不是也是 k
  • 权重: 对于满足 nums[i] % m == k 的元素,它对结果的贡献是 1,否则是 0

分析到这里,容易想到用前缀和实现:

  • 前缀和: 记录从起点到 [i] 位置的 [0, i] 区间范围内满足目标的权重数;
  • 两数之和: 从左到右枚举 [i],并寻找已经遍历的位置中满足 (preSum[i] - preSum[j]) \% m == k 的方案数记入结果;
  • 公式转换: 上式带有取模运算,我们需要转换一下:
    • 原式 (preSum[i] - preSum[j]) \% m == k
    • 考虑 preSum[i] \% m - preSum[j] \% m 是正数数的的情况,原式等价于:preSum[i] \% m - preSum[j] \% m == k
    • 考虑 preSum[i] \% m - preSum[j] \% m 是负数的的情况,我们在等式左边增加补数:(preSum[i] \% m - preSum[j] \% m + m) %m == k
    • 联合正数和负数两种情况,即我们需要找到前缀和为 (preSum[i] \% m - k + m) \% m 的元素;
  • 修正前缀和定义: 最后,我们修改前缀和的定义为权重 \% m

组合以上技巧:

class Solution {
    fun countInterestingSubarrays(nums: List<Int>, m: Int, k: Int): Long {
        val n = nums.size
        var ret = 0L
        val preSum = HashMap<Int, Int>()
        preSum[0] = 1 // 注意空数组的状态
        var cur = 0
        for (i in 0 until n) {
            if (nums[i] % m == k) cur ++ // 更新前缀和
            val key = cur % m
            val target = (key - k + m) % m
            ret += preSum.getOrDefault(target, 0) // 记录方案
            preSum[key] = preSum.getOrDefault(key, 0) + 1 // 记录前缀和
        }
        return ret
    }
}

复杂度分析:

  • 时间复杂度:O(n) 线性遍历,单次查询时间为 O(1)
  • 空间复杂度:O(m) 散列表空间。

相似题目:


T4. 边权重均等查询(Hard)

https://leetcode.cn/problems/minimum-edge-weight-equilibrium-queries-in-a-tree/

题解(倍增求 LCA、树上差分)

初步分析:

  • 问题目标: 给定若干个查询 [x, y],要求计算将 <x, y> 的路径上的每条边修改为相同权重的最少操作次数;
  • 问题要件: 对于每个查询 [x, y],我们需要计算 <x, y> 的路径长度 l,以及边权重的众数的出现次数 c,而要修改的操作次数就是 l - c
  • 技巧: 对于 “树上路径” 问题有一种经典技巧,我们可以把 <x, y> 的路径转换为从 <x, lca> 的路径与 <lca, y> 的两条路径;

思考实现:

  • 长度: 将问题转换为经过 lca 中转的路径后,路径长度 l 可以用深度来计算:l = depth[x] + depth[y] - 2 * depth[lca]
  • 权重: 同理,权重 w[x,y] 可以通过 w[x, lca]w[lca, y] 累加计算;

现在的关键问题是,如何快速地找到 <x, y> 的最近公共祖先 LCA?

对于单次 LCA 操作来说,我们可以走 DFS 实现 O(n) 时间复杂度的算法,而对于多次 LCA 操作可以使用 倍增算法 预处理以空间换时间,单次 LCA 操作的时间复杂度进位 O(lgn)

在 LeetCode 有倍增的模板题 1483. 树节点的第 K 个祖先

在求 LCA 时,我们先把 <x, y> 跳到相同高度,再利用倍增算法向上跳 2^j 个父节点,直到到达相同节点即为最近公共祖先。

class Solution {
    fun minOperationsQueries(n: Int, edges: Array<IntArray>, queries: Array<IntArray>): IntArray {
        val U = 26
        // 建图
        val graph = Array(n) { LinkedList<IntArray>() }
        for (edge in edges) {
            graph[edge[0]].add(intArrayOf(edge[1], edge[2] - 1))
            graph[edge[1]].add(intArrayOf(edge[0], edge[2] - 1))
        }

        // 预处理深度、倍增祖先节点、倍增路径信息
        val m = 32 - Integer.numberOfLeadingZeros(n - 1)
        val depth = IntArray(n)
        val parent = Array(n) { IntArray(m) { -1 }} // parent[i][j] 表示 i 的第 2^j 个父节点
        val cnt = Array(n) { Array(m) { IntArray(U) }} // cnt[i][j] 表示 <i - 2^j> 个父节点的路径信息
        
        fun dfs(i: Int, par: Int) {
            for ((to, w) in graph[i]) {
                if (to == par) continue // 避免回环
                depth[to] = depth[i] + 1
                parent[to][0] = i
                cnt[to][0][w] = 1
                dfs(to, i)
            }
        }

        dfs(0, -1) // 选择 0 作为根节点

        // 预处理倍增
        for (j in 1 until m) {
            for (i in 0 until n) {
                val from = parent[i][j - 1]
                if (-1 != from) {
                    parent[i][j] = parent[from][j - 1]
                    cnt[i][j] = cnt[i][j - 1].zip(cnt[from][j - 1]) { e1, e2 -> e1 + e2 }.toIntArray()
                }
            }
        }

        // 查询
        val q = queries.size
        val ret = IntArray(q)
        for ((i, query) in queries.withIndex()) {
            var (x, y) = query
            // 特判
            if (x == y || parent[x][0] == y || parent[y][0] == x) {
                ret[i] = 0
            }
            val w = IntArray(U) // 记录路径信息
            var path = depth[x] + depth[y] // 记录路径长度
            // 先跳到相同高度
            if (depth[y] > depth[x]) {
                val temp = x
                x = y
                y = temp
            }
            var k = depth[x] - depth[y]
            while (k > 0) {
                val j = Integer.numberOfTrailingZeros(k) // 二进制分解
                w.indices.forEach { w[it] += cnt[x][j][it] } // 记录路径信息
                x = parent[x][j] // 向上跳 2^j 个父节点
                k = k and (k - 1)
            }

            // 再使用倍增找 LCA
            if (x != y) {
                for (j in m - 1 downTo 0) { // 最多跳 m - 1 次
                    if (parent[x][j] == parent[y][j]) continue // 跳上去相同就不跳
                    w.indices.forEach { w[it] += cnt[x][j][it] } // 记录路径信息
                    w.indices.forEach { w[it] += cnt[y][j][it] } // 记录路径信息
                    x = parent[x][j]
                    y = parent[y][j] // 向上跳 2^j 个父节点
                }
                // 最后再跳一次就是 lca
                w.indices.forEach { w[it] += cnt[x][0][it] } // 记录路径信息
                w.indices.forEach { w[it] += cnt[y][0][it] } // 记录路径信息
                x = parent[x][0]
            }
            // 减去重链长度
            ret[i] = path - 2 * depth[x] - w.max()
        }
        return ret
    }
}

复杂度分析:

  • 时间复杂度:O(nlgn·U) 预处理的时间复杂度是 O(nlgn·U),单次查询的时间是 O(lgn·U)
  • 空间复杂度:O(nlgn·U) 预处理倍增信息空间。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,839评论 6 482
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,543评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 153,116评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,371评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,384评论 5 374
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,111评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,416评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,053评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,558评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,007评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,117评论 1 334
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,756评论 4 324
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,324评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,315评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,539评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,578评论 2 355
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,877评论 2 345

推荐阅读更多精彩内容