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

【C++前后缀分解 动态规划】2100. 适合野炊的日子|1702

本文涉及知道点

C++前后缀分解
C++动态规划

LeetCode2100. 适合野炊的日子

你和朋友们准备去野炊。给你一个下标从 0 开始的整数数组 security ,其中 security[i] 是第 i 天的建议出行指数。日子从 0 开始编号。同时给你一个整数 time 。
如果第 i 天满足以下所有条件,我们称它为一个适合野炊的日子:
第 i 天前和后都分别至少有 time 天。
第 i 天前连续 time 天建议出行指数都是非递增的。
第 i 天后连续 time 天建议出行指数都是非递减的。
更正式的,第 i 天是一个适合野炊的日子当且仅当:security[i - time] >= security[i - time + 1] >= … >= security[i] <= … <= security[i + time - 1] <= security[i + time].
请你返回一个数组,包含 所有 适合野炊的日子(下标从 0 开始)。返回的日子可以 任意 顺序排列。
示例 1:
输入:security = [5,3,3,3,5,6,2], time = 2
输出:[2,3]
解释:
第 2 天,我们有 security[0] >= security[1] >= security[2] <= security[3] <= security[4] 。
第 3 天,我们有 security[1] >= security[2] >= security[3] <= security[4] <= security[5] 。
没有其他日子符合这个条件,所以日子 2 和 3 是适合野炊的日子。
示例 2:
输入:security = [1,1,1,1,1], time = 0
输出:[0,1,2,3,4]
解释:
因为 time 等于 0 ,所以每一天都是适合野炊的日子,所以返回每一天。
示例 3:
输入:security = [1,2,3,4,5,6], time = 2
输出:[]
解释:
没有任何一天的前 2 天建议出行指数是非递增的。
所以没有适合野炊的日子,返回空数组。
提示:
1 <= security.length <= 105
0 <= security[i], time <= 105

前后缀分解

n = security.length
left[i] 记录 以nums[i]结尾的最长非递增子数组的长度。
如果left[i] <= left[i-1]则left[i] = left[i-1]+1;否则left[i] =1 。
right[i]记录 以nums[i]开始的最长非递减子数组的长度。
如果left[i]和right[i]大于time,则是好日子。
right[n-1-i] 就是nums的转置数组的left[i]

代码

打开打包代码的方法兼述单元测试

核心代码

class Solution {public:vector<int> goodDaysToRobBank(vector<int>& security, int time) {m_iN = security.size();auto Do = [&](const vector<int>& security) {vector<int> ret(m_iN, 1);for (int i = 1; i < m_iN; i++) {if (security[i] <= security[i - 1]) {ret[i] = ret[i - 1] + 1;}}return ret;};auto left = Do(security);auto right = Do(vector<int>(security.rbegin(), security.rend()));vector<int> ret;for (int i = 0; i < m_iN; i++) {if ((left[i] > time) && (right[m_iN - 1 - i] > time)) {ret.emplace_back(i);}}return ret;}int m_iN;};

单元测试

	vector<int> security;int time;TEST_METHOD(TestMethod11){security = { 5, 3, 3, 3, 5, 6, 2 }, time = 2;auto res = Solution().goodDaysToRobBank(security, time);AssertEx({ 2,3 }, res);}TEST_METHOD(TestMethod12){security = { 1,1,1,1,1 }, time = 0;auto res = Solution().goodDaysToRobBank(security, time);AssertEx({ 0,1,2,3,4 }, res);}TEST_METHOD(TestMethod13){security = { 1,2,3,4,5,6 }, time = 2;auto res = Solution().goodDaysToRobBank(security, time);AssertEx({  }, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

相关文章:

【C++前后缀分解 动态规划】2100. 适合野炊的日子|1702

本文涉及知道点 C前后缀分解 C动态规划 LeetCode2100. 适合野炊的日子 你和朋友们准备去野炊。给你一个下标从 0 开始的整数数组 security &#xff0c;其中 security[i] 是第 i 天的建议出行指数。日子从 0 开始编号。同时给你一个整数 time 。 如果第 i 天满足以下所有条件…...

HarmonyOS 速记

目录 装饰器Entry(入口)Component(组件)State(状态)Preview(预览)PreviewerInspector 结构体structbuild自定义组件自定义 Custom 组件 容器Row(行) & Column(列)RelativeContainer(相对布局容器)marginpaddingGrid(网格容器)List(列表) 组件Image(图片)图片的填充模式 Tex…...

使用 Milvus、vLLM 和 Llama 3.1 搭建 RAG 应用

vLLM 是一个简单易用的 LLM 推理服务库。加州大学伯克利分校于 2024 年 7 月将 vLLM 作为孵化项目正式捐赠给 LF AI & Data Foundation 基金会。欢迎 vLLM 加入 LF AI & Data 大家庭&#xff01;&#x1f389; 在主流的 AI 应用架构中&#xff0c;大语言模型&#xff0…...

【springboot】父子工程项目搭建

父工程创建 1.新建一个spring项目 2.选择合适的springboot版本&#xff0c;点击【完成】&#xff0c;即创建父工程完毕 3.删除父工程中无用文件&#xff1a;src 创建子工程模块 1.右键项目名->新建&#xff08;news&#xff09;->模块&#xff08;Module&#xff09;…...

【Paper Reading】结合 NanoFlow 研究,优化大语言模型服务效率的探索

作者 王伟 PAI引擎团队 近年来&#xff0c;人工智能领域的快速发展推动了大型语言模型的广泛应用&#xff0c;随之而来的是对其服务效率的迫切需求。论文《NanoFlow&#xff1a;Towards Optimal Large Language Model Serving Throughput》提出了一种突破性的新型服务框架&…...

达芬奇竖屏导出有黑屏解决方案

文章目录 项目设置导出设置 初学达芬奇&#xff0c;导出的时候&#xff0c;总是有黑边。 经过研究&#xff0c;才发现导出的时候的分辨率和项目分辨率 2个地方都要设置&#xff0c;否则导出就会导致有黑边。 项目设置 点击 文件 选择项目设置 选择竖屏分辨率 导出设置...

Elasticsearch Java API 针对 Geohash7 网点进行分桶聚合

需求整理&#xff1a; geohash 7网格存储工作热度和学习热度数值&#xff0c;支持随机区域多个范围的热度聚合&#xff1b; 创建索引结构 索引文档需要包含 Geohash 网格、工作热度和学习热度等字段。可以在 Elasticsearch 中定义一个索引&#xff0c;确保 location 字段的类…...

Transformer学习(1):注意力机制

文章目录 什么是注意力如何实现注意注意力的计算过程总结 什么是注意力 在一张图像中&#xff0c;包含了各种信息&#xff0c;而我们会自动关注重要的信息。下图是注意力热力图&#xff0c;可以发现人们会注意兔子的脸这些重要信息。 而在深度学习中&#xff0c;输入数据包含…...

spring模块(六)spring event事件(3)广播与异步问题

发布事件和监听器之间默认是同步的&#xff1b;监听器则是广播形式。demo&#xff1a; event&#xff1a; package com.listener.demo.event;import com.listener.demo.dto.UserLogDTO; import org.springframework.context.ApplicationEvent;public class MyLogEvent extends…...

【Elasticsearch系列八】高阶使用

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

【H2O2|全栈】关于CSS(4)CSS基础(四)

目录 CSS基础知识 前言 准备工作 精灵图 概念 属性 案例 浮动 基础属性 清除浮动 案例 预告和回顾 后话 CSS基础知识 前言 本系列博客将分享层叠样式表&#xff08;CSS&#xff09;有关的知识点。 接下来的几期内容相对比较少&#xff0c;主要是对前面的内容进…...

node.js+Koa框架+MySQL实现注册登录

完整视频展示&#xff1a;https://item.taobao.com/item.htm?ftt&id831092436619&spma21dvs.23580594.0.0.52de2c1bg9gTfM 效果展示&#xff1a; 一、项目介绍 本项目是基于node.jsKoamysql的注册登录的项目,主要是给才学习node.js和Koa框架的萌新才写的。 二、项目…...

矢量化操作

约定 本文中的”向量”均指一维数组/张量,”矩阵”均值二维数组/张量 前言 在ML当中,向量和矩阵非常常见。由于之前使用C语言的惯性,本人经常会从标量的角度考虑向量和矩阵的运算,也就是用for循环来完成向量或矩阵的运算。实际上,for循环的风格比python内置的操作或pytor…...

【LeetCode】每日一题 2024_9_16 公交站间的距离(模拟)

前言 每天和你一起刷 LeetCode 每日一题~ LeetCode 启动&#xff01; 题目&#xff1a;公交站间的距离 代码与解题思路 func distanceBetweenBusStops(distance []int, start int, destination int) int {// 首先让 start > destination, 这两个谁大对结果没有影响&#…...

【Python笔记】PyCharm大模型项目环境配置

一、PyCharm创建新项目 二、更新pip版本 ...>python.exe -m pip install --upgrade pip 三、生成所需requirements配置文件 ...>pip freeze > requirements.txt 四、安装所需组件requirements.txt ...>pip install -r requirements.txt...

FPGA-Vivado-IP核-虚拟输入输出(VIO)

VIO IP核 背景介绍 Vivado中的VIO&#xff08;Virtual Input/Output&#xff0c;虚拟输入/输出&#xff09; IP核是一种用于调试和测试FPGA设计的IP核。当设计者通过JTAG接口与FPGA芯片连接时&#xff0c;在Vivado的Verilog代码中添加VIO IP核&#xff0c;就可以让设计者与FPG…...

使用knn算法对iris数据集进行分类

程序功能 使用 scikit-learn 库中的鸢尾花数据集&#xff08;Iris dataset&#xff09;&#xff0c;并基于 KNN&#xff08;K-Nearest Neighbors&#xff0c;K近邻&#xff09;算法进行分类&#xff0c;最后评估模型的准确率。 代码 from sklearn import datasets# 加载鸢尾…...

GEE Shapefile 格式转换 GeoJSON

在地理信息系统&#xff08;GIS&#xff09;领域&#xff0c;数据格式之间的转换是一项常见的需求。例如&#xff0c;将 Shapefile 格式转换为 GeoJSON 格式&#xff0c;对于上传数据到 Google Earth Engine (GEE) 尤其有用。本文将通过一个 Python 脚本的示例&#xff0c;实现…...

从kaggle竞赛零基础上手CV实战(Deepfake检测)

关注B站可以观看更多实战教学视频&#xff1a;hallo128的个人空间 从kaggle竞赛零基础上手CV实战 从kaggle竞赛零基础上手CV实战&#xff08;Deepfake检测&#xff09; 目录 从kaggle竞赛零基础上手CV实战&#xff08;Deepfake检测&#xff09;背景介绍学习地址课程大纲课程特色…...

Linux cat命令详解使用:高效文本内容管理

cat是 Linux 中最常用的命令之一&#xff0c;主要用于查看文件内容、合并文件以及重定向输出。它可以一次性显示文件内容&#xff0c;也可以将多个文件的内容串联显示出来。 基本语法 cat [选项] [文件...]常用参数选项 -n&#xff1a;为输出的每一行添加行号。-b&#xff1…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

手机平板能效生态设计指令EU 2023/1670标准解读

手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读&#xff0c;综合法规核心要求、最新修正及企业合规要点&#xff1a; 一、法规背景与目标 生效与强制时间 发布于2023年8月31日&#xff08;OJ公报&…...

Spring Security 认证流程——补充

一、认证流程概述 Spring Security 的认证流程基于 过滤器链&#xff08;Filter Chain&#xff09;&#xff0c;核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤&#xff1a; 用户提交登录请求拦…...