当前位置: 首页 > news >正文

leetcode 1997.访问完所有房间的第一天

思路:动态规划+前缀和

这道题还是很难的,因为你如果需要推出状态方程是很难想的。

在题中我们其实可以发现,这里在访问nextVisit数组的过程中,其实就是对于当前访问的房子之前的房子进行了回访。

怎么说呢?比如你现在在第i个房间里,你为什么会在第i个房间呢?是因为前面的房间你都已经访问了偶数次才会到达这里的吧?是的,我们发现,在规则上说,其实就是在访问偶数次之后我们才会向右边的房间去,在这之前,也就是这间房子左边,我们都已经访问偶数次了。

那我们不妨可以看看,从某个房间到达奇数次-->这个房间到达偶数次这个状态是怎么样的。我们发现不论你选取哪一个房子,都是要经历这个过程的,所以我们可以把状态方程f的含义定为:

访问第i间房子的奇数次到访问第i间房子的偶数次所需要的天数。这就是f[i]的含义。

那么我们可以推知,从第j间房子访问到第i间房子的总天数就是f[i]=f[j]+f[j+1]+...+f[i-1]+2.

为什么需要+2呢?因为你在第一次访问第i间房子之后,你需要回访,然后再回来的时候才会访问偶数次,也就是访问了2次,也就是两天,其他的那些和,其实就是你回访其他房间所用的时间。

好了,如果我们真需要处理这些和的话,势必会让时间复杂度变成n**2。怎么才能进行优化呢?

说到求和,我们会想到一个知识点,那就是前缀和,前缀和会用On的时间来进行操作,这样的话就好说了,我们就用前缀和进行优化。

设s为前缀和数组,那么s[0]=0,至于为什么需要这样,参考一下灵神在这道题里面的题解的解释:303. 区域和检索 - 数组不可变 - 力扣(LeetCode)

那么,就这样推下去的话:s[1]=f[0],s[2]=f[1]+f[0]......s[i+1]=f[i]+s[i]

而我们上面写的f[i]也就可以化简为:f[i]=s[i]-s[j]+2,我们把这两个式子结合一下,

就变成了:s[i+1]=s[i]*2-s[j]+2。这样就算是完成了

class Solution {
public:int firstDayBeenInAllRooms(vector<int>& nextVisit) {int n=nextVisit.size();const int mod=1e9+7;vector<long>s(n);for(int i=0;i<n-1;i++){int j=nextVisit[i];s[i+1]=(s[i]*2-s[j]+2+mod)%mod;}return s[n-1];}
};

相关文章:

leetcode 1997.访问完所有房间的第一天

思路&#xff1a;动态规划前缀和 这道题还是很难的&#xff0c;因为你如果需要推出状态方程是很难想的。 在题中我们其实可以发现&#xff0c;这里在访问nextVisit数组的过程中&#xff0c;其实就是对于当前访问的房子之前的房子进行了回访。 怎么说呢&#xff1f;比如你现在…...

【InternLM 实战营第二期笔记】书生·浦语大模型全链路开源体系及InternLM2技术报告笔记

大模型 大模型成为发展通用人工智能的重要途径 专用模型&#xff1a;针对特定任务&#xff0c;一个模型解决一个问题 通用大模型&#xff1a;一个模型应对多种任务、多种模态 书生浦语大模型开源历程 2023.6.7&#xff1a;InternLM千亿参数语言大模型发布 2023.7.6&#…...

Netty对Channel事件的处理以及空轮询Bug的解决

继续上一篇Netty文章&#xff0c;这篇文章主要分析Netty对Channel事件的处理以及空轮询Bug的解决 当Netty中采用循环处理事件和提交的任务时 由于此时我在客户端建立连接&#xff0c;此时服务端没有提交任何任务 此时select方法让Selector进入无休止的阻塞等待 此时selectCnt进…...

【PostgreSQL】- 1.1 在 Debian 12 上安装 PostgreSQL 15

官方说明参考 &#xff08;原文 PostgreSQL&#xff1a;Linux 下载 &#xff08;Debian&#xff09;&#xff09; 默认情况下&#xff0c;PostgreSQL 在所有 Debian 版本中都可用。但是&#xff0c; Debians 的稳定版本“快照”了特定版本的 PostgreSQL 然后在该 Debian 版本的…...

第4章.精通标准提示,引领ChatGPT精准输出

标准提示 标准提示&#xff0c;是引导ChatGPT输出的一个简单方法&#xff0c;它提供了一个具体的任务让模型完成。 如果你要生成一篇新闻摘要。你只要发送指示词&#xff1a;汇总这篇新闻 : …… 提示公式&#xff1a;生成[任务] 生成新闻文章的摘要&#xff1a; 任务&#x…...

HTTP状态 405 - 方法不允许

方法有问题。 用Post发的请求&#xff0c;然后用Put接收的。 大家也可以看看是不是有这种问题 <body><h1>HTTP状态 405 - 方法不允许</h1><hr class"line" /><p><b>类型</b> 状态报告</p><p><b>消息…...

题目 2898: 二维数组回形遍历

题目描述: 给定一个row行col列的整数数组array&#xff0c;要求从array[0][0]元素开始&#xff0c;按回形从外向内顺时针顺序遍历整个数组。如图所示&#xff1a; 代码: package lanqiao;import java.math.BigInteger; import java.util.*;public class Main {public static …...

Git命令上传本地项目至github

记录如何创建个人仓库并上传已有代码至github in MacOS环境 0. 首先下载git 方法很多 这里就不介绍了 1. Github Create a new repository 先在github上创建一个空仓库&#xff0c;用于一会儿链接项目文件&#xff0c;按照自己的需求设置name和是否private 2.push an exis…...

机器学习之决策树现成的模型使用

目录 须知 DecisionTreeClassifier sklearn.tree.plot_tree cost_complexity_pruning_path(X_train, y_train) CART分类树算法 基尼指数 分类树的构建思想 对于离散的数据 对于连续值 剪枝策略 剪枝是什么 剪枝的分类 预剪枝 后剪枝 后剪枝策略体现之威斯康辛州乳…...

【python分析实战】成本:揭示电商平台月度开支与成本结构占比 - 过于详细 【收藏】

重点关注本文思路&#xff0c;用python分析&#xff0c;方便大家实验复现&#xff0c;代码每次都用全量的&#xff0c;其他工具自行选择。 全文3000字&#xff0c;阅读10min&#xff0c;操作1小时 企业案例实战欢迎关注专栏 每日更新&#xff1a;https://blog.csdn.net/cciehl/…...

新网站收录时间是多久,新建网站多久被百度收录

对于新建的网站而言&#xff0c;被搜索引擎收录是非常重要的一步&#xff0c;它标志着网站的正式上线和对外开放。然而&#xff0c;新网站被搜索引擎收录需要一定的时间&#xff0c;而且时间长短受多种因素影响。本文将探讨新网站收录需要多长时间&#xff0c;以及新建网站多久…...

通过Caliper进行压力测试程序,且汇总压力测试问题解决

环境要求 第一步. 配置基本环境 部署Caliper的计算机需要有外网权限;操作系统版本需要满足以下要求:Ubuntu >= 16.04、CentOS >= 7或MacOS >= 10.14;部署Caliper的计算机需要安装有以下软件:python 2.7、make、g++(gcc-c++)、gcc及git。第二步. 安装NodeJS # …...

LabVIEW比例流量阀自动测试系统

LabVIEW比例流量阀自动测试系统 开发了一套基于LabVIEW编程和PLC控制的比例流量阀自动测试系统。通过引入改进的FCMAC算法至测试回路的压力控制系统&#xff0c;有效提升了压力控制效果&#xff0c;展现了系统的设计理念和实现方法。 项目背景&#xff1a; 比例流量阀在液压…...

安卓U3D逆向从Assembly-CSharp到il2cpp

随着unity技术的发展及厂商对于脚本源码的保护&#xff0c;很大一部分U3D应用的scripting backend已经由mono转为了il2cpp&#xff0c;本文从unity简单应用的制作讲起&#xff0c;介绍U3D应用脚本的Assembly-CSharp.dll的逆向及il2cpp.so的逆向分析。 目录如下&#xff1a; 0…...

计算机网络——30SDN控制平面

SDN控制平面 SDN架构 数据平面交换机 快速、简单&#xff0c;商业化交换设备采用硬件实现通用转发功能流表被控制器计算和安装基于南向API&#xff0c;SDN控制器访问基于流的交换机 定义了哪些可以被控制哪些不能 也定义了和控制器的协议 SDN控制器&#xff08;网络OS&#…...

Obsidian插件-高亮块(Admonition)

在插件市场里面搜索Admonition并安装插件&#xff0c;就可以使用高亮块了。 添加高亮块 用法稍微有一些不同。按照下面的格式&#xff0c;输入Markdown就可以创建一个高亮块。 内容内容内容输入*ad-*会出现相应的类型可以选择...

jHipster 之 webflux-前端用EventSource处理sse变成了批量处理而非实时处理

现象&#xff1a; const eventSource new EventSource(API_URL5);eventSource.onmessage streamEvent > {console.log(a message is come in--------->);const content streamEvent.data;console.log(Received content: content);};前端用EventSource 处理webflux的…...

原型链-(前端面试 2024 版)

来讲一讲原型链 原型链只存在于函数之中 四个规则 1、引用类型&#xff0c;都具有对象特性&#xff0c;即可自由扩展属性。 2、引用类型&#xff0c;都有一个隐式原型 __proto__ 属性&#xff0c;属性值是一个普通的对象。 3、引用类型&#xff0c;隐式原型 __proto__ 的属…...

网络套接字补充——UDP网络编程

五、UDP网络编程 ​ 1.对于服务器使用智能指针维护生命周期&#xff1b;2.创建UDP套接字&#xff1b;3.绑定端口号&#xff0c;包括设置服务器端口号和IP地址&#xff0c;端口号一般是2字节使用uint16_t&#xff0c;而IP地址用户习惯使用点分十进制格式所以传入的是string类型…...

自动化测试 —— Pytest fixture及conftest详解

前言 fixture是在测试函数运行前后&#xff0c;由pytest执行的外壳函数。fixture中的代码可以定制&#xff0c;满足多变的测试需求&#xff0c;包括定义传入测试中的数据集、配置测试前系统的初始状态、为批量测试提供数据源等等。fixture是pytest的精髓所在&#xff0c;类似u…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...