LeetCode笔记：Biweekly Contest 87
LeetCode笔记：Biweekly Contest 87
0. 小结
这一次题目倒是都搞定了，不过没有参加比赛，赛后做题终归是比较轻松一些。错了挺多次的，基本算是面向bug做题了，所以整体还是感觉有点伤，不过anyway，能把4道题都搞定了就好。
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题就是一个分类讨论问题，把日期转换一下然后看一下交叉的时间范围就行了。
2. 代码实现
给出python代码实现如下：
class Solution:
def countDaysTogether(self, arriveAlice: str, leaveAlice: str, arriveBob: str, leaveBob: str) -> int:
days = [0] + list(accumulate([31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]))
def get_date(date):
month, day = date.split("-")
return days[int(month)-1] + int(day)
arriveAlice = get_date(arriveAlice)
leaveAlice = get_date(leaveAlice)
arriveBob = get_date(arriveBob)
leaveBob = get_date(leaveBob)
if arriveAlice <= arriveBob:
if arriveBob <= leaveAlice:
return min(leaveBob, leaveAlice)-arriveBob + 1
else:
return 0
else:
if leaveBob >= arriveAlice:
return min(leaveBob, leaveAlice)-arriveAlice + 1
else:
return 0提交代码评测得到：耗时33ms，占用内存13.9MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题就是一个贪婪算法，首先对player和trainer进行一下排序，然后将每一个player分配给第一个能够达到标准的trainer，然后看看有个player能够分配到trainer即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def matchPlayersAndTrainers(self, players: List[int], trainers: List[int]) -> int:
players = sorted(players)
trainers = sorted(trainers)
n, m = len(players), len(trainers)
i, j = 0, 0
res = 0
while i < n:
while j < m and players[i] > trainers[j]:
j += 1
if j >= m:
break
res += 1
i += 1
j += 1
return res提交代码评测得到：耗时1067ms，占用内存30.1MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题思路上就是一个倒序的滑动窗口控制，对于每一个新加入的元素，考察滑动窗口的右边缘最靠近可以靠近到哪个位置，然后更新位置即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def smallestSubarrays(self, nums: List[int]) -> List[int]:
def get_digits(x):
return [int(d) for d in bin(x)[2:][::-1]]
res = [0 for _ in nums]
digits = [0 for _ in range(32)]
n = len(nums)
i, j = n-1, n-1
while i >= 0:
d = get_digits(nums[i])
for k, x in enumerate(d):
digits[k] += x
while j > i:
d = get_digits(nums[j])
if any(x == y == 1 for x, y in zip(digits, d)):
break
for k, x in enumerate(d):
digits[k] -= x
j -= 1
res[i] = j-i+1
i -= 1
return res 提交代码评测得到：耗时3063ms，占用内存28.9MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题就是一个排序问题。
如果cashback能够cover住cost，那么经过一次交易之后现金总量是会增加的，因此要让任意的顺序的操作都能够实现，最坏的情况一定是先完成所有的cover不住的那部分交易，然后再完成所有能够cover住的交易。
而在能够cover住的交易，后续手上的现金已经是持续增加的，因此，最糟糕的情况一定是先完成需要的cost最大的交易，此后所有的其他交易一定都能够完成。
而在cover不住的那部分操作，要保证每一个操作都能够完成，手上的现金必须cover住所有的亏空，且要保证每一个时刻都需要cover住亏空，那么就需要让每一个时刻能够补回的现金流最小。
综上，我们重新排序之后就能够获得最终的答案了。
2. 代码实现
给出python代码实现如下：
class Solution:
def minimumMoney(self, transactions: List[List[int]]) -> int:
def order(cost, cashback):
if cashback - cost <= 0:
return (0, cashback, cost)
else:
return (1, -cost, cashback)
transactions = sorted(transactions, key = lambda x: order(*x))
need = 0
remain = 0
for cost, cashback in transactions:
if remain < cost:
need += cost - remain
remain = cashback
else:
remain += cashback - cost
return need提交代码评测得到：耗时2204ms，占用内存63MB。