0%

Weekly Contest 199

Ranking: 256 / 14309 🧐🤔😑

Q1. 1528. Shuffle String

Given a string s and an integer array indices of the same length.

The string s will be shuffled such that the character at the ith position moves to indices[i] in the shuffled string.

Return the shuffled string.

1
2
3
4
5
6
class Solution:
def restoreString(self, s: str, indices: List[int]) -> str:
ret = [None] * len(s)
for i, c in zip(indices, s):
ret[i] = c
return ''.join(ret)

Q2. 1529. Bulb Switcher IV

There is a room with n bulbs, numbered from 0 to n-1, arranged in a row from left to right. Initially all the bulbs are turned off.

Your task is to obtain the configuration represented by target where target[i] is ‘1’ if the i-th bulb is turned on and is ‘0’ if it is turned off.

You have a switch to flip the state of the bulb, a flip operation is defined as follows:

Choose any bulb (index i) of your current configuration.
Flip each bulb from index i to n-1.
When any bulb is flipped it means that if it is 0 it changes to 1 and if it is 1 it changes to 0.

Return the minimum number of flips required to form target.

Intuition

The best (greedy) strategy is

  • starting from left most bulb, flip that bulb and all following bulbs if it does not match target
  • move to next bulb

Key observation
if we follow the above strategy, at any point, all following bulbs are at the same statue.
Hence we can use boolean to represent the status of all following bulbs and only update that boolean when we flip all following bubls.

1
2
3
4
5
6
7
8
9
class Solution:
def minFlips(self, target: str) -> int:
ret, cur = 0, 0
for i in range(len(target)):
ex = 0 if target[i] == '0' else 1
if ex != cur:
ret += 1
cur = 0 if cur == 1 else 1
return ret

1530. Number of Good Leaf Nodes Pairs FAILED

Given the root of a binary tree and an integer distance. A pair of two different leaf nodes of a binary tree is said to be good if the length of the shortest path between them is less than or equal to distance.

Return the number of good leaf node pairs in the tree.

4D DP, hum…

It was so clear that this is a DP problem.
But i was not able to define the state transform formula during the contest…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def getLengthOfOptimalCompression(self, s: str, k: int) -> int:
# dp
@lru_cache(None)
def dp(idx, last, size, remove):
if remove > k: return math.inf
if idx == len(s): return (1+(0 if size==1 else len(str(size)))) if last else 0
# remove, merge
if s[idx] == last:
ret = min(dp(idx+1, last, size+1, remove), dp(idx+1, last, size, remove+1))
else:
ret = min((1+(0 if size==1 else len(str(size))) if last else 0)+dp(idx+1, s[idx], 1, remove), \
dp(idx+1, last, size, remove+1))
return ret
return dp(0, None, 0, 0)