LeetCode 1997.访问完所有房间的第一天:动态规划(DP)——4行主要代码(不需要什么前缀和)

本文主要是介绍LeetCode 1997.访问完所有房间的第一天:动态规划(DP)——4行主要代码(不需要什么前缀和),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【LetMeFly】1997.访问完所有房间的第一天:动态规划(DP)——4行主要代码(不需要什么前缀和)

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

你需要访问 n 个房间,房间从 0n - 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

解题方法:动态规划(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(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 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和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/137119523

这篇关于LeetCode 1997.访问完所有房间的第一天:动态规划(DP)——4行主要代码(不需要什么前缀和)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/859452

相关文章

使用C#代码计算数学表达式实例

《使用C#代码计算数学表达式实例》这段文字主要讲述了如何使用C#语言来计算数学表达式,该程序通过使用Dictionary保存变量,定义了运算符优先级,并实现了EvaluateExpression方法来... 目录C#代码计算数学表达式该方法很长,因此我将分段描述下面的代码片段显示了下一步以下代码显示该方法如

通过C#获取PDF中指定文本或所有文本的字体信息

《通过C#获取PDF中指定文本或所有文本的字体信息》在设计和出版行业中,字体的选择和使用对最终作品的质量有着重要影响,然而,有时我们可能会遇到包含未知字体的PDF文件,这使得我们无法准确地复制或修改文... 目录引言C# 获取PDF中指定文本的字体信息C# 获取PDF文档中用到的所有字体信息引言在设计和出

VUE动态绑定class类的三种常用方式及适用场景详解

《VUE动态绑定class类的三种常用方式及适用场景详解》文章介绍了在实际开发中动态绑定class的三种常见情况及其解决方案,包括根据不同的返回值渲染不同的class样式、给模块添加基础样式以及根据设... 目录前言1.动态选择class样式(对象添加:情景一)2.动态添加一个class样式(字符串添加:情

Python 标准库time时间的访问和转换问题小结

《Python标准库time时间的访问和转换问题小结》time模块为Python提供了处理时间和日期的多种功能,适用于多种与时间相关的场景,包括获取当前时间、格式化时间、暂停程序执行、计算程序运行时... 目录模块介绍使用场景主要类主要函数 - time()- sleep()- localtime()- g

python多进程实现数据共享的示例代码

《python多进程实现数据共享的示例代码》本文介绍了Python中多进程实现数据共享的方法,包括使用multiprocessing模块和manager模块这两种方法,具有一定的参考价值,感兴趣的可以... 目录背景进程、进程创建进程间通信 进程间共享数据共享list实践背景 安卓ui自动化框架,使用的是

使用Python实现批量访问URL并解析XML响应功能

《使用Python实现批量访问URL并解析XML响应功能》在现代Web开发和数据抓取中,批量访问URL并解析响应内容是一个常见的需求,本文将详细介绍如何使用Python实现批量访问URL并解析XML响... 目录引言1. 背景与需求2. 工具方法实现2.1 单URL访问与解析代码实现代码说明2.2 示例调用

SpringBoot生成和操作PDF的代码详解

《SpringBoot生成和操作PDF的代码详解》本文主要介绍了在SpringBoot项目下,通过代码和操作步骤,详细的介绍了如何操作PDF,希望可以帮助到准备通过JAVA操作PDF的你,项目框架用的... 目录本文简介PDF文件简介代码实现PDF操作基于PDF模板生成,并下载完全基于代码生成,并保存合并P

SpringCloud配置动态更新原理解析

《SpringCloud配置动态更新原理解析》在微服务架构的浩瀚星海中,服务配置的动态更新如同魔法一般,能够让应用在不重启的情况下,实时响应配置的变更,SpringCloud作为微服务架构中的佼佼者,... 目录一、SpringBoot、Cloud配置的读取二、SpringCloud配置动态刷新三、更新@R

SpringBoot基于MyBatis-Plus实现Lambda Query查询的示例代码

《SpringBoot基于MyBatis-Plus实现LambdaQuery查询的示例代码》MyBatis-Plus是MyBatis的增强工具,简化了数据库操作,并提高了开发效率,它提供了多种查询方... 目录引言基础环境配置依赖配置(Maven)application.yml 配置表结构设计demo_st

SpringCloud集成AlloyDB的示例代码

《SpringCloud集成AlloyDB的示例代码》AlloyDB是GoogleCloud提供的一种高度可扩展、强性能的关系型数据库服务,它兼容PostgreSQL,并提供了更快的查询性能... 目录1.AlloyDBjavascript是什么?AlloyDB 的工作原理2.搭建测试环境3.代码工程1.