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

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...

mac:大模型系列测试
0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何,是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试,是可以跑通文章里面的代码。训练速度也是很快的。 注意…...
Modbus RTU与Modbus TCP详解指南
目录 1. Modbus协议基础 1.1 什么是Modbus? 1.2 Modbus协议历史 1.3 Modbus协议族 1.4 Modbus通信模型 🎭 主从架构 🔄 请求响应模式 2. Modbus RTU详解 2.1 RTU是什么? 2.2 RTU物理层 🔌 连接方式 ⚡ 通信参数 2.3 RTU数据帧格式 📦 帧结构详解 🔍…...