date
type
status
slug
summary
tags
category
password
icon
这篇博客将会分析LeetCode周赛365的四道题。
 

2873 & 2874. Maximum Value of an Ordered Triplet II

 
给定一个下标从 0 开始的整数数组 nums
请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中,找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数,则返回 0
下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k]
示例:
 

分析:

本次周赛的第一道与第二道的题干相同,区别在于对时间复杂度的要求上。
初见此题,很容易想到一个三重循环:
 
对第一道题,这个的算法就足够了。但对于第二道题,这个算法会超时,这就要求我们改进算法。
事实上,我们可以把算法的时间复杂度改进到
 
在这里,我们考虑使用Kadane算法的思路
Kadane算法简介
Kadane算法,也被称为最大子数组和算法,是一个有效地求解一维数组中最大连续子数组和的算法。
这是算法的基本原理:
  1. 遍历数组,维护两个变量:当前最大子数组和(currentMax)和全局最大子数组和(globalMax)。
  1. 对于每个元素,更新currentMaxglobalMax
  1. 最终的globalMax即为整个数组中的最大子数组和。
 
在Kadane算法中,我们维护的两个变量为当前最大子数组和,与全局最大子数组和,而在这道题中,我们需要维护三个变量:
  1. 当前最大结果 max_ans( ≈ max((nums[i] - nums[j]) * nums[k]))
  1. 当前最大差 max_delta( ≈ max(nums[i] - nums[j]))
  1. 当前最大数 max_a( ≈ max(nums[i]))
如何维护这三个变量?
我们先写一个for循环,再看看如何维护:
 
在这里,我们需要弄清楚两件事:
  1. 如何更新这三个变量
  1. 按照怎样的顺序更新这三个变量
 
如何更新这三个变量
max_ans记录当前最大结果,因此max_ans = max(max_ans, max_delta * a)
max_delta记录当前最大差,当前最大差自然就是当前最大数减去当前最小数。因此max_delta = max(max_delta, max_a - a).
max_a记录当前最大数,因此max_a = max(max_a, a)
按照怎样的顺序更新这三个变量
考虑一个具体场景,其中a是nums的最后一个元素。在这种情况下,a只能作为公式((nums[i] - nums[j]) * nums[k])中的nums[k]。而更新max_delta是把a作为nums[j]来考虑,更新max_a则是把a视为nums[i]。
由于我们现在考虑的是a作为nums[k],所以我们首先需要更新的是max_ans,其次才是max_delta和max_a。尽管在更新max_delta和更新max_a时还是把a视作了nums[i]和nums[j],但在这个具体场景下,循环已经结束,因此对max_delta和max_a的更新不会对答案,即max_ans产生影响。因此,更新max_ans应该在其他更新之前进行。
同理,我们可以推出,更新顺序为:max_ans → max_delta → max_a
 
这样,我们就能写出代码了:
LeetCode 53. Maximum Subarray可以用同样的思路解决,请读者自行尝试。
 

2875. Minimum Size Subarray in Infinite Array

 
给定一个下标从 0 开始的数组 nums 和一个整数 target
下标从 0 开始的数组 infinite_nums 是通过无限地将 nums 的元素追加到自己之后生成的。
请你从 infinite_nums 中找出满足 元素和 等于 target最短 子数组,并返回该子数组的长度。如果不存在满足条件的子数组,返回 -1
示例 1:
 

分析:

初见这道题,我有一种强烈的用sum(nums)去模target的冲动。为此,我们可以把ans分为两部分,商(quo)和余数(rem)。这让我们把target控制在一个较小范围内,有利于后续操作的进行。
 
接下来,我们只需要实现subarraySum即可,该函数返回在nums中的和为target的连续(可以头尾相接)子数组的最短长度。
样例:
nums = [1, 1, 1, 4, 2]
target = 3
subarraySum返回2,因为符合条件的子数组有[1, 1, 1]和[2, 1](头尾相接),最短长度是2.
 
为此,我们有两种思路:
  1. 滑动窗口(双指针)
  1. 前缀和
 

滑动窗口(双指针)

首先,我们有左指针与右指针,当前窗口的长度可以在指针移动时进行更新。
其次,我们要考虑如何计算当前窗口的数的总和。我们考虑在指针移动时对delta进行更新,从而让delta记录当前的窗口的数的总和与target的差值。如果delta变为0,说明当前窗口的数的总和与target的值相等。
那么如何更新delta?一个自然的思路是:
最后,我们需要考虑循环的结束条件。结束条件有两种,
第一种是右指针已经经过了整个数组两遍。这是由于target在取模后总是小于sum(nums),因此我们不必继续移动右指针;
第二种是left == n。这是因为nums中的数都是正数,从而不会出现left移动的步数比right移动的步数更多的情形,因此当left == n时再次移动left会进行重复计算,这没有意义。
以下是代码:
 

前缀和

前缀和的基本思想如下: sum(nums[i:j]) = sum(nums[:j]) - sum(nums[:i])
我们只需要把所有的sum(nums[:k])保存起来存入一个字典中(耗时O(len),其中len为整个数组的长度),就能在O(1)时间内求出任何一个连续子数组的和。
考虑到我们需要的子数组可能是首尾相接的连续数组,令extended_nums = nums * 2即可。
这让[1, 2, 3]变成[1, 2, 3, 1, 2, 3]。
根据以上思想,我们就可以写出代码:
 
综上,我们就解决了这道题:
 

2876. Count Visited Nodes in a Directed Graph

 
现有一个有向图,其中包含 n 个节点,节点编号从 0n - 1 。此外,该图还包含了 n 条有向边。
给定一个下标从 0 开始的数组 edges ,其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的边。
想象在图上发生以下过程:
  • 你从节点 x 开始,通过边访问其他节点,直到你在 此过程 中再次访问到之前已经访问过的节点。
返回数组 answer 作为答案,其中 answer[i] 表示如果从节点 i 开始执行该过程,你可以访问到的不同节点数。
示例 1:
notion image
 

分析:

n个节点n条有向边,每个节点出发一条边,说明图中存在有向环,且不存在两个环有公共节点。同时每个节点或是在一个环上,或是与一个环上的某个节点连通。(这几个命题相对直观,因此下面给出的分析不很严谨,请见谅。)
对上面的命题的分析
  1. 图中存在有向环:由于每个节点都有一条出边,且总共有 n 条边,所以必然会在某个点形成一个环。即,如果我们从任何一个节点开始遍历,由于没有“终点”(没有任何一个节点是没有出边的),所以总会回到之前遇到过的节点,形成环。
  1. 不存在两个环有公共节点:考虑反证法。假设存在两个有向环 A 和 B 共享一个公共节点 x。由于 x 在 A 中是一个环,并且 x 只有一个出边,那么 x 在 B 中就不能形成一个环。这与假设矛盾。所以,不可能有两个有向环共享一个节点。
  1. 每个节点或是在一个环上,或是与一个环上的某个节点连通:对于不在环上的任何节点,由于它有一条出边且总共有 n 条边,它必然会指向一个其他节点。如果这个其他节点不在环上,它也会指向另一个节点。这种情况下,我们有一个由有向边组成的路径。由于不存在“终点”并且总共只有 n 个节点,这个路径最终必须进入一个已知的有向环。
 
 
对任何一个环cycle,在环上的节点的ans即为该环的总长度。对不在环上但与环上的某个节点target连通的节点A,假设它到target的路径上共有k个节点(包括A但不包括target),那么节点A的ans为(k + 环的总长度)。
由此可知,我们可以先找到所有的环及环上节点,更新它们的ans,再从环上的节点向外不断更新通向环的节点的ans即可。(可以视作topological sort)
 
我们可以通过以下操作来找到图中的环:
  1. 记录所有的节点的indegree
  1. 把indegree为0的节点存入队列中
  1. 依次移除这些indegree为0的节点,把这些节点存入stack,并更新它们neighbor的indegree, 如果neighbor的indegree变为0,把它加入队列。
  1. 重复操作直到队列为空。
  1. 此时所有indegree不为0的节点即为在环上的节点。
对第五步的解释
对环上的任何一个节点,它的indegree至少为1,从而不会进入队列。 而对不在环上的任何一个节点,考虑所有的以它为终点,以一个indegree为0的节点为起点的路径,这些路径的长度一定会最终变为0(因为indegree为0的节点会被不断移除,使得路径长度缩短),从而这个节点的indegree也会变为0,从而该节点会被加入队列。
 
综上,我们可以按照以下的步骤来完成我们的算法
  1. 找到环(node_in_cycles)
  1. 更新在环上的节点的answer
  1. 根据stack来处理不在环上的节点的answer。answer = 1 + answer[后继节点]
 
CS188 Reinforcement Learning笔记费马小定理的组合证明