LeetCode---402周赛
题目列表
3184. 构成整天的下标对数目 I
3185. 构成整天的下标对数目 II
3186. 施咒的最大总伤害
3187. 数组中的峰值
一、构成整天的下标对数目 I & II
可以直接二重for循环暴力遍历出所有的下标对,然后统计符合条件的下标对数目返回。代码如下
class Solution {
public:int countCompleteDayPairs(vector<int>& hours) {int n = hours.size(), ans = 0;for(int i = 0; i < n; i++) {for(int j = 0; j < i; j++){if((hours[i]+hours[j])%24==0)ans++;}}return ans;}
};
能不能优化呢?或者说能否去掉一层循环,用一次遍历计算出答案?
我们来思考一下内层循环的作用是什么,就是看前面的数字能否和当前数字能否组成能被24整除的数,也就是说只要我们在遍历的同时,统计满足加起来能被24的整除的数的出现次数,就能在O(1)的时间内得到与当前数字匹配的数字个数,从而降低时间复杂度。
如何得知两个数加起来能被24整除?只要知道它们的%24的值即可,比如一个数%24=20,那么我们只要找%24=4的数字即可,故代码如下
class Solution {
public:int countCompleteDayPairs(vector<int>& hours) {int cnt[24]{};int ans = 0;for(auto x:hours) {ans += cnt[(24-x%24)%24]; // (24-x%24)%24 用来计算另一个数%24的余数,为了防止出现24-0 = 24 的情况,故需要(...)%24cnt[x%24]++;}return ans;}
};
二、施咒的最大总伤害
先将数组排序,这样我们从前往后选咒语只要考虑当前咒语伤害是否大于前一个选择的咒语+2即可,当然咒语伤害相同可以同时被选中,所以我们还可以统计伤害相同的咒语的出现次数,然后将数组去重。最终,我们只要考虑当前咒语伤害是否大于前一个选择的咒语+2即可。
状态定义:f[i]表示前i个咒语中能得到的最大伤害
状态转移方程:
- 选当前咒语,f[i] = f[j] + cnt[x]*x,x = power[i],f[j]为满足power[j] + 2 < power[i]的最接近当前位置的值
- 不选当前咒语,f[i] = f[i-1]
故 f[i] = max( f[i-1],f[j] + cnt[x]*x),在遍历 j 的时候,我们不用每次都从头开始,j 只会变大,有点类似滑动窗口
代码如下
class Solution {using LL = long long;
public:long long maximumTotalDamage(vector<int>& power) {// 统计相同的咒语的出现次数unordered_map<int,int> mp;for(auto x:power) mp[x]++;// 排序 + 去重sort(power.begin(),power.end());power.erase(unique(power.begin(),power.end()),power.end());int n = power.size();LL ans = 0, j = 0;// f[i] 表示前i个咒语中的施咒最大总伤害// f[i] = max(f[i-1],f[j] + mp[x]*x) x = power[i]vector<LL> f(n+1); for(int i = 0; i < n; i++) {while(power[j] + 2 < power[i])j++;f[i+1] = max(f[i], f[j] + (LL)mp[power[i]]*power[i]);ans = max(f[i+1], ans);}return ans;}
};
三、数组中的峰值
这题一看题目要求,单点修改 + 区间查询,可以用树状数组,也可以用线段树,代码如下
// 树状数组
struct BIT
{vector<int> t;BIT(int n):t(n+1){}void update(int i, int val){while(i < t.size()) {t[i] += val;i += (i&-i);}}int pre_sum(int i) {int res = 0;while(i > 0) {res += t[i];i -= (i&-i);}return res;}int query(int l, int r){if(l > r) return 0;return pre_sum(r) - pre_sum(l);}
};
class Solution {
public:vector<int> countOfPeaks(vector<int>& nums, vector<vector<int>>& q) {int n = nums.size();BIT t(n);auto update = [&](int i, int val) {if(nums[i] > nums[i-1] && nums[i] > nums[i+1])t.update(i+1,val);};for(int i = 1; i < n-1; i++) {update(i,1);}vector<int> ans;for(auto v:q) {if(v[0]==1) { // 区间查询ans.push_back(t.query(v[1]+1,v[2])); // 注意查询的区间,由于查询的子数组的左右端点不能算作峰值,并且树状数组的下标是从1开始的,并且使用前缀和相减得到区间内的峰值}else{ // 单点修改int x = v[1];// 先将可能会发生改变的点复原for(int i = max(x-1,1); i <= min(x+1,n-2); i++) {update(i,-1);}nums[x] = v[2];// 再重新更新可能会发生变化的点for(int i = max(x-1,1); i <= min(x+1,n-2); i++) {update(i,1);}}}return ans;}
};// 线段树
struct SegTree
{vector<int> t;SegTree(int n): t(n<<2){}void up(int o) {t[o] = t[o*2+1] + t[o*2+2];}void build(const vector<int>&a,int o,int l,int r) {if(l == r) {t[o] = 1;return;}int mid = (l + r) >> 1;build(a, o*2+1, l, mid);build(a, o*2+2, mid+1, r);up(o);}void update(int o,int l, int r, int i, int val) {if(l==r){t[o] = val;return;}int mid = (l + r) >> 1;if(i <= mid) update(o*2+1, l, mid, i, val);else update(o*2+2, mid+1, r, i, val);up(o);}int query(int o, int l, int r, int ql, int qr) {if(ql > qr) return 0;if(ql <= l && r <= qr)return t[o];int res = 0;int mid = (l + r) >> 1;if(mid >= ql) res += query(o*2+1, l, mid, ql, qr);if(mid < qr) res += query(o*2+2, mid+1, r, ql, qr);return res;}
};
class Solution {
public:vector<int> countOfPeaks(vector<int>& nums, vector<vector<int>>& q) {int n = nums.size();SegTree st(n);auto update = [&](int i, int val) {if(nums[i] > nums[i-1] && nums[i] > nums[i+1]) {st.update(0,0,n-1,i,val);}};for(int i = 1; i < n-1; i++) {update(i,1);}vector<int> ans;for(auto v:q) {if(v[0]==1) { // 区间查询ans.push_back(st.query(0,0,n-1,v[1]+1,v[2]-1));}else{ // 单点修改int x = v[1];for(int i = max(x-1,1); i <= min(x+1,n-2); i++) {update(i,0);}nums[x] = v[2];for(int i = max(x-1,1); i <= min(x+1,n-2); i++) {update(i,1);}}}return ans;}
};
相关文章:

LeetCode---402周赛
题目列表 3184. 构成整天的下标对数目 I 3185. 构成整天的下标对数目 II 3186. 施咒的最大总伤害 3187. 数组中的峰值 一、构成整天的下标对数目 I & II 可以直接二重for循环暴力遍历出所有的下标对,然后统计符合条件的下标对数目返回。代码如下 class So…...
循环冗余校验
循环冗余校验(Cyclic Redundancy Check,简称CRC)是一种广泛使用的错误检测编码技术,用于检测数据在传输或存储过程中是否发生错误。CRC通过在数据后面添加一个校验值(通常称为CRC码或CRC校验和)来实现错误检…...
resample sensor
resample sensor 的一个问题。 背景: 项目要求,发送多个数据到 sensor-hal 上去,发现无论怎样,在 sensor-hal 上都 只有一个数据。 resample sensor 是重新采样,这个怎么理解的,我的理解是: 假设 sensor 采…...

【Linux】多线程的相关知识点
一、线程安全 1.1 可重入 VS 线程安全 1.1.1 概念 线程安全:多个线程并发执行同一段代码时,不会出现不同的结果。常见对全局变量或者静态变量进行操作,并且没有锁的保护的情况下,会出现问题。重入:同一个函数被不同…...
Java反射详解
Java反射 一.什么是反射 我们使用的一些像框架,tomcat,或者一些其他的组件(jackson 对象–>json)。他们可以做到给他什么类名,就可以创建给定类的对象,并调用该对象的方法和属性。这是如何做到的? 当他们加载我们…...
Spring Boot与Apache Kafka集成的深度指南
Spring Boot与Apache Kafka集成的深度指南 大家好,我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿! 在现代分布式系统中,消息队列的作用愈发重要࿰…...

甄选版“论软件系统架构评估”,软考高级论文,系统架构设计师论文
论文真题 对于软件系统,尤其是大规模的复杂软件系统来说,软件的系统架构对于确保最终系统的质量具有十分重要的意义,不恰当的系统架构将给项目开发带来高昂的代价和难以避免的灾难。对一个系统架构进行评估,是为了:分析现有架构存在的潜在风险,检验设计中提出的质量需求,…...

uniapp开发企业微信内部应用
最近一直忙着开发项目,终于1.0版本开发完成,抽时间自己总结下在项目开发中遇到的技术点。此次项目属于自研产品,公司扩展业务,需要在企业微信中开发内部应用。因为工作中使用的是钉钉,很少使用企业微信,对于…...
0122__linux之eventfd理解
linux之eventfd理解-CSDN博客 Linux fd 系列 — eventfd 是什么?-CSDN博客...
数学建模 —— 查找数据
目录 百度搜索技巧 完全匹配搜索:查询词的外边加上双引号“ ” 标题必含关键词:查询词前加上intitle: 搜索文档:空格再输入filetype:文件格式 去掉不想要的:查询词后面加空格后加减号与关键字 知网查文献 先看知网的硕博士…...

合并有序链表
合并有序链表 图解代码如下 图解 虽然很复杂,但能够很好的理解怎么使用链表,以及对链表的指针类理解 代码如下 Node* merge_list_two_pointer(List& list1, List& list2) {Node* new_head1 list1.head;Node* new_head2 list2.head;Node* s…...
【SpringBoot Web框架实战教程】05 Spring Boot 使用 JdbcTemplate 操作数据库
不积跬步,无以至千里;不积小流,无以成江海。大家好,我是闲鹤,微信:xxh_1459,十多年开发、架构经验,先后在华为、迅雷服役过,也在高校从事教学3年;目前已创业了…...

Spark基于DPU的Native引擎算子卸载方案
1.背景介绍 Apache Spark(以下简称Spark)是一个开源的分布式计算框架,由UC Berkeley AMP Lab开发,可用于批处理、交互式查询(Spark SQL)、实时流处理(Spark Streaming)、机器学习&a…...
Mini2440 start.s 修改支持串口输出,方便调试 (四)
经常会遇到点板子的时候,板子没有任何反应!怎么知道板子有没有在正常启动,在uboot阶段 start.s 中加入串口打印信息是很有必要的! 输出串口信息 ***UART:mini-2440-uBoot*** ***UART:mini-2440-uBoot*** ***UART:mini-2440-uBoo…...

【教程】几种不同的RBF神经网络
本站原创文章,转载请说明来自《老饼讲解-机器学习》www.bbbdata.com 目录 一、经典RBF神经网络1.1.经典径向基神经网络是什么1.2.经典径向基神经网络-代码与示例 二、广义回归神经网络GRNN2.1.广义回归神经网络是什么2.2.广义回归神经网络是什么-代码与示例 三、概率…...

【Liunx-后端开发软件安装】Liunx安装FDFS并整合nginx
【Liunx-后端开发软件安装】Liunx安装nacos 文章中涉及的相关fdfs相关软件安装包请点击下载: https://download.csdn.net/download/weixin_49051190/89471122 一、简介 FastDFS是一个开源的轻量级分布式文件系统,它对文件进行管理,功能包括…...

【Java笔记】Flyway数据库管理工具的基本原理
文章目录 1. 工作流程2. 版本号校验算法3. 锁机制3.1 为什么数据库管理工具需要锁3.2 flyway的锁机制 Reference 最近实习做的几个项目都用到了Flyway来做数据库的版本管理,顺便了解了下基本原理,做个记录。 详细的使用就不写了,网上教程很多…...

国际数字影像产业园创业培训,全面提升创业能力!
国际数字影像产业园作为数字影像产业的创新高地,致力于提供全面的创业支持服务。其中,创业培训作为重要的组成部分,旨在通过系统的课程设置和专业的讲师团队,为创业者提供从基础到进阶的全方位指导,帮助他们在数字影像…...

pyqt5 制作视频剪辑软件,切割视频
该软件用于切割视频,手动选取视频片段的起始帧和结束帧并保存为json文件。gui界面如下:包含快进、快退、暂停等功能, 代码如下: # codingUTF-8 """ theme: pyqt5实现动作起始帧和结束帧的定位,将定位到…...
VUE----通过nvm管理node版本
使用 NVM(Node Version Manager)来管理和切换 Node.js 版本是一个很好的选择。以下是在 苹果电脑macos系统 上使用 NVM 安装和切换 Node.js 版本的步骤: 1. 安装 NVM 如果你还没有安装 NVM,可以按照以下步骤进行安装:…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...

边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...

CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...