2873. 有序三元组中的最大值 I
核心思想:由于这题数据范围比较小,直接枚举i,j,k即可。
2874. 有序三元组中的最大值 II
核心思想:这题是在2873题目的基础上将数据范围进行了增加,意味着我们需要对上面的代码进行优化。两种优化方法,第一种优化方法是枚举nums[j],然后求出前后缀,第二种优化方法是枚举nums[k],维护最大的(nums[i] - nums[j]),代码注释了解题思路。
方法一
方法二
2875. 无限数组的最短子数组
核心思想:滑动窗口+分类讨论。其实这题就是问你一个nums,求出nums中最短的满足和等于target的子数组,唯一不一样的地方是,这里的nums你可以进行延展。这里就需要根据target的大小进行分类讨论了,结论:如果target的和小于nums的和s,那么只需要两个nums排列即可做出来,如果target的和大于等于nums的和s,那么需要把target%s即从target中把s删除,统计删除的s个数即可,然后现在的target又变成了target小于s的情况了,又可以用方法一做了。具体可以看灵神的题解。
2876. 有向图访问计数
核心思想:从环上的根节点去枚举,这里借用一下灵神画的图。正常情况下是从树枝上的节点往环节点去跑,比如这里环上有三个节点,最左边这个节点到环上节点跑了3个节点加起来总共6个节点,然后它的儿子就是5个节点。这里我们不这样跑,我们反向跑,环上的节点是3个节点,然后环上节点的父节点就是4个节点,父亲的父亲就是5个节点,以此类推。所以核心就变成,一,找出环上的节点,这里环不止一个;二,从环上节点去反向跑。找环上的节点需要用拓扑排序来删掉树枝点,反向跑把环上的节点当作跟节点去求深度。