Ranking: 256 / 14309 🧐🤔😑
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.
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.
The best (greedy) strategy is
- starting from left most bulb, flip that bulb and all following bulbs if it does not match
- move to next bulb
if we follow the above strategy, at any point, all following bulbs are at the same statue.
Hence we can use
booleanto represent the status of all following bulbs and only update that
booleanwhen we flip all following bubls.
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.
It was so clear that this is a DP problem.
But i was not able to define the state transform formula during the contest…