1997. First Day Where You Have Been in All the Rooms
Description
There are n
rooms you need to visit, labeled from 0
to n - 1
. Each day is labeled, starting from 0
. You will go in and visit one room a day.
Initially on day 0
, you visit room 0
. The order you visit the rooms for the coming days is determined by the following rules and a given 0-indexed array nextVisit
of length n
:
- Assuming that on a day, you visit room
i
, - if you have been in room
i
an odd number of times (including the current visit), on the next day you will visit a room with a lower or equal room number specified bynextVisit[i]
where0 <= nextVisit[i] <= i
; - if you have been in room
i
an even number of times (including the current visit), on the next day you will visit room(i + 1) mod n
.
Return the label of the first day where you have been in all the rooms. It can be shown that such a day exists. Since the answer may be very large, return it modulo 109 + 7
.
Example 1:
Input: nextVisit = [0,0] Output: 2 Explanation: - On day 0, you visit room 0. The total times you have been in room 0 is 1, which is odd. On the next day you will visit room nextVisit[0] = 0 - On day 1, you visit room 0, The total times you have been in room 0 is 2, which is even. On the next day you will visit room (0 + 1) mod 2 = 1 - On day 2, you visit room 1. This is the first day where you have been in all the rooms.
Example 2:
Input: nextVisit = [0,0,2] Output: 6 Explanation: Your room visiting order for each day is: [0,0,1,0,0,1,2,...]. Day 6 is the first day where you have been in all the rooms.
Example 3:
Input: nextVisit = [0,1,2,0] Output: 6 Explanation: Your room visiting order for each day is: [0,0,1,1,2,2,3,...]. Day 6 is the first day where you have been in all the rooms.
Constraints:
n == nextVisit.length
2 <= n <= 105
0 <= nextVisit[i] <= i
Solutions
Solution 1: Dynamic Programming
We define $f[i]$ as the date number of the first visit to the $i$-th room, so the answer is $f[n - 1]$.
Consider the date number of the first arrival at the $(i-1)$-th room, denoted as $f[i-1]$. At this time, it takes one day to return to the $nextVisit[i-1]$-th room. Why return? Because the problem restricts $0 \leq nextVisit[i] \leq i$.
After returning, the $nextVisit[i-1]$-th room is visited an odd number of times, and the rooms from $nextVisit[i-1]+1$ to $i-1$ are visited an even number of times. At this time, we go to the $(i-1)$-th room again from the $nextVisit[i-1]$-th room, which takes $f[i-1] - f[nextVisit[i-1]]$ days, and then it takes one more day to reach the $i$-th room. Therefore, $f[i] = f[i-1] + 1 + f[i-1] - f[nextVisit[i-1]] + 1$. Since $f[i]$ may be very large, we need to take the remainder of $10^9 + 7$, and to prevent negative numbers, we need to add $10^9 + 7$.
Finally, return $f[n-1]$.
The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the number of rooms.
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|