Weekly Contest 316
这礼拜的题目蛮好玩的
1.给你两个时段问有没有重叠 感觉写过很多类似的题目
class Solution:
def haveConflict(self, event1: List[str], event2: List[str]) -> bool:
t1s, t1e = int(event1[0][:2])*60 + int(event1[0][3:]),
int(event1[1][:2])*60 + int(event1[1][3:])
t2s, t2e = int(event2[0][:2])*60 + int(event2[0][3:]),
int(event2[1][:2])*60 + int(event2[1][3:])
return max(t1s, t2s) <= min(t1e, t2e)
不过还是写很丑 哈 好像可以直接比字串大小
2.给你一个 integer array 和 k 问你他有几个 GCD 等于 k 的 subarray
好难 用 2 pointer 想很久 一直在想怎么维护GCD
最后才发现测资范围有鬼 哭阿
class Solution:
def subarrayGCD(self, nums: List[int], k: int) -> int:
n = len(nums)
res = 0
for i in range(n):
subgcd = nums[i]
for j in range(i, -1, -1):
subgcd = gcd(subgcd, nums[j])
res += subgcd == k
return res
没什么特别的O(n^2)
3.给你两个 array nums 和 cost 问你要把 nums 的数字全部变成一样最少要花的 cost
cost[i] 代表把 nums[i] +1/-1 花的 cost
一开始以为是DP 看了测资范围发现不太像
然后就想到要算 cost 会有个目标数字 n 和要把 nums 全部变成 n 要花的 cost(n)
如果 n = min(nums) 或 n = max(nums) 那 cost(n) 应该都会很大
然后要在 min(nums)~max(nums) 中间找 cost(n) 最小值
就猜 cost(n) 会是二次曲线 -> 可以用 ternary search
比较 cost(n) 和 cost(n+1) 往比较小的那一半搜
class Solution:
def minCost(self, nums: List[int], cost: List[int]) -> int:
left, right = min(nums), max(nums)
def count(num):
res = 0
for idx, n in enumerate(nums):
res += cost[idx]*abs(num-n)
return res
res = 0
while left < right:
mid = (left + right)//2
cost1 = count(mid)
cost2 = count(mid+1)
res = min(cost1, cost2)
if cost1 < cost2:
right = mid
else:
left = mid+1
return res
其实不太确定正确性
4.给你两个 integer array nums 和 target 问你要让 nums 的元素跟 target 一样
要花多少操作 结果可以不用照顺序 例如最后 nums = [10,14,2], target = [2,14,10]
操作只有一种: 挑不同的 nums[i], nums[j] 后 nums[i] += 2, nums[j] -= 2
感觉很像 greedy 一开始就配给每个 nums[i] 一个 target[j]
+2/-2 不能让奇偶变化 所以一开始就把奇数偶数分开配
然后算出总共的 diff 也就是 abs(nums[i] - target[j]) 的 sum
最后因为一个操作能让 diff 少 4 所以答案就是 diff/4
要怎么帮 nums[i] 找到对应的 target
一个很直觉的想法是直接用 sort 后的顺序来配 因为要到最大的 target
一定是最大的 nums 最快
这里如果有点疑虑 可以讨论 sort 后的末两项
假设有 nums[-2:] = [a, b], target[-2:] = [c, d], 其中 a <= b, c <= d
我们只要保证 abs(d-b) + abs(c-a) 不会比 abs(d-a) + abs(c-b) 差就好
有好几种状况
a b a b a b a b a b
c d c d c d c d c d
可以发现 [a, b] 不交换的 diff 会小于等于交换后 并且对于每个前面的元素也都是这样
最后就是讨论一下能不能直接用 diff/4 也就是 nums[i] 在变成他的 target 的过程中
会不会有 detour 也就是先变大再变小或是先变小再变大
假设 nums[i] 发生两种操作 (nums[i]-2, nums[j]+2) 和 (nums[i]+2, nums[k]-2)
那其实就可以直接做 (nums[j]+2, nums[k]-2) 消除这种 detour
所以最佳解中是不会有这种例子(不然他就不会是最佳解)
当然主要是因为题目保证给的 nums 一定能转换成 target 少了很多麻烦
class Solution:
def makeSimilar(self, nums: List[int], target: List[int]) -> int:
oddnums, oddtarget = [n for n in nums if n%2], [n for n in target if
n%2]
evennums, eventarget = [n for n in nums if not n%2], [n for n in
target if not n%2]
oddnums.sort()
oddtarget.sort()
diff = 0
for i in range(len(oddnums)):
diff += abs(oddnums[i]-oddtarget[i])
evennums.sort()
eventarget.sort()
for i in range(len(evennums)):
diff += abs(evennums[i] - eventarget[i])
return diff//4
还有 @Bakerston 的
def makeSimilar(self, A, B):
A.sort(key = lambda a: (a & 1, a))
B.sort(key = lambda a: (a & 1, a))
return sum(abs(a - b) for a,b in zip(A, B)) // 4
妈的 这什么神仙