题目

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

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

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

请返回你访问完所有房间的第一天的日期编号。题目数据保证总是存在这样的一天。由于答案可能很大，返回对 109 + 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 <= 105
• 0 <= nextVisit[i] <= i

我的题解

题解（动归）

这个奇偶数访问的设定实际就是让访问一个房间后需要再往前访问，再回到当前位置才能继续向下。这个过程就像一个循环，或者说一个口袋。口袋的口就是当前访问的这个位置，而口袋里是所有在这个循环区间内的小循环。口袋需要计算口袋的口（访问了两次）和口袋内所有的循环，因为要全部重新走一遍才能回到当前位置。

在这个过程中，显然需要用到多次重复的累加，可以使用前缀和加速这个过程，否则会TLE。

代码如下

class Solution {
public:
    int firstDayBeenInAllRooms(vector<int>& nextVisit) {
        int n = nextVisit.size();
        if(n==1){
            return 0;
        }
        vector<int> visit_loop_count = vector<int>(n);
        // 初始为2
        visit_loop_count[0] = 2;
        // 下面使用了前缀和，不太容易理解
        for(int i=1;i<n;i++){
            int sum;
            if(nextVisit[i]>=1)
            {
                sum = visit_loop_count[i-1]-visit_loop_count[nextVisit[i]-1];
                sum = sum<0?sum+(int)(1e9+7):sum;
            }
            else
                sum = visit_loop_count[i-1];
            visit_loop_count[i] = (visit_loop_count[i-1]+sum+2)%(int)(1e9 + 7);
        }
        return visit_loop_count[n-2];
        //容易理解的没有加前缀和的代码如下：
        // vector<int> visit_loop_count = vector<int>(nextVisit.size(), 0);
        // for(int i=0;i<nextVisit.size();i++){
        //     int sum = 0;
        //     for(int j=nextVisit[i];j<i;j++){
        //         sum = (sum+visit_loop_count[j])%(int)(1e9 + 7);
        //     }
        //     visit_loop_count[i] = sum+2;
        // }
        // int ret = 0;
        // for(int i=0;i<nextVisit.size()-1;i++){
        //     ret  = (ret+visit_loop_count[i])%(int)(1e9 + 7);
        // }
        // return ret;
    }
};class Solution {
public:
    int firstDayBeenInAllRooms(vector<int>& nextVisit) {
        int n = nextVisit.size();
        if(n==1){
            return 0;
        }
        vector<int> visit_loop_count = vector<int>(n);
        // 初始为2
        visit_loop_count[0] = 2;
        // 下面使用了前缀和，不太容易理解
        for(int i=1;i<n;i++){
            int sum;
            if(nextVisit[i]>=1)
            {
                sum = visit_loop_count[i-1]-visit_loop_count[nextVisit[i]-1];
                sum = sum<0?sum+(int)(1e9+7):sum;
            }
            else
                sum = visit_loop_count[i-1];
            visit_loop_count[i] = (visit_loop_count[i-1]+sum+2)%(int)(1e9 + 7);
        }
        return visit_loop_count[n-2];
        //容易理解的没有加前缀和的代码如下：
        // vector<int> visit_loop_count = vector<int>(nextVisit.size(), 0);
        // for(int i=0;i<nextVisit.size();i++){
        //     int sum = 0;
        //     for(int j=nextVisit[i];j<i;j++){
        //         sum = (sum+visit_loop_count[j])%(int)(1e9 + 7);
        //     }
        //     visit_loop_count[i] = sum+2;
        // }
        // int ret = 0;
        // for(int i=0;i<nextVisit.size()-1;i++){
        //     ret  = (ret+visit_loop_count[i])%(int)(1e9 + 7);
        // }
        // return ret;
    }
};

官方题解

值得注意的是，官方题解中有更好的取余处理方法（注意其中的+mod)：

for (int i = 1; i < len; i++) {
    int to = nextVisit[i];
    dp[i] = 2 + dp[i - 1];

    if (to != 0) {
        dp[i] = (dp[i] - dp[to - 1] + mod) % mod; //避免负数
    }
    dp[i] = (dp[i] + dp[i - 1]) % mod;
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/first-day-where-you-have-been-in-all-the-rooms/solutions/2710218/fang-wen-wan-suo-you-fang-jian-de-di-yi-p7fc2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

取余模板

另外，也有人使用了取余操作模板

static constexpr int mod = 1000000007;

class modint {
public:
    int val;
    inline modint(int val_ = 0) : val(val_) {}
    inline modint &operator=(int val_) { return val = val_, *this; }
    inline modint &operator+=(const modint &k) { return val = val + k.val >= mod ? val + k.val - mod : val + k.val, *this; }
    inline modint &operator-=(const modint &k) { return val = val - k.val < 0 ? val - k.val + mod : val - k.val, *this; }
    inline modint &operator*=(const modint &k) { return val = 1ll * val * k.val % mod, *this; }
    inline modint &operator^=(int k) {
        modint res = 1, tmp = *this;
        for (; k; k >>= 1, tmp *= tmp)
            if (k & 1)
                res *= tmp;
        return val = res.val, *this;
    }
    inline modint &operator/=(modint k) { return *this *= (k ^= mod - 2); }
    inline modint &operator+=(int k) { return val = val + k >= mod ? (val + k) % mod : val + k, *this; }
    inline modint &operator-=(int k) { return val = val < k ? val - k + mod : val - k, *this; }
    inline modint &operator*=(int k) { return val = 1ll * val * k % mod, *this; }
    inline modint &operator/=(int k) { return *this *= ((modint(k)) ^= mod - 2); }
    template <class T>
    friend modint operator+(modint a, T b) { return a += b; }
    template <class T>
    friend modint operator-(modint a, T b) { return a -= b; }
    template <class T>
    friend modint operator*(modint a, T b) { return a *= b; }
    template <class T>
    friend modint operator^(modint a, T b) { return a /= b; }
    template <class T>
    friend modint operator/(modint a, T b) { return a /= b; }
    friend modint operator^(modint a, int b) { return a ^= b; }
    friend bool operator==(modint a, int b) { return a.val == b; }
    friend bool operator!=(modint a, int b) { return a.val != b; }
    inline bool operator!() { return !val; }
    inline modint operator-() { return val ? mod - val : 0; }
    inline modint &operator++() { return *this += 1; }
    inline modint &operator--() { return *this -= 1; }
    friend ostream &operator<<(ostream &os, const modint &n) { return os << n.val; }
};

class Solution {
public:
    int firstDayBeenInAllRooms(vector<int>& nextVisit) {
        int n = nextVisit.size();
        vector<modint> dp(n, 0);
        dp[1] = 2;
        for (int i = 2; i < n; ++i) {
            dp[i] = (dp[i - 1] - dp[nextVisit[i - 1]] + dp[i - 1] + 2);
        }
        return dp[n - 1].val;
    }
};

完成时间

2024-03-28：[ 用时: 38 m 37 s ]

题目链接

https://leetcode.cn/problems/first-day-where-you-have-been-in-all-the-rooms/