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
媽的 這什麼神仙