LeetCode笔记：Biweekly Contest 63
LeetCode笔记：Biweekly Contest 63
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题思路挺直接的，我们直接对座位和学生位置进行排序，然后逐位取差值即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
seats = sorted(seats)
students = sorted(students)
return sum(abs(x-y) for x, y in zip(seats, students))提交代码评测得到：耗时36ms，占用内存15.1MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题由于要求只能够取连续的元素中间的位置，因此，我们只需要统计连续的A和B的个数即可得到Alice以及Bob可做的操作数目。
然后我们比较这两个数的大小关系即可得到最终的胜负关系。
2. 代码实现
给出python代码实现如下：
class Solution:
def winnerOfGame(self, colors: str) -> bool:
def count(ch):
pre = ""
cnt = 0
res = 0
for c in colors:
if c != pre:
if pre == ch and cnt > 2:
res += cnt - 2
pre = c
cnt = 1
else:
cnt += 1
if pre == ch and cnt > 2:
res += cnt-2
return res
a, b = count("A"), count("B")
return a > b提交代码评测得到：耗时164ms，占用内存15MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题我们只需要考察每一个网络节点的活跃时间，然后求出其中最大的值就是网络空闲前的最后一刻，然后+1即是我们所需的答案。
而对于每一个节点的活跃时间的计算，我们首先计算出这个节点到中心节点的距离，然后他的信号发送会重复到第一次信号发送并传回的时间，即距离的两倍，由此我们可以找到最后一个信号发送的时间点，然后加上单次信号发送到传回的时间，即是这个节点活跃的时间。
2. 代码实现
给出最终的python代码实现如下：
class Solution:
def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:
n = len(patience)
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
distance = [0 for _ in range(n)]
q = [(0, 0)]
idx, m = 0, 1
seen = {0}
while idx < m:
u, d = q[idx]
distance[u] = d
for v in graph[u]:
if v not in seen:
q.append((v, d+1))
seen.add(v)
m += 1
idx += 1
def cal_last_time(d, p):
if p == 0:
return 0
t = d * 2
last = ((t-1) // p) * p
return last + t
return max(cal_last_time(d, p) for d, p in zip(distance, patience))+1提交代码评测得到：耗时532ms，占用内存64.4MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题的做法我其实借鉴了网上其他大佬们的解题思路。
思路上而言，就是一个二分查找，首先找到可能的乘积的最大值与最小值，然后使用二分查找分别计算对于某一个数可以找到的乘积对的数目 f ( x ) f(x) f(x)。
当 f ( x ) > = k f(x) >= k f(x)>=k且 f ( x − 1 ) < k f(x-1) < k f(x−1)<k时，x即为我们最终所需要的解。
而对于 f ( x ) f(x) f(x)的计算，我们同样可以通过二分查找进行优化。
2. 代码实现
给出我们最终的python代码实现如下：
class Solution:
def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:
n, m = len(nums1), len(nums2)
if n > m:
return self.kthSmallestProduct(nums2, nums1, k)
def get_interval():
s = [nums1[0] * nums2[0], nums1[0] * nums2[-1], nums1[-1] * nums2[0], nums1[-1] * nums2[-1]]
return min(s), max(s)
def is_kth(val):
cnt = 0
for x in nums1:
if x == 0:
cnt = cnt if val < 0 else cnt + m
elif x < 0:
tgt = math.ceil(val / x)
cnt += m - bisect.bisect_left(nums2, tgt)
else:
tgt = val // x
cnt += bisect.bisect_right(nums2, tgt)
if cnt >= k:
return 1
return -1
i, j = get_interval()
if is_kth(i) >= 0:
return i
while i < j-1:
val = (i+j) // 2
status = is_kth(val)
if status == 1:
j = val
else:
i = val
return j提交代码评测得到：耗时3396ms，占用内存21.7MB。