leetcode 第 315 场算法比赛

零、背景

这次比赛非常水，这是最有可能进去前 50 名的机会。
但是除了意外，最后一题读错题了，最终排名 123 名。

一、与对应负数同时存在的最大正整数

题意：给一个数组，求一个数字与符号相反的数字同时出现在数组中的最大整数。

思路：数组存在 set 中，循环判断即可。

二、 反转之后不同整数的数目

题意：给一个数组，所有数字按十进制进行翻转，求翻转后的数字集合大小。

思路：按照题意翻转，去重即可。

三、反转之后的数字和

题意：问是否存在一个数字， 使得数字与十进制翻转的数字之和等于目标数字。

思路：预处理所有小于等于目标数字的翻转之和，存入 set 中，直接判断即可。

四、统计定界子数组的数目

题意：给一个数组，问存在多少个子数组，其中子数组的最大值与最小值等于输入的值。

思路：双指针。

显然，如果一个值小于最小值或者大于最大值，不会有子数组覆盖这个值的位置。
所以，两个最值将数组划分为若干粗粒度的子数组，子数组内的值都在这个最值区间内。

对于每个粗粒度的子数组，从左到右扫描，记录两个最值最后一次出现的位置。
假设起始位置是 L， 扫描到 R，最小值最后一次出现的位置是 minPos，最大值最后一次出现的位置是 maxPos。
则以 R 为有边界，符合要求的子数组个数是 min(minPos, maxPos) - L + 1。

解释：题意要求子数组必须包含最小值和最大值，则最短的以 R 为有边界的子数组是 [min(minPos, maxPos), R]。
由于[L, R]内的值都在最值之内，所以所有前缀加进来都符合要求。

五、最后

这次比赛题目比较简单。

加油，算法人。

《完》

-EOF-

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