【LetMeFly】1997.訪問完所有房間的第一天：動態(tài)規(guī)劃(DP)——4行主要代碼(不需要什么前綴和)

力扣題目鏈接：https://leetcode.cn/problems/first-day-where-you-have-been-in-all-the-rooms/

你需要訪問?n 個房間，房間從 0 到 n - 1 編號。同時，每一天都有一個日期編號，從 0 開始，依天數(shù)遞增。你每天都會訪問一個房間。

最開始的第 0 天，你訪問?0 號房間。給你一個長度為 n 且 下標從 0 開始 的數(shù)組 nextVisit 。在接下來的幾天中，你訪問房間的 次序 將根據(jù)下面的 規(guī)則 決定：

• 假設某一天，你訪問?i 號房間。
• 如果算上本次訪問，訪問?i 號房間的次數(shù)為 奇數(shù) ，那么 第二天 需要訪問?nextVisit[i] 所指定的房間，其中 0 <= nextVisit[i] <= i 。
• 如果算上本次訪問，訪問?i 號房間的次數(shù)為 偶數(shù) ，那么 第二天 需要訪問?(i + 1) mod n 號房間。

請返回你訪問完所有房間的第一天的日期編號。題目數(shù)據(jù)保證總是存在這樣的一天。由于答案可能很大，返回對 109 + 7 取余后的結果。

?

示例 1：

輸入：nextVisit = [0,0]
輸出：2
解釋：
- 第 0 天，你訪問房間 0 。訪問 0 號房間的總次數(shù)為 1 ，次數(shù)為奇數(shù)。
? 下一天你需要訪問房間的編號是 nextVisit[0] = 0
- 第 1 天，你訪問房間 0 。訪問 0 號房間的總次數(shù)為 2 ，次數(shù)為偶數(shù)。
? 下一天你需要訪問房間的編號是 (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

解題方法：動態(tài)規(guī)劃(DP)

題目中明確說明了0 <= nextVisit[i] <= i，也就是說每個房間第一次訪問都會“往前回退”到nextVisit[i]而不會訪問新的房間，而第二次訪問則會訪問到“相鄰的下一個房間”。

因此我們可以使用一個firstVisit數(shù)組，其中firstVisit[i]代表房間i第一次被訪問時的天數(shù)。

那么，由房間i訪問到房間i + 1需要多久呢？

• 首先需要花費一天訪問到nextVisit[i]這個房間（記為j）
• 接著需要花費firstVisit[i] - firstVisit[j]天再一次地由j訪問到i
• 最后再花費一天由i訪問到i + 1

因此首次訪問到房間i + 1的天數(shù)為firstVisit[i] + 1 + (firstVisit[i] - firstVisit[j]) + 1 = 2 * firstVisit[i] - firstVisit[j] + 2。

從房間1開始往后遍歷到最后一間房間，則firstVisit.back()記為答案。

時空復雜度

• 時間復雜度$O(len(nextVisit))$
• 空間復雜度$O(len(nextVisit))$。其實不難發(fā)現(xiàn)nextVisit數(shù)組中每個值只會用到一次，因此若將firstVisit保存在nextVisit數(shù)組中則可以以$O(1)$的空間復雜度實現(xiàn)。

AC代碼

C++

typedef long long ll;
const ll MOD = 1e9 + 7;
class Solution {
public:
    int firstDayBeenInAllRooms(vector<int>& nextVisit) {
        vector<ll> firstVisit(nextVisit.size());
        for (int i = 1; i < nextVisit.size(); i++) {
            firstVisit[i] = (firstVisit[i - 1] * 2 - firstVisit[nextVisit[i - 1]] + 2 + MOD) % MOD;  // 記得先加個MOD再對MOD取模，否則可能是負結果。
        }
        return firstVisit.back();
    }
};

Python

from typing import List

class Solution:
    def firstDayBeenInAllRooms(self, nextVisit: List[int]) -> int:
        firstVisit = [0] * len(nextVisit)
        for i in range(1, len(nextVisit)):
            firstVisit[i] = (firstVisit[i - 1] * 2 - firstVisit[nextVisit[i - 1]] + 2 + 1_000_000_007) % 1_000_000_007
        return firstVisit[-1]

同步發(fā)文于CSDN和我的個人博客，原創(chuàng)不易，轉載經(jīng)作者同意后請附上原文鏈接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/137119523文章來源地址http://www.zghlxwxcb.cn/news/detail-851155.html

到了這里，關于LeetCode 1997.訪問完所有房間的第一天：動態(tài)規(guī)劃(DP)——4行主要代碼(不需要什么前綴和)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！