2021 LC Weekly Contest 230Created: 2021/02/28 Updated: 2021/02/28 14:00 JST
Table 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: return baseCosts 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
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)) -> 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, small) if abs(-1 * big - 1) >= abs(small - 6) and canChangeBig: if big == -1: canChangeBig = False continue if big - 1 >= diff: return res + 1 pop = -1 * heappop(big) #print("big: ", pop, " -> 1") diff -= (pop - 1) heappush(big, -1) else: if 6 - small >= diff: return res + 1 pop = heappop(small) #print("small: ", pop, " -> 6") diff -= (6 - pop) heappush(small, 6) res += 1 return res