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

本文主要是介绍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];
}

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

这篇关于2024.3.28力扣每日一题——访问完所有房间的第一天的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---