LeetCode笔记：Biweekly Contest 51 比赛记录
LeetCode笔记：Biweekly Contest 51 比赛记录
- LeetCode笔记：Biweekly Contest 51
- 0. 赛后总结
- 1. 题目一
- 1. 解题思路
- 2. 代码实现
- 2. 题目二
- 1. 解题思路
- 2. 代码实现
- 3. 题目三
- 1. 解题思路
- 2. 代码实现
- 4. 题目四
- 1. 解题思路
- 2. 代码实现
0. 赛后总结
五一第一天，结果就水过去了，啥正事都没干，健身房也没去，晚上的比赛也偷懒没参加，真的是负罪感满满……
今天倒是试着做了一下，不过没有做模拟竞赛，所以时间上估计就是超时严重，不过万幸的是题目总算还是做出来了，也算是不幸中的大幸了……
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
第一题按惯例依然没啥难度，把奇数位的数全部按照给定的变换进行一下操作就行了。
2. 代码实现
给出python代码实现如下：
class Solution:
def replaceDigits(self, s: str) -> str:
n = len(s)
res = ""
for i in range(n):
if i % 2 == 0:
res += s[i]
else:
res += chr(ord(s[i-1]) + int(s[i]))
return res提交代码评测得到：耗时48ms，占用内存14.2MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
第二题的思路倒是挺直接的，用堆排或者有序列表都可以，反正只要维护当前可用的位子有序，能够不断地给出最小的可用位置即可。
2. 代码实现
这里，我们使用的方式使用二分搜索维持有序列表。
给出python代码实现如下：
class SeatManager:
def __init__(self, n: int):
self.avaliable = [i+1 for i in range(n)]
def reserve(self) -> int:
seat = self.avaliable.pop(0)
return seat
def unreserve(self, seatNumber: int) -> None:
bisect.insort(self.avaliable, seatNumber)
# Your SeatManager object will be instantiated and called as such:
# obj = SeatManager(n)
# param_1 = obj.reserve()
# obj.unreserve(seatNumber)提交代码评测得到：耗时6200ms，占用内存42.5MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这题一开始看错题目了，结果就做错了，惨的一逼……
不过其实这题挺简单的，我们首先将原数组进行排序，由于元素只能够执行减运算，因此考察第i个元素，其可取的最大值就是这个值本身和其上一个值+1之间的较小数。
因此，我们可以在 O(N)的算法复杂度内找到最终可以取到的最大值，而排序的算法复杂度是 O(N⋅logN)，因此整体的算法复杂度就是 O(N⋅logN)。
2. 代码实现
给出python代码实现如下：
class Solution:
def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:
arr = sorted(arr)
n = len(arr)
pre = 0
for i in range(n):
pre = min(pre+1, arr[i])
return pre提交代码评测得到：耗时632ms，占用内存24.3MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题讲真绕了挺多弯路的，最后万幸倒是做出来了。
问题的难点在于对每一个query都需要重新按照size对所有的房间进行一次过滤，然后再针对prefer的index按照绝对值进行一次排序。
因此，这就要求其即保有一定的size方面的顺序，又需要保持index的顺序信息。
一开始就想同时这两方面的信息，然后就很难，后来转换了一下思路，我们先将query按照size进行排序，这样的话可用房间的变化就是单向的，只增不减，这样我们就可以在 O(N)的算法复杂度内对所有的query进行实现。
而此时对于query，我们不再需要size信息，只需要index信息即可，此时，我们只需要维持index有序就能够在logN算法复杂度内完成每一次query的查询。
综上，整体的算法复杂度就是 O(N⋅logN)。
2. 代码实现
给出python代码实现如下：
class Solution:
def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:
queries = sorted([(size, pid, idx) for idx, (pid, size) in enumerate(queries)], reverse = True)
res = [-1 for _ in queries]
rooms = sorted(rooms, key=lambda x: x[1], reverse=True)
i, n = 0, len(rooms)
cache = []
for size, pid, idx in queries:
while i < n and rooms[i][1] >= size:
bisect.insort(cache, rooms[i][0])
i += 1
if len(cache) == 0:
continue
sid = bisect.bisect_left(cache, pid)
if not (sid == 0 or sid == len(cache)):
res[idx] = cache[sid-1] if abs(cache[sid-1] - pid) <= abs(cache[sid] - pid) else cache[sid]
elif sid == 0:
res[idx] = cache[sid]
else:
res[idx] = cache[sid-1]
return res提交代码评测得到：耗时2044ms，占用内存49.2MB。