0%

Weekly Contest 198

Ranking: 1197 / 15151 πŸ˜”πŸ˜‚πŸ˜­

Q1. 1518. Water Bottles

Given numBottles full water bottles, you can exchange numExchange empty water bottles for one full water bottle.

The operation of drinking a full water bottle turns it into an empty bottle.

Return the maximum number of water bottles you can drink

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def numWaterBottles(self, A: int, B: int) -> int:
ret = 0
while A:
if A >= B:
drink = (A // B) * B
else:
drink = A
ret += drink
A = A - drink + drink // B
return ret

Q2. 1519. Number of Nodes in the Sub-Tree With the Same Label

See details in link

Note

similar to
437. Path Sum III
834. Sum of Distances in Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:
graph = defaultdict(set)
for u, v in edges:
graph[u].add(v)
graph[v].add(u)

d, ret = Counter(), [0] * n
def dfs(cur, p):
above = d[labels[cur]]
d[labels[cur]] += 1
for nxt in graph[cur]:
if nxt == p: continue
dfs(nxt, cur)
ret[cur] = d[labels[cur]] - above
dfs(0, -1)
return ret

Q3. 1520. Maximum Number of Non-Overlapping Substrings FAILED

See details in link

Notes

  1. So hard….
  2. I thought we just need to deal with the edges [l, r]. But it turns out that we have to scan
    all possible substring since within a substring, it may contains other characters which may extend the size of current substring. So it is different to merge ranges.
  3. @votrubac’s post) provides an idea which is
    1. Append current possible substring
    2. Replace the previous substring if we find a better one to replace it
      This idea might be helpful when dealing with other greedy algorithm.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
def maxNumOfSubstrings(self, s: str) -> List[str]:
c_set = set(s)
idx_l, idx_r = {c: s.index(c) for c in c_set}, {c: s.rindex(c) for c in c_set}

def find_right(start):
right = idx_r[s[start]]
i = start
while i <= right:
if idx_l[s[i]] < start:
return -1
right = max(right, idx_r[s[i]])
i += 1
return right

ret, right_max = [], -1
for i, c in enumerate(s):
if idx_l[c] == i:
right = find_right(i)
if right == -1: continue
if right > right_max:
ret.append(s[i:right+1])
else:
ret[-1] = s[i:right+1]
right_max = right

return ret

Q4. 1521. Find a Value of a Mysterious Function Closest to Target FAILED

See details in link

Brute force

1
2
3
4
5
6
7
8
class Solution:
def closestToTarget(self, arr: List[int], target: int) -> int:
ret, s = math.inf, set()
for a in arr:
s = {a & b for b in s} | {a}
for val in s:
ret = min(ret, abs(target-val))
return ret

Summary

  1. When dealing with tree/graph problem, a pattern subtree = total - parent can be very useful. e.g.
    437. Path Sum III
    834. Sum of Distances in Tree
  2. A useful pattern in greedy algo.
    1. Add current possible value
    2. Replace previous value if we find a better
  3. Too sad…