LeetCode 周赛上分之旅 #49 再探内向基环树

LeetCode 周赛 365

T1. 有序三元组中的最大值 I(Easy)

  • 标签:模拟、前后缀分解、线性遍历

T2. 有序三元组中的最大值 II(Medium)

  • 标签:模拟、前后缀分解、线性遍历

T3. 无限数组的最短子数组(Medium)

  • 标签:滑动窗口

T4. 有向图访问计数(Hard)

  • 标签:内向基环树、拓扑排序、DFS

T1. 有序三元组中的最大值 I(Easy)

https://leetcode.cn/problems/maximum-value-of-an-ordered-triplet-i/description/

同 T2。


T2. 有序三元组中的最大值 II(Medium)

https://leetcode.cn/problems/maximum-value-of-an-ordered-triplet-ii/description/

问题分析

初步分析:

  • 问题目标: 构造满足条件的合法方案,使得计算结果最大;
  • 问题条件: 数组下标满足 i < j < k 的三位数;
  • 计算结果: (nums[i] - nums[j]) * nums[k]

思考实现:

思考优化:

为了使得计算结果尽可能大,显然应该让乘法的左右两部分尽可能大。对于存在多个变量的问题,一个重要的技巧是 「固定一个,思考另一个」 ,这就容易多了。

  • 固定 j 为了让结果更大,应该找到 nums[j] 左边最大的 nums[i] 和右边最大的 nums[k] 组合,时间复杂度是 O(n^2)。我们也可以使用前后缀分解预处理出来,这样时间复杂度就是 O(n)
  • 固定 k 同理,固定 k 寻找应该找到左边使得 nums[i] - nums[j] 最大的方案,这可以实现线性时间和常量空间。

题解一(枚举)

枚举所有方案,记录最优解。

class Solution {
    fun maximumTripletValue(nums: IntArray): Long {
        var ret = 0L
        val n = nums.size
        for (i in 0 until n) {
            for (j in i + 1 until n) {
                for (k in j + 1 until n) {
                    ret = max(ret, 1L * (nums[i] - nums[j]) * nums[k])
                }
            }
        }
        return ret
    }
}

复杂度分析:

  • 时间复杂度:O(n^3)
  • 空间复杂度:O(1)

题解二(前后缀分解)

预处理出每个位置前后的最大值,再枚举 nums[j] 记录最优解。

class Solution {
    fun maximumTripletValue(nums: IntArray): Long {
        val n = nums.size
        val preMax = IntArray(n)
        var sufMax = IntArray(n)
        for (i in 1 until n) {
            preMax[i] = max(preMax[i - 1], nums[i - 1])
        }
        for (i in n - 2 downTo 0) {
            sufMax[i] = max(sufMax[i + 1], nums[i + 1])
        }
        return max(0, (1 .. n - 2).maxOf { 1L * (preMax[it] - nums[it]) * sufMax[it] })
    }
}

复杂度分析:

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

题解三(线性遍历)

线性遍历 nums[k] 并记录 (nums[i] - nums[j]) 的最大值,记录最优解。

class Solution {
    fun maximumTripletValue(nums: IntArray): Long {
        val n = nums.size
        var ret = 0L
        var maxDelta = 0
        var maxI = 0
        for (e in nums) {
            ret = max(ret, 1L * maxDelta * e)
            maxDelta = max(maxDelta, maxI - e)
            maxI = max(maxI, e)
        }
        return ret
    }
}
class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        ret = maxDelta = maxI = 0
        for e in nums:
            ret = max(ret, maxDelta * e)
            maxDelta = max(maxDelta, maxI - e)
            maxI = max(maxI, e)
        return ret
class Solution {
public:
    long long maximumTripletValue(vector<int> &nums) {
        long long ret = 0;
        int max_delta = 0, max_i = 0;
        for (int e : nums) {
            ret = max(ret, (long long) max_delta * e);
            max_delta = max(max_delta, max_i - e);
            max_i = max(max_i, e);
        }
        return ret;
    }
};

复杂度分析:

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

T3. 无限数组的最短子数组(Medium)

https://leetcode.cn/problems/minimum-size-subarray-in-infinite-array/description/

问题分析

nums 数组的整体元素和为 s,考虑 target 的两种情况:

  • 对于 target 很小的情况(小于数组整体和 s):这是很简单的滑动窗口问题;
  • 对于 target 较大的情况(大于等于数组的整体和 s):那么最小长度中一定包含整数倍的 s,以及某个 nums 的子数组。
class Solution {
    fun minSizeSubarray(nums: IntArray, t: Int): Int {
        val n = nums.size
        val s = nums.sum()
        val k = t % s
        // 同向双指针
        var left = 0
        var sum = 0
        var len = n
        for (right in 0 until 2 * n) {
            sum += nums[right % n]
            while (sum > k) {
                sum -= nums[left % n]
                left ++
            }
            if (sum == k) len = min(len, right - left + 1)
        }
        return if (len == n) -1 else n * (t / s) + len
    }
}

复杂度分析:

  • 时间复杂度:O(n) 最大扫描 2 倍数组长度;
  • 空间复杂度:仅使用常量级别空间。

T4. 有向图访问计数(Hard)

https://leetcode.cn/problems/count-visited-nodes-in-a-directed-graph/description/

问题分析

初步分析:

对于 n 个点 n 条边的有向弱连通图,图中每个点的出度都是 1,因此它是一棵 「内向基环树」。那么,对于每个点有 2 种情况:

  • 环上节点:绕环行走一圈后就会回到当前位置,因此最长访问路径就是环长;
  • 树链节点:那么从树链走到环上后也可以绕环行走一圈,因此最长访问路径就是走到环的路径 + 环长。

思考实现:

  • 只有一个连通分量的情况: 那么问题就相对简单,我们用拓扑排序剪去树链,并记录链上节点的深度(到环上的距离),最后剩下的部分就是基环;
  • 有多个连通分量的情况: 我们需要枚举每个连通分量的基环,再将基环的长度累加到该连通分量的每个节点。

题解(拓扑排序 + DFS)

  • 第一个问题:将基环的长度累加到该连通分量的每个节点

拓扑排序减去树链很容易实现,考虑到我们这道题在找到基环后需要反向遍历树链,因此我们考虑构造反向图(外向基环树);

  • 第二个问题:找到基环长度

在拓扑排序后,树链上节点的入度都是 0,因此入度大于 0 的节点就位于基环上。枚举未访问的基环节点走 DFS,就可以找到该连通分量的基环。

class Solution {
    fun countVisitedNodes(edges: List<Int>): IntArray {
        // 内向基环树
        val n = edges.size
        val degree = IntArray(n)
        val graph = Array(n) { LinkedList<Int>() }
        for ((x,y) in edges.withIndex()) {
            graph[y].add(x)
            degree[y]++ // 入度
        }
        // 拓扑排序
        val ret = IntArray(n)
        var queue = LinkedList<Int>()
        for (i in 0 until n) {
            if (0 == degree[i]) queue.offer(i)
        }
        while(!queue.isEmpty()) {
            val x = queue.poll()
            val y = edges[x]                                         
            if (0 == -- degree[y]) queue.offer(y)
        }

        // 反向 DFS
        fun rdfs(i: Int, depth: Int) {
            for (to in graph[i]) {
                if (degree[to] == -1) continue
                ret[to] = depth
                rdfs(to, depth + 1)
            }
        }
        
        // 枚举连通分量
        for (i in 0 until n) {
            if (degree[i] <= 0) continue
            val ring = LinkedList<Int>()
            var x = i
            while (true) {
                degree[x] = -1
                ring.add(x)
                x = edges[x]
                if (x == i) break
            }
            for (e in ring) {
                ret[e] = ring.size
                rdfs(e, ring.size + 1)
            }
        }
        return ret
    }
}

复杂度分析:

  • 时间复杂度:O(n) 拓扑排序和 DFS 都是线性时间;
  • 空间复杂度:O(n) 图空间和队列空间。

题解二(朴素 DFS)

思路参考小羊的题解。

我们发现这道题的核心在于 「找到每个基环的节点」 ,除了拓扑排序剪枝外,对于内向基环树来,从任何一个节点走 DFS 走到的最后一个节点一定是基环上的节点。

在细节上,对于每个未访问过的节点走 DFS 的结果会存在 3 种情况:

  • 环上节点:刚好走过基环;
  • 树链节点:走过树链 + 基环。
  • 还有 1 种情况:DFS 起点是从树链的末端走的,而前面树链的部分和基环都被走过,此时 DFS 终点就不一定是基环节点了。这种情况就同理从终点直接反向遍历就好了,等于说省略了处理基环的步骤。
class Solution {
    fun countVisitedNodes(edges: List<Int>): IntArray {
        val n = edges.size
        val ret = IntArray(n)
        val visit = BooleanArray(n)
        for (i in 0 until n) {
            if (visit[i]) continue
            // DFS
            val link = LinkedList<Int>()
            var x = i
            while (!visit[x]) {
                visit[x] = true
                link.add(x)
                x = edges[x]
            }
            if (ret[x] == 0) {
                val depth = link.size - link.indexOf(x) // (此时 x 位于基环入口)
                repeat(depth) {
                    ret[link.pollLast()] = depth
                }
            }
            var depth = ret[x]
            while (!link.isEmpty()) {
                ret[link.pollLast()] = ++depth
            }
        }
        return ret
    }
}

复杂度分析:

  • 时间复杂度:O(n) DFS 都是线性时间;
  • 空间复杂度:O(n) 图空间和队列空间。

推荐阅读

LeetCode 上分之旅系列往期回顾:

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

推荐阅读更多精彩内容