友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
1997. 访问完所有房间的第一天
你需要访问 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
思路分析
抄的答案，一脸懵逼！
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-22 20:19:06
*/
public int firstDayBeenInAllRooms(int[] nextVisit) {
int mod = (int) 1e9 + 7;
int len = nextVisit.length;
int[] dp = new int[len];
dp[0] = 2;
for (int i = 1; i < len; i++) {
int to = nextVisit[i];
dp[i] = dp[i - 1] + 2;
if (to != 0) {
dp[i] = (dp[i] - dp[to - 1] + mod) % mod;
}
dp[i] = (dp[i] + dp[i - 1]) % mod;
}
return dp[len - 2];
}
参考资料
-
1997. 访问完所有房间的第一天 - 官方题解 — 一脸懵逼！
-
1997. 访问完所有房间的第一天 - 前缀和优化 DP — 这个题解更清晰易懂一些。
-
1997. 访问完所有房间的第一天 - 【JavaScript】动态规划 — 这个讲解也可以。