leetcode 第 353 场算法比赛

零、背景

这次比赛休假回家了，没参加比赛。
周末了，有时间补上上次比赛的题解。

一、找出最大的可达成数字

题意：给两个数字 num 和 x， 每次操作 num 和 x 都可以加一或减一。
问最多操作 t 次时，给一个 num，x 的最大可能值是多少？

思路：x 要最大，显然是 num 加一，x 减一。
所以最大的 x 是 num + 2 * t。

二、达到末尾下标所需的最大跳跃次数

题意：给一个数组，从一个位置 i 可以跳到 j 的条件是 j>i && -target <= nums[j] - nums[i] <= target。
现在起始位置是第一个位置，问是否可以到达最后位置，以及到达的最大跳数。

思路：递推或者递归，以递推为例。

定义状态数组，含义是到达每个位置的最大跳数，默认值是 -1，代表不可到达。
从前到后处理每个位置，如果是可以到达的，则枚举计算后面可以到达的所有位置，并更新对应位置的最大跳数。

第一个位置的状态值为 0，按上面逻辑处理即可。

复杂度：O(n^2)

三、构造最长非递减子数组

题意：根据两个输入数组构造出一个输出数组，构造方法为两个输入数组相同位置选择一个当做输出数组的值。
问怎么构造输出数组，才能使得 最长非递减子数组的长度最长。

思路：动态规划。

非递减子数组翻译一下就是子数组保持有序性。

假设一个子数组前缀是有序的，对于下个元素，只需要与前缀的最后一个元素比较，即可判断是否可以得到更长的有序子数组。

故可以计算两个数组每个位置为后缀可以得到的最长有序子数组长度。
对于下个位置，分别与两个数组的上个位置比较，从而可以当前位置的最长有序子数组的长度。

复杂度：O(n)

四、使数组中的所有元素都等于零

题意：给一个数组，每次操作可以对长度为 k 的子数组的值都减一。
问是否可以在若干次操作后，将数组的值都设置为 0。

思路1：线段树。

从前到后判断当前位置的值 v，分三种情况。

1）v 小于 0，无解。
2）v 等于 0，跳过当前位置。
3）v 大于 0，选择当前位置为起始位置长度为 k 的子数组，减 k 次。

边界：如果当前位置值大于0，但到最后位置长度不足 k，则无解。

复杂度：O(n log(n))

思路2：差分。

一个子数组减 k，可以标记为左边界减 k，右边界加 k。
左边界直接储存在游标上。
右边界储存在一个差分数组上。

游标从左到右循环，从而计算出当前位置与游标的和 sum。
如果 sum 小于0，则没有答案。
如果 sum 等于0，则不需要选择子数组。

如果 sum 大于0，则代表需要选择 sum 个当前位置开始的长度为 k 的子数组。
游标减去 sum，子数组的右边界位置更新差分数组。

复杂度：O(n)

五、最后

这次比赛题目不难，最后一题我每次想到的都是线段树，结果都可以使用更简单的方法通过。

《完》

-EOF-

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