1997. 第一天访问所有房间的日期

Medium

题目描述

有 n 个房间需要访问，编号从 0 到 n - 1。每一天都有一个标签，从 0 开始。你每天会访问一个房间。

在第 0 天，你访问房间 0。接下来几天访问房间的顺序由以下规则和给定的长度为 n 的 0 索引数组 nextVisit 决定：

假设在某一天，你访问房间 i，

• 如果你访问房间 i 的次数是奇数次（包括当前访问），那么明天你将访问 nextVisit[i] 指定的房间号更小或相等的房间，其中 0 <= nextVisit[i] <= i；
• 如果你访问房间 i 的次数是偶数次（包括当前访问），那么明天你将访问房间 (i + 1) mod n。

返回你访问过所有房间的第一天的标签。可以证明这样的一天是存在的。由于答案可能很大，返回答案对 10^9 + 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^5
• 0 <= nextVisit[i] <= i

解题思路

这是一个经典的动态规划问题。核心观察是：要访问房间 i+1，必须先让房间 i 被访问偶数次。

关键洞察：

1. 当我们第一次到达房间 i 时，访问次数为奇数，下一步必须跳到 nextVisit[i]
2. 要让房间 i 变成偶数次访问，我们需要从 nextVisit[i] 再次回到房间 i
3. 从房间 nextVisit[i] 到房间 i 的天数可以用之前计算的结果

状态定义： 设 dp[i] 表示第一次到达房间 i 的天数。

状态转移：

• dp[0] = 0（第0天就在房间0）
• 对于 i > 0：
  • 首先从房间 i-1 走到房间 i：dp[i-1] + 1 天
  • 但此时房间 i 只被访问了1次（奇数），需要跳到 nextVisit[i]
  • 从 nextVisit[i] 回到房间 i 需要：dp[i] - dp[nextVisit[i]] 天
  • 回到房间 i 后，访问次数变为2次（偶数），可以继续前进
  • 所以：dp[i] = (dp[i-1] + 1) + (dp[i] - dp[nextVisit[i]]) + 1

简化后：dp[i] = 2 * dp[i-1] - dp[nextVisit[i]] + 2

为避免负数，需要在每步都取模。

代码实现

class Solution {
public:
    int firstDayBeenInAllRooms(vector<int>& nextVisit) {
        int n = nextVisit.size();
        vector<long long> dp(n, 0);
        const int MOD = 1e9 + 7;
        
        for (int i = 1; i < n; i++) {
            dp[i] = (2 * dp[i-1] - dp[nextVisit[i]] + 2 + MOD) % MOD;
        }
        
        return dp[n-1];
    }
};

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

public class Solution {
    public int FirstDayBeenInAllRooms(int[] nextVisit) {
        int n = nextVisit.Length;
        long[] dp = new long[n];
        const int MOD = 1000000007;
        
        for (int i = 1; i < n; i++) {
            dp[i] = (2 * dp[i-1] - dp[nextVisit[i]] + 2 + MOD) % MOD;
        }
        
        return (int)dp[n-1];
    }
}

var firstDayBeenInAllRooms = function(nextVisit) {
    const n = nextVisit.length;
    const dp = new Array(n).fill(0);
    const MOD = 1e9 + 7;
    
    for (let i = 1; i < n; i++) {
        dp[i] = (2 * dp[i-1] - dp[nextVisit[i]] + 2 + MOD) % MOD;
    }
    
    return dp[n-1];
};

复杂度分析

其中 n 为房间数量。我们只需要遍历一次数组计算每个状态，空间复杂度为存储 dp 数组所需的空间。