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

相关文章

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景:会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作?今天我要分享的Pyth... 目录一、项目概述:不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL

jupyter代码块没有运行图标的解决方案

《jupyter代码块没有运行图标的解决方案》:本文主要介绍jupyter代码块没有运行图标的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录jupyter代码块没有运行图标的解决1.找到Jupyter notebook的系统配置文件2.这时候一般会搜索到