2024.3.28力扣每日一题——访问完所有房间的第一天

题目来源

力扣每日一题；题序：1997

我的题解

方法一 模拟

使用一个Set存储已经访问过的房间号，直到Set中的元素个数等于房间数时停止模拟。

时间复杂度：O(day)。能够访问完所有房间的最小天数
空间复杂度：O(n)。count数组记录房间被访问次数的奇偶

public int firstDayBeenInAllRooms(int[] nextVisit) {
    int n=nextVisit.length;
    int[] count=new int[n];
    Set<Integer> set=new HashSet<>();
    int i=0;
    long day=0;
    int mod=1000000007;
    set.add(0);
    while(set.size()<n){
        if(count[i]==0){
            count[i]=1;
            i=nextVisit[i];
        }else{
            count[i]=0;
            i=(i+1)%n;
        }
        day=(day+1)%mod;
        set.add(i);
    }
    return (int)(day%mod);
}

方法二 动态规划

当访问次数是奇数时下次访问会回访，只有访问次数是偶数才会遍历下一个房间。所以，在访问房间i时，左边的房间一定都已经访问了偶数次（不然不可能到达i）。也就是从 i回到 j 时，此时 [j,i−1] 范围内的房间都处于访问偶数次的状态。那么当我们访问这个范围内的每个房间时，算上本次访问，访问次数一定是奇数，所以要想重新回到 iii，对于 [j,i−1] 范围内的每个房间，都需要执行一次「回访」。
定义 f[i] 表示从「访问到房间 i 且次数为奇数」到「访问到房间 i且次数为偶数」所需要的天数。定义包含了首次访问房间 i的一天，和重新回到房间 i 的一天
由于 [j,i−1]范围内的每个房间都需要「回访」，所以需要把这个范围内的 fff 值都加起来，再算上房间 i 需要访问 2次。所以，状态转移方程：
$f[i]=2+{\sum }_{k=j}^{i-1}f[k]$
和式采用前缀和优化，最终的状态转移方程：
$dp[i+1]=dp[i]\ast 2-dp[j]+2$
dp[i]表示${\sum }_{j=0}^{i}f[i]$

时间复杂度：O(n)
空间复杂度：O(n) 。

public int firstDayBeenInAllRooms(int[] nextVisit) {
    int n = nextVisit.length;
    int mod=1_000_000_007;
    long[] dp = new long[n];
    for (int i = 0; i < n-1; i++) {
       int j=nextVisit[i];
       dp[i+1]=(dp[i]*2-dp[j]+2+mod)%mod;//需要避免算出负数
    }

    return (int)dp[n-1];
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~