2021 LC Weekly Contest 229
Created: 2021/02/21 Updated: 2021/02/21 23:20 JSTTable of Contents
- Q2 1769 - Minimum Number of Operations to Move All Balls to Each Box
- Q3 1754 - Largest Merge Of Two Strings
Q2 1769 - Minimum Number of Operations to Move All Balls to Each Box
Bruteforce
Calculating for each position.
- Time: O(N^2) where N is length of boxes.
- Space: O(1)
class Solution:
def minOperations(self, boxes: str) -> List[int]:
# consider distance
# bruteforce
res = []
for i in range(len(boxes)):
cur = 0
for j in range(len(boxes)):
if boxes[j] == '1':
cur += abs(j - i)
res.append(cur)
return res
Solution: go two directions
TO-BE-FILLED
- Time: O(N) where N is length of boxes.
- Space: O(1)
class Solution:
def minOperations(self, boxes: str) -> List[int]:
# from left to right, then right to left
res = [0 for i in range(len(boxes))]
count = 0
ops = 0
for i in range(len(boxes)):
res[i] += ops
count += 1 if boxes[i] == '1' else 0
ops += count
count = 0
ops = 0
for i in reversed(range(len(boxes))):
res[i] += ops
count += 1 if boxes[i] == '1' else 0
ops += count
return res
Q3 1754 - Largest Merge Of Two Strings
Solution: Top-Down DP
TO-BE-FILLED
- Time:
- Space: