1997. 访问完所有房间的第一天(中等)twice

Posted on In Views:

1，问题描述

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：

1
2
3
4
5
6
7
8
输入：nextVisit = [0,0]
输出：2
解释：
- 第 0 天，你访问房间 0 。访问 0 号房间的总次数为 1 ，次数为奇数。
  下一天你需要访问房间的编号是 nextVisit[0] = 0
- 第 1 天，你访问房间 0 。访问 0 号房间的总次数为 2 ，次数为偶数。
  下一天你需要访问房间的编号是 (0 + 1) mod 2 = 1
- 第 2 天，你访问房间 1 。这是你第一次完成访问所有房间的那天。

示例 2：

1
2
3
4
5
输入：nextVisit = [0,0,2]
输出：6
解释：
你每天访问房间的次序是 [0,0,1,0,0,1,2,...] 。
第 6 天是你访问完所有房间的第一天。

示例 3：

1
2
3
4
5
输入：nextVisit = [0,1,2,0]
输出：6
解释：
你每天访问房间的次序是 [0,0,1,1,2,2,3,...] 。
第 6 天是你访问完所有房间的第一天。

提示：

  • n == nextVisit.length
  • 2 <= n <= 105
  • 0 <= nextVisit[i] <= i

2，初步思考

​ 动态规划处理

3，代码处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import support.Pair;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class _1997访问完所有房间的第一天 {


    // 官方解法：动态规划
    public int firstDayBeenInAllRooms_dp(int[] nextVisit){
        int mod = 1000000007;
        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] = 2 + dp[i - 1];
            if (to != 0) {
                dp[i] = (dp[i] - dp[to - 1] + mod) % mod; //避免负数
            }

            dp[i] = (dp[i] + dp[i - 1]) % mod;
        }
        return dp[len - 2]; //题目保证n >= 2

    }

    //
    public int firstDayBeenInAllRooms(int[] nextVisit) {
        Pair<Integer, Integer>[] dp = new Pair[nextVisit.length];
        Set<Integer> set = new HashSet<>();
        Map<Integer, Pair<Integer, Integer>> map = new HashMap<>();
        for (int i = 0; i < nextVisit.length; i++) {
            int roomId = nextVisit[i];
            Pair<Integer, Integer> pair = map.getOrDefault(roomId, new Pair<>(roomId, 0));
            dp[i] = pair;
            set.add(i);
        }

        // 状态转移方程
        int cnt = 0;
        int nextRoomId = 0;
        while (!set.isEmpty()) {
            Pair<Integer, Integer> pair = map.getOrDefault(nextRoomId, new Pair<>(nextRoomId, 0));
            pair.setValue(pair.getValue() + 1);
            map.put(nextRoomId, pair);
            if (pair.getValue() % 2 == 1) {// isOdd
                nextRoomId = dp[nextRoomId].getKey();
            } else {
                nextRoomId = (nextRoomId + 1) % nextVisit.length;
            }
            set.remove(nextRoomId);
            cnt++;
        }
        return cnt ;
    }

    public static void main(String[] args) {
        _1997访问完所有房间的第一天 firstDayBeenInAllRooms = new _1997访问完所有房间的第一天();
        System.out.println(firstDayBeenInAllRooms.firstDayBeenInAllRooms(new int[]{0, 0}));
        System.out.println(firstDayBeenInAllRooms.firstDayBeenInAllRooms(new int[]{0, 0, 2}));
        System.out.println(firstDayBeenInAllRooms.firstDayBeenInAllRooms(new int[]{0, 1, 2, 0}));
    }
}