2021 LC Weekly Contest 226Created: 2021/01/31 Updated: 2021/01/31 18:30 JST
Table of Contents
- Q1 1742 - Maximum Number of Balls in a Box
- Q2 1743 - Restore the Array From Adjacent Pairs
- Q3 1744 - Can You Eat Your Favorite Candy on Your Favorite Day?
- Q4 1745 - Palindrome Partitioning IV
Q1 1742 - Maximum Number of Balls in a Box
This first question needs a little bit more work than the ones in normal weekly contest. But we still can just loop al numbers, for each one try to calculate the sum of each digit then plus one in the map.
- Time: O(N * L) where N is the number count and L is the digit count for each number.
- Space: O(N) where N is the number count and used for hashMap.
Q2 1743 - Restore the Array From Adjacent Pairs
Solution: HashMap and Graph traversal
Since each number is unique, it is perfect for key of hashMap. Another key point is to find any end of the original array, which has the property that it has no two neighbors. After forming this map, we can traverse from any one of the end number, then form the rest of the numbers by using a queue.
- Time: O(N) where N is the number count.
- Space: O(N) where N is the number count.
class Solution: def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]: if len(adjacentPairs) == 1: return adjacentPairs m = collections.defaultdict(list) for pair in adjacentPairs: l, r = pair, pair m[l].append(r) m[r].append(l) res =  # find one which has no only one neighbor q = collections.deque() for k, v in m.items(): if len(v) == 1: q.append(k) break visited = set() while len(q) > 0: cur = q.pop() visited.add(cur) res.append(cur) for neighbor in m[cur]: if neighbor not in visited: q.append(neighbor) return res
Q3 1744 - Can You Eat Your Favorite Candy on Your Favorite Day?
Solution: think about the conditions?
Because the candies need to be consumed sequentially, it is perfect for
prefix[i]indicates the total sum until
Let’s give the parameter name: type, day and limit.
Since the all parameters given by query is 0-indexed, we need to think about easy cases:
day = 0 && type = 0: always true since
candy typewill be eaten on the first day in the very beginning.
day = 0 && type != 0: one day can be up to
limit, so if prefix sum of previous day is less then limit, then we can assure than
candy typewill be eaten.
day != 0 && type = 0:
candy 0will be eaten firstly so it needs to have more than
limit = 1multiply
day - 1
day > prefix[t]: when using minimal
limit = 1multiply
day - 1is greater than prefix sum of type, which means candies will be eaten to 0 before
day, then it is not possible
(day + 1) * limit <= prefix[t-1]: if even eat maximally candy until day, we cannot finish
prefix[t-1]candies, then it is not possible to eat
candy ton this day.
- Time: O(max(M, N)): where M is candy types and N is query count.
- Space: O(M): where M is candy types.
Q4 1745 - Palindrome Partitioning IV
Solution: DP with table (traditional dp for palindrome)
The key point to consider what does
dp[i][j] mean in this case. So the best answer is boolean value of palindrome for substring
What about the state transition? it is simple to know when substring from
j inclusive is palindrome, then whether larger subtring from
j+1 is palindrome depends on
s[i-1] == s[j+1], so the state transition is
dp[i][j] = s[i] == s[j] && dp[i-1][j+1].
So a bottom-up solution is to expand the i and j. Then we need to iterate i and j in opposite direction. In this case is: i goes left and j goes right.
- Time: O(N^2) where N is length of given string.
- Space: O(N^2) where N is length of given string. For dp table.
class Solution: def checkPartitioning(self, s: str) -> bool: dp = [[False for _ in range(len(s))] for _ in range(len(s))] for i in reversed(range(len(s))): for j in range(i, len(s)): if i == j: dp[i][j] = True elif i + 1 == j: dp[i][j] = s[i] == s[j] else: dp[i][j] = s[i] == s[j] and dp[i + 1][j - 1] for i in range(1, len(s)): for j in range(i, len(s) - 1): if dp[i-1] and dp[i][j] and dp[j+1][len(s) - 1]: return True return False