2021 LC Weekly Contest 230
Created: 2021/02/28 Updated: 2021/02/28 14:00 JSTTable of Contents
- Q2 1774 - Closest Dessert Cost
- Q3 1775 - Equal Sum Arrays With Minimum Number of Operations
- Q4 1776 - Car Fleet II
Q2 1774 - Closest Dessert Cost
Solution: Bruteforce with limit
BruteForce thinking, go and grab single base then go through toppings by acending order.
To avoid traversing all possible combinations, we have a diff which represents the absolute value of difference between current cost and target. If current cost exceed is smaller than target, we can continue without thinking about this, otherwise we need to stop if current cost is much greater than tracked minimal value.
Return target if current cost exactly equals to target.
-
Time: O(logM + logN + logN * 2) = O(logM logN) - Space: O(M*N) where N is length of M * N
class Solution:
def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:
# Need one base and 0 or n toppings to have minimize(diff(target, cost)), if multiple choose smaller cost
# dfs?
# bfs?
toppingCosts.sort()
baseCosts.sort()
targets = collections.deque()
minDiff = float("inf")
for base in baseCosts:
targets.append(target - base)
minDiff = min(minDiff, abs(target - base))
# If any of base cost is greater than target
if targets[0] < 0:
return baseCosts[0]
for top in toppingCosts:
newTargets = []
i = 0
while i < len(targets):
# 0
top0 = targets[i]
if top0 > 0:
newTargets.append(top0)
elif top0 == 0:
return target
else:
if abs(top0) <= minDiff:
newTargets.append(top0)
minDiff = abs(top0)
# 1
top1 = targets[i] - top
if top1 > 0:
newTargets.append(top1)
elif top1 == 0:
return target
else:
if abs(top1) <= minDiff:
newTargets.append(top1)
minDiff = abs(top1)
# 2
top2 = targets[i] - top * 2
if top2 > 0:
newTargets.append(top2)
elif top2 == 0:
return target
else:
if abs(top2) <= minDiff:
newTargets.append(top2)
minDiff = abs(top2)
i += 1
# print(minDiff, newTargets)
if len(newTargets) == 0:
break
targets = newTargets
# print(targets)
targets.sort(key=lambda key: abs(key))
return target - targets[0]
Q3 1775 - Equal Sum Arrays With Minimum Number of Operations
Solution: Greedy with min/max heap
To shrink diff between two array, we greedly change the small/large value from one of the array under the condition that it has larger effect on shrinking the difference.
- Time: O(M * logM + N * logN) where M is length of nums1, and N is length of nums2
- Space: O(M + N)
from heapq import heapify, heappush, heappop
class Solution:
def minOperations(self, nums1: List[int], nums2: List[int]) -> int:
# [1, 6]
# abs(sum(nums1) - sum(nums[2])) -> 0
# Edge case
if len(nums1) > 6 * len(nums2) or len(nums2) > 6 * len(nums1):
return -1
self.res = 0
sum1 = sum(nums1)
sum2 = sum(nums2)
big = None
small = None
if sum1 > sum2:
big = [-1 * i for i in nums1]
heapify(big)
small = nums2
heapify(small)
elif sum2 > sum1:
big = [-1 * i for i in nums2]
heapify(big)
small = nums1
heapify(small)
else:
return 0
diff = abs(sum1 - sum2)
res = 0
canChangeBig = True
while diff > 0:
# print(big[0], small[0])
if abs(-1 * big[0] - 1) >= abs(small[0] - 6) and canChangeBig:
if big[0] == -1:
canChangeBig = False
continue
if big[0] - 1 >= diff:
return res + 1
pop = -1 * heappop(big)
#print("big: ", pop, " -> 1")
diff -= (pop - 1)
heappush(big, -1)
else:
if 6 - small[0] >= diff:
return res + 1
pop = heappop(small)
#print("small: ", pop, " -> 6")
diff -= (6 - pop)
heappush(small, 6)
res += 1
return res