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,可以按照以下步骤进行安装:…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
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…...

从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
PostgreSQL——环境搭建
一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在࿰…...
适应性Java用于现代 API:REST、GraphQL 和事件驱动
在快速发展的软件开发领域,REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名,不断适应这些现代范式的需求。随着不断发展的生态系统,Java 在现代 API 方…...