leetcode 第 309 场算法比赛

零、背景

这次比赛比以往的稍微难一些，根据难度就可以看出招聘公司的算法要求吧。

一、检查相同字母间的距离

题意：给一个字符串，每个字母恰好出现两次。
现在提前预测了出现的字母的间距，问间距是否正确。

思路：循环计算字母的间距，判断是否正确即可。

暴力方法：每个字母单独判断。
复杂度：O(n^2)

标记法：字母第一次出现时记录位置，第二次出现时判断距离。
复杂度：O(n)

二、恰好移动 k 步到达某一位置的方法数目

题意：坐标轴上给一个起始位置和目标位置。
每次移动可以左右移动一格，问移动 K 次后，能够到达目标位置的路径数。

思路：典型的动态规划题。

由于可能出现负数，可以提前把起始位置和目标位置左移，使得最坏情况下也不可能出现负数即可。

状态转移方程：f(i, k) = f(i-1, k-1) + f(i+1, k+1)

三、最长优雅子数组

题意：给一个数组，如果某个子数组的任意两个元素的与运算值是0，则这个子数组是优雅子数组。
求最长的优雅子数组。

思路：任意两个元素与运算是0，以为二进制中不能有相同位值为1。
进而可以得出结论，优雅子数组的所有元素的二进制中，1 出现的位数互不相同。

根据上面的结论，算法也就明确了。

维护一个满足要求的滑动窗口，窗口内的所有值求或运算。
每次加入新的元素之前，先判断是否满足要求，不满足就删除最左边的元素，直到满足。

复杂度：O(n)

四、会议室 III

题意：给 n 个房间以及若干会议， 每个会议有一个独特的开始时间与结束时间。

按照下面的规则为会议分配房间号。

1）每次分配空闲的编号最小的房间。
2）如果会议时间到了，但是没有房间，则延期，直到有空闲房间。会议的持续时间不变。
3）如果未来又有空闲房间了，优先分配原始会议开始时间最小的会议。

问按照这个规则进行开会，最终哪个房间开得会议最多，如果存在多个，返回编号最小的那个。

思路：很容易发现，是个最小堆的问题，关键是如何组织数据结构。

我定义了三个最小堆。

1）空闲房间最小堆，用于快速分配与回收房间。
2）使用房间最小堆，用于判断最早的开完会的房间，显然需要储存结束时间和房间号。
3）等待会议最小堆，储存开始时间与会议时长。

之后就是按照时间轴，分配会议了。

1）如果当前时刻有会议开完了，则回收房间。
2）如果当前时刻有会议需要开，且有空闲房间，则进行分配。
3）时间轴前进：如果房间满了，则时间快进到下次回收房间的时刻，否则去回收房间时间与下次会议时间的最小值。

注意实现：时间轴可能超过 32位整数最大值，需要使用 64位整数。

五、最后

这次比赛后两题都挺有意思的，尤其是最后一题。

加油，算法人。

《完》

-EOF-

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