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.访问完所有房间的第一天
思路:动态规划前缀和 这道题还是很难的,因为你如果需要推出状态方程是很难想的。 在题中我们其实可以发现,这里在访问nextVisit数组的过程中,其实就是对于当前访问的房子之前的房子进行了回访。 怎么说呢?比如你现在…...
【InternLM 实战营第二期笔记】书生·浦语大模型全链路开源体系及InternLM2技术报告笔记
大模型 大模型成为发展通用人工智能的重要途径 专用模型:针对特定任务,一个模型解决一个问题 通用大模型:一个模型应对多种任务、多种模态 书生浦语大模型开源历程 2023.6.7:InternLM千亿参数语言大模型发布 2023.7.6&#…...
Netty对Channel事件的处理以及空轮询Bug的解决
继续上一篇Netty文章,这篇文章主要分析Netty对Channel事件的处理以及空轮询Bug的解决 当Netty中采用循环处理事件和提交的任务时 由于此时我在客户端建立连接,此时服务端没有提交任何任务 此时select方法让Selector进入无休止的阻塞等待 此时selectCnt进…...
【PostgreSQL】- 1.1 在 Debian 12 上安装 PostgreSQL 15
官方说明参考 (原文 PostgreSQL:Linux 下载 (Debian)) 默认情况下,PostgreSQL 在所有 Debian 版本中都可用。但是, Debians 的稳定版本“快照”了特定版本的 PostgreSQL 然后在该 Debian 版本的…...
第4章.精通标准提示,引领ChatGPT精准输出
标准提示 标准提示,是引导ChatGPT输出的一个简单方法,它提供了一个具体的任务让模型完成。 如果你要生成一篇新闻摘要。你只要发送指示词:汇总这篇新闻 : …… 提示公式:生成[任务] 生成新闻文章的摘要: 任务&#x…...
HTTP状态 405 - 方法不允许
方法有问题。 用Post发的请求,然后用Put接收的。 大家也可以看看是不是有这种问题 <body><h1>HTTP状态 405 - 方法不允许</h1><hr class"line" /><p><b>类型</b> 状态报告</p><p><b>消息…...
题目 2898: 二维数组回形遍历
题目描述: 给定一个row行col列的整数数组array,要求从array[0][0]元素开始,按回形从外向内顺时针顺序遍历整个数组。如图所示: 代码: 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上创建一个空仓库,用于一会儿链接项目文件,按照自己的需求设置name和是否private 2.push an exis…...
机器学习之决策树现成的模型使用
目录 须知 DecisionTreeClassifier sklearn.tree.plot_tree cost_complexity_pruning_path(X_train, y_train) CART分类树算法 基尼指数 分类树的构建思想 对于离散的数据 对于连续值 剪枝策略 剪枝是什么 剪枝的分类 预剪枝 后剪枝 后剪枝策略体现之威斯康辛州乳…...
【python分析实战】成本:揭示电商平台月度开支与成本结构占比 - 过于详细 【收藏】
重点关注本文思路,用python分析,方便大家实验复现,代码每次都用全量的,其他工具自行选择。 全文3000字,阅读10min,操作1小时 企业案例实战欢迎关注专栏 每日更新:https://blog.csdn.net/cciehl/…...
新网站收录时间是多久,新建网站多久被百度收录
对于新建的网站而言,被搜索引擎收录是非常重要的一步,它标志着网站的正式上线和对外开放。然而,新网站被搜索引擎收录需要一定的时间,而且时间长短受多种因素影响。本文将探讨新网站收录需要多长时间,以及新建网站多久…...
通过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算法至测试回路的压力控制系统,有效提升了压力控制效果,展现了系统的设计理念和实现方法。 项目背景: 比例流量阀在液压…...
安卓U3D逆向从Assembly-CSharp到il2cpp
随着unity技术的发展及厂商对于脚本源码的保护,很大一部分U3D应用的scripting backend已经由mono转为了il2cpp,本文从unity简单应用的制作讲起,介绍U3D应用脚本的Assembly-CSharp.dll的逆向及il2cpp.so的逆向分析。 目录如下: 0…...
计算机网络——30SDN控制平面
SDN控制平面 SDN架构 数据平面交换机 快速、简单,商业化交换设备采用硬件实现通用转发功能流表被控制器计算和安装基于南向API,SDN控制器访问基于流的交换机 定义了哪些可以被控制哪些不能 也定义了和控制器的协议 SDN控制器(网络OS&#…...
Obsidian插件-高亮块(Admonition)
在插件市场里面搜索Admonition并安装插件,就可以使用高亮块了。 添加高亮块 用法稍微有一些不同。按照下面的格式,输入Markdown就可以创建一个高亮块。 内容内容内容输入*ad-*会出现相应的类型可以选择...
jHipster 之 webflux-前端用EventSource处理sse变成了批量处理而非实时处理
现象: 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、引用类型,都具有对象特性,即可自由扩展属性。 2、引用类型,都有一个隐式原型 __proto__ 属性,属性值是一个普通的对象。 3、引用类型,隐式原型 __proto__ 的属…...
网络套接字补充——UDP网络编程
五、UDP网络编程 1.对于服务器使用智能指针维护生命周期;2.创建UDP套接字;3.绑定端口号,包括设置服务器端口号和IP地址,端口号一般是2字节使用uint16_t,而IP地址用户习惯使用点分十进制格式所以传入的是string类型…...
自动化测试 —— Pytest fixture及conftest详解
前言 fixture是在测试函数运行前后,由pytest执行的外壳函数。fixture中的代码可以定制,满足多变的测试需求,包括定义传入测试中的数据集、配置测试前系统的初始状态、为批量测试提供数据源等等。fixture是pytest的精髓所在,类似u…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?
Redis 的发布订阅(Pub/Sub)模式与专业的 MQ(Message Queue)如 Kafka、RabbitMQ 进行比较,核心的权衡点在于:简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
OD 算法题 B卷【正整数到Excel编号之间的转换】
文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的:a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...
论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing
Muffin 论文 现有方法 CRADLE 和 LEMON,依赖模型推理阶段输出进行差分测试,但在训练阶段是不可行的,因为训练阶段直到最后才有固定输出,中间过程是不断变化的。API 库覆盖低,因为各个 API 都是在各种具体场景下使用。…...
书籍“之“字形打印矩阵(8)0609
题目 给定一个矩阵matrix,按照"之"字形的方式打印这个矩阵,例如: 1 2 3 4 5 6 7 8 9 10 11 12 ”之“字形打印的结果为:1,…...
