- LeetCode笔记：Weekly Contest 327
- 0. 做题感受
- 1. 题目一
- 1. 解题思路
- 2. 代码实现
- 3. 题目二
- 1. 解题思路
- 2. 代码实现
- 2. 题目三
- 1. 解题思路
- 2. 代码实现
- 4. 题目四
- 1. 解题思路
- 2. 代码实现
- 比赛链接：https://leetcode.com/contest/weekly-contest-327/
0. 做题感受
这次的题目一看大佬们的用时，最快的居然也花了将近30min，把我吓了一大跳，结果真正做下来就有点无语了，就是超级繁琐的各种分类讨论以及边界条件，难度倒是感觉还好，但是真要再做一遍估计还得去掉半条命，简直了……
1. 题目一
给出题目一的试题链接如下：
- 2529. Maximum Count of Positive Integer and Negative Integer
1. 解题思路
这一题有序数列的话其实可以二分找边界，不过我这边就比较暴力的直接遍历统计了一遍就是了……
2. 代码实现
给出python代码实现如下：
class Solution:def maximumCount(self, nums: List[int]) -> int:pos, neg = 0, 0for x in nums:if x < 0:neg += 1elif x > 0:pos += 1return max(pos, neg)
提交代码评测得到：耗时135ms，占用内存14.2MB。
3. 题目二
给出题目二的试题链接如下：
- 2530. Maximal Score After Applying K Operations
1. 解题思路
这一题其实就是不断地去最大元素进行操作，然后更新数组就行了。
问题就在于如何快速地更新数组以及取最大值，我是采用了堆排，不过全有序排序也问题不大就是了。
2. 代码实现
给出python代码实现如下：
class Solution:def maxKelements(self, nums: List[int], k: int) -> int:nums = [-x for x in nums]score = 0heapq.heapify(nums)for _ in range(k):x = -heapq.heappop(nums)score += xheapq.heappush(nums, - ceil(x/3))return score
提交代码评测得到：耗时1132ms，占用内存29.1MB。
2. 题目三
给出题目三的试题链接如下：
- 2531. Make Number of Distinct Characters Equal
1. 解题思路
这一题我这边的做法就是一个非常暴力的分类讨论，首先统计两个单词之中出现了那些字符，然后分别考察交换两个字符之后可能出现的情况，将所有情况分别枚举一边就行了……
2. 代码实现
给出python代码实现如下：
class Solution:def isItPossible(self, word1: str, word2: str) -> bool:cnt1 = Counter(word1)cnt2 = Counter(word2)diff = len(cnt1) - len(cnt2)for ch1 in cnt1:for ch2 in cnt2:if ch1 == ch2:change = 0elif cnt1[ch1] == 1 and cnt2[ch2] == 1:if cnt2[ch1] > 0 and cnt1[ch2] > 0:change = 0elif cnt2[ch1] > 0 and cnt1[ch2] == 0:change = 1elif cnt2[ch1] == 0 and cnt1[ch2] > 0:change = -1else:change = 0elif cnt1[ch1] == 1 and cnt2[ch2] > 1:if cnt2[ch1] > 0 and cnt1[ch2] > 0:change = -1elif cnt2[ch1] > 0 and cnt1[ch2] == 0:change = 0elif cnt2[ch1] == 0 and cnt1[ch2] > 0:change = -2else:change = -1elif cnt1[ch1] > 1 and cnt2[ch2] == 1:if cnt2[ch1] > 0 and cnt1[ch2] > 0:change = 1elif cnt2[ch1] > 0 and cnt1[ch2] == 0:change = 2elif cnt2[ch1] == 0 and cnt1[ch2] > 0:change = 0else:change = 1else:if cnt2[ch1] > 0 and cnt1[ch2] > 0:change = 0elif cnt2[ch1] > 0 and cnt1[ch2] == 0:change = 1elif cnt2[ch1] == 0 and cnt1[ch2] > 0:change = -1else:change = 0if change == -diff:return Truereturn False
提交代码评测得到：耗时114ms，占用内存15.4MB。
4. 题目四
给出题目四的试题链接如下：
- 2532. Time to Cross a Bridge
1. 解题思路
这一题其实思路不怎么复杂，就是按照题意完全用代码翻译一下，然后模拟一下其完整的过程就可以了。
不过，如前所述，问题就是繁琐……
2. 代码实现
给出python代码实现如下：
class Solution:def findCrossingTime(self, n: int, k: int, time: List[List[int]]) -> int:eff = sorted([(t[0] + t[2], i) for i, t in enumerate(time)], reverse=True)orders = [0 for _ in range(k)]for i in range(k):orders[eff[i][1]] = iright, left = 0, 1q = [(left, orders[i], i) for i in range(k)]heapq.heapify(q)waited = []t = 0while q or waited:while q == [] and waited:nxt, side, order, wid = heapq.heappop(waited)if n > 0 or side == right:t = max(t, nxt)heapq.heappush(q, (side, order, wid))while waited and waited[0][0] <= t:_, side, order, wid = heapq.heappop(waited)heapq.heappush(q, (side, order, wid))if q == []:breakside, order, wid = heapq.heappop(q)if side == left:if n == 0:continuet += time[wid][0]heapq.heappush(waited, (t + time[wid][1], right, order, wid))n -= 1else:t += time[wid][2]heapq.heappush(waited, (t + time[wid][3], left, order, wid))return t
提交代码评测得到：744ms，占用内存21.2MB。
