leetcode 第 365 场算法比赛

零、背景

最近发现 Leetcode 真会玩，两道题一模一样，只是数据范围不一样。

以后可以指出两道题，根据数据范围拆分为 4 道题，就是一场比赛了。

leetcode 仓库地址：https://github.com/tiankonguse/leetcode-solutions

比赛代码：contest/3/365

一、有序三元组中的最大值 I

题意：给一个数组，选择三个下标 i,j,k，使得 i<j<k 且 (nums[i] - nums[j]) * nums[k] 最大。
数据范围：n<=100

思路：数据范围不大，三层循环枚举即可。
复杂度: O(n^3)

二、有序三元组中的最大值 II

题意：给一个数组，选择三个下标 i,j,k，使得 i<j<k 且 (nums[i] - nums[j]) * nums[k] 最大。
数据范围：n<=10^5

思路：数字的值都是正整数，要是目标最大，j 确定后，显然需要使得 nums[i] 和 nums[k] 都尽量的大。

可以预处理做每个下标左边和右边的最大值，然后枚举 j 计算出最大值即可。
复杂度: O(n)

三、无限数组的最短子数组

题意：给一个数组，数组收尾相连组成一个无限数组。
问如何选才能选出子数组和为 target，如果可以，返回子数组的最短长度。
数据范围：n<=10^5

思路：

步骤1：如果子数组和 target 大于原数组的和，说明需要选择几个完整的原数组，需要减去，使得目标和不大于原数组的和。

步骤2：答案显然是从原始数组的某个位置开始，即有 n 个选择，每个选择的长度不大于 n。

如何判断子数组和为 target 是否存在呢？
子数组和可以转化为两个前缀子数组的差集。
前缀和储存在 hash 表中，枚举右边界，判断左边界是否存在即可。
复杂度：O(n)

四、有向图访问计数

题意：给一个有向图，每个顶点有一个出边，问每个顶点可以到达多少个顶点。

思路：每个顶点只有一个出边，意味着对于一个联通图，只有一个环，连通图环之外的顶点都是指向环的路径。

所以我们可以递归找到连通图中的环并计算出环大小。
环上顶点的答案就是环的大小。
链上顶点的答案就是下个顶点答案加一。

怎么找到环呢？
递归是打上标记，当遇到标记时代表有环。
如何计算环大小呢？标记可以使用负数表示，每递归一次标记减一，这样两个标记相减就是环的大小。

五、最后

这次比赛比较简单，不过国庆了，做题的人应该比较少吧。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code