2021 LC Weekly Contest 227
Created: 2021/02/07 Updated: 2021/02/07 14:30 JSTTable of Contents
- Q2 1753 - Maximum Score From Removing Stones
- Q3 1754 - Largest Merge Of Two Strings
- Q4 1755 - Closest Subsequence Sum
Q2 1753 - Maximum Score From Removing Stones
Solution: Greedy and sort
Using DFS to find all possible ways will result in TLE.
Already take pile from the most piles, so we need to sort a b and c, then take from later two until there are no more two piles left.
class Solution:
def maximumScore(self, a: int, b: int, c: int) -> int:
nums = [a, b, c]
nums.sort()
res = 0
while nums[0] >= 0 and nums[1] >= 1 and nums[2] >= 1:
nums[2] -= 1
nums[1] -= 1
nums.sort()
res += 1
return res
- Time: O(N) where maximal is 2 * max(a, b, c)
- Space: O(1) space for sorted array.
Optimize by math/heap
TODO
Q3 1754 - Largest Merge Of Two Strings
Solution: Compare and
- Time: O(N) where N is len(word1) + len(word2)
- Space: O(1) space for sorted array.
class Solution:
def largestMerge(self, word1: str, word2: str) -> str:
# just compare?
p1 = p2 = 0
merge = ""
while p1 < len(word1) and p2 < len(word2):
if word1[p1] > word2[p2]:
merge += word1[p1]
p1 += 1
elif word2[p2] > word1[p1]:
merge += word2[p2]
p2 += 1
else:
if word1[p1+1:] > word2[p2+1:]:
merge += word1[p1]
p1 += 1
else:
merge += word2[p2]
p2 += 1
if p1 < len(word1):
merge += word1[p1:]
if p2 < len(word2):
merge += word2[p2:]
return merge
Optimize
Q4 1755 - Closest Subsequence Sum
TODO