What is the main pattern used in First Day Where You Have Been in All the Rooms?

It is a state transition dynamic programming pattern where each room's next visit depends on previous room visits and their parity.

Why do we need modulo 10^9 + 7 in this problem?

The number of days can become extremely large, so modulo ensures results stay within integer limits without affecting correctness.

Can we solve this problem with brute-force simulation?

No, brute-force will timeout for large n due to repeated visits; using DP with state transitions is required.

How do odd and even visits affect room transitions?

If a room has been visited an odd number of times, the next room is determined by nextVisit; if even, move to the next sequential room modulo n.

What is the time complexity of the DP solution?

The solution runs in O(n) time since each room is processed once using dynamic programming with previous states.

#1997

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

访问完所有房间的第一天

你需要访问 n 个房间，房间从 0 到 n - 1 编号。同时，每一天都有一个日期编号，从 0 开始，依天数递增。你每天都会访问一个房间。最开始的第 0 天，你访问 0 号房间。给你一个长度为 n 且下标从 0 开始的数组 nextVisit 。在接下来的几天中，你访问房间的次序将根据下面…

数组动态规划

题目描述

你需要访问 n 个房间，房间从 0 到 n - 1 编号。同时，每一天都有一个日期编号，从 0 开始，依天数递增。你每天都会访问一个房间。

最开始的第 0 天，你访问 0 号房间。给你一个长度为 n 且 下标从 0 开始 的数组 nextVisit 。在接下来的几天中，你访问房间的次序将根据下面的规则决定：

假设某一天，你访问 i 号房间。
如果算上本次访问，访问 i 号房间的次数为奇数，那么 第二天 需要访问 nextVisit[i] 所指定的房间，其中 0 <= nextVisit[i] <= i 。
如果算上本次访问，访问 i 号房间的次数为偶数，那么 第二天 需要访问 (i + 1) mod n 号房间。

请返回你访问完所有房间的第一天的日期编号。题目数据保证总是存在这样的一天。由于答案可能很大，返回对 10⁹ + 7 取余后的结果。

示例 1：

输入：nextVisit = [0,0]
输出：2
解释：
- 第 0 天，你访问房间 0 。访问 0 号房间的总次数为 1 ，次数为奇数。
  下一天你需要访问房间的编号是 nextVisit[0] = 0
- 第 1 天，你访问房间 0 。访问 0 号房间的总次数为 2 ，次数为偶数。
  下一天你需要访问房间的编号是 (0 + 1) mod 2 = 1
- 第 2 天，你访问房间 1 。这是你第一次完成访问所有房间的那天。

示例 2：

输入：nextVisit = [0,0,2]
输出：6
解释：
你每天访问房间的次序是 [0,0,1,0,0,1,2,...] 。
第 6 天是你访问完所有房间的第一天。

示例 3：

输入：nextVisit = [0,1,2,0]
输出：6
解释：
你每天访问房间的次序是 [0,0,1,1,2,2,3,...] 。
第 6 天是你访问完所有房间的第一天。

提示：

n == nextVisit.length
2 <= n <= 10⁵
0 <= nextVisit[i] <= i

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i]$ 表示第一次访问第 $i$ 号房间的日期编号，那么答案就是 $f[n - 1]$ 。

我们考虑第一次到达第 $i-1$ 号房间的日期编号，记为 $f[i-1]$ ，此时需要花一天的时间回退到第 $nextVisit[i-1]$ 号房间，为什么是回退呢？因为题目限制了 $0 \leq nextVisit[i] \leq i$ 。

回退之后，此时第 $nextVisit[i-1]$ 号房间的访问为奇数次，而第 $[nextVisit[i-1]+1,..i-1]$ 号房间均被访问偶数次，那么这时候我们从第 $nextVisit[i-1]$ 号房间再次走到第 $i-1$ 号房间，就需要花费 $f[i-1] - f[nextVisit[i-1]]$ 天的时间，然后再花费一天的时间到达第 $i$ 号房间，因此 $f[i] = f[i-1] + 1 + f[i-1] - f[nextVisit[i-1]] + 1$ 。由于 $f[i]$ 可能很大，因此需要对 $10^9 + 7$ 取余，并且为了防止负数，需要加上 $10^9 + 7$ 。

最后返回 $f[n-1]$ 即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为房间数。

1

2

3

4

5

6

7

8

9

class Solution:
    def firstDayBeenInAllRooms(self, nextVisit: List[int]) -> int:
        n = len(nextVisit)
        f = [0] * n
        mod = 10**9 + 7
        for i in range(1, n):
            f[i] = (f[i - 1] + 1 + f[i - 1] - f[nextVisit[i - 1]] + 1) % mod
        return f[-1]

speed

复杂度分析

指标	值
时间	complexity is O(n) since each room is processed once using dynamic programming. Space complexity is O(n) to store the dp array for earliest day calculations.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if candidate identifies the state transition pattern between rooms.
question_mark
Listen for understanding of parity-based room transitions and DP optimization.
question_mark
Assess if candidate can correctly handle modulo arithmetic to prevent overflow.

warning

常见陷阱

外企场景

error
Failing to account for the odd/even visit rule when transitioning rooms.
error
Not applying modulo 10^9 + 7 consistently, causing incorrect large results.
error
Attempting brute-force simulation which leads to timeouts for large n.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change nextVisit rules to allow skipping multiple rooms and recompute first day.
arrow_right_alt
Ask for minimum days to visit a subset of target rooms instead of all rooms.
arrow_right_alt
Introduce random room re-entries and analyze adjusted state transition DP.

help

常见问题

外企场景

继续练习

#1994 好子集的数目 #1986 完成任务的最少工作时间段 #2008 出租车的最大盈利