网站开发要跑道吗,亚马逊aws永久免费下载,吉安市建设规划局网站,网站备案 更名【LetMeFly】1997.访问完所有房间的第一天#xff1a;动态规划(DP)——4行主要代码(不需要什么前缀和)
力扣题目链接#xff1a;https://leetcode.cn/problems/first-day-where-you-have-been-in-all-the-rooms/
你需要访问 n 个房间#xff0c;房间从 0 到 n - 1 编号。同…【LetMeFly】1997.访问完所有房间的第一天动态规划(DP)——4行主要代码(不需要什么前缀和)
力扣题目链接https://leetcode.cn/problems/first-day-where-you-have-been-in-all-the-rooms/
你需要访问 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.length2 n 1050 nextVisit[i] i
解题方法动态规划(DP)
题目中明确说明了0 nextVisit[i] i也就是说每个房间第一次访问都会“往前回退”到nextVisit[i]而不会访问新的房间而第二次访问则会访问到“相邻的下一个房间”。
因此我们可以使用一个firstVisit数组其中firstVisit[i]代表房间i第一次被访问时的天数。
那么由房间i访问到房间i 1需要多久呢
首先需要花费一天访问到nextVisit[i]这个房间记为j接着需要花费firstVisit[i] - firstVisit[j]天再一次地由j访问到i最后再花费一天由i访问到i 1
因此首次访问到房间i 1的天数为firstVisit[i] 1 (firstVisit[i] - firstVisit[j]) 1 2 * firstVisit[i] - firstVisit[j] 2。
从房间1开始往后遍历到最后一间房间则firstVisit.back()记为答案。
时空复杂度
时间复杂度 O ( l e n ( n e x t V i s i t ) ) O(len(nextVisit)) O(len(nextVisit))空间复杂度 O ( l e n ( n e x t V i s i t ) ) O(len(nextVisit)) O(len(nextVisit))。其实不难发现nextVisit数组中每个值只会用到一次因此若将firstVisit保存在nextVisit数组中则可以以 O ( 1 ) O(1) O(1)的空间复杂度实现。
AC代码
C
typedef long long ll;
const ll MOD 1e9 7;
class Solution {
public:int firstDayBeenInAllRooms(vectorint nextVisit) {vectorll 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 Listclass 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_007return firstVisit[-1]同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/137119523
