统计定界子数组的数组
前言：看到这个题目的时候，只想着怎么暴力枚举右端点，结合线段树还是会超时，没找到很好的处理方法
超时代码
class Tree1:def __init__(self,n):self.t = [0]*(4*n)def update(self,o,l,r,index,va):if l==r:self.t[o] = vareturnmid = (l+r)//2if index<=mid:self.update(o*2,l,mid,index,va)else:self.update(o*2+1,mid+1,r,index,va)self.t[o] = max(self.t[o*2],self.t[o*2+1])def query(self,o,l,r,L,R):if L<=l and r <=R:return self.t[o]tmp = 0mid = (l+r)//2if mid>=L:tmp = max(tmp,self.query(o*2,l,mid,L,R))if R>mid:tmp = max(tmp,self.query(o*2+1,mid+1,r,L,R))return tmp
class Tree2:def __init__(self,n):self.t = [1000006]*(4*n)def update(self,o,l,r,index,va):if l==r:self.t[o] = vareturnmid = (l+r)//2if index<=mid:self.update(o*2,l,mid,index,va)else:self.update(o*2+1,mid+1,r,index,va)self.t[o] = min(self.t[o*2],self.t[o*2+1])def query(self,o,l,r,L,R):if L<=l and r <=R:return self.t[o]tmp = 1000006mid = (l+r)//2if mid>=L:tmp = min(tmp,self.query(o*2,l,mid,L,R))if R>mid:tmp = min(tmp,self.query(o*2+1,mid+1,r,L,R))return tmpclass Solution:def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:le = 0n = len(nums)big = Tree1(n)xiao = Tree2(n)le = 0ans = 0pre = 0for i,va in enumerate(nums):big.update(1,0,n-1,i,va)xiao.update(1,0,n-1,i,va)if va>maxK or va <minK:le = i+1pre = 0continueif pre!=0 and minK < va <maxK:ans += precontinuepre = 0for j in range(le,i+1):tmpxiao = xiao.query(1,0,n-1,j,i)tmpbig = big.query(1,0,n-1,j,i)# print("xiao",j,i,tmpxiao)# print("big",j,i,tmpbig)if tmpxiao==minK and tmpbig ==maxK:pre += 1else:breakans += prereturn ans
看了题解才发现是自己思维狭隘了，这个题目我每次遇到小于minK和大于maxK的值重新计数是对的，但是可以有更加优化的方法
class Solution:def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:ans = 0min_i = max_i = i0 = -1for i, x in enumerate(nums):if x == minK:min_i = i # 最近的 minK 位置if x == maxK:max_i = i # 最近的 maxK 位置if not minK <= x <= maxK:i0 = i # 子数组不能包含 nums[i0]ans += max(min(min_i, max_i) - i0, 0)return ans
相关文章：
统计定界子数组的数组
前言：看到这个题目的时候，只想着怎么暴力枚举右端点，结合线段树还是会超时，没找到很好的处理方法 超时代码 class Tree1:def __init__(self,n):self.t [0]*(4*n)def update(self,o,l,r,index,va):if lr:self.t[o] vareturnmid …...
JAVA---字符串
ctrlN 搜索界面（idea） API和API帮助文档 API ： 应用程序编程接口（换句话说，就是别人已经写好了，我们不需要再编写，直接使用即可） Java API ：就是JDK中提供的各种功能…...
import tree # pip install dm_tree ModuleNotFoundError: No module named ‘tree‘
在导入tree包时，在python库里找了很久，一直以为是tree这个包没下载好，有的推荐执行 pip install dm_tree这是deepmind开发一个处理处理嵌套数据结构的库。它在某种程度上tree 概括了仅支持扁平序列的内置map函数，并允许将函数应用…...
Java ThreadLocal与内存泄漏
当我们利用 ThreadLocal 来管理数据时，我们不可避免地会面临内存泄漏的风险。 原因在于 ThreadLocal 的工作方式。当我们在当前线程的 ThreadLocalMap 中存储一个值时，一旦这个值不再需要，释放它就变得至关重要。如果不这样做，那么…...
Rule.resource作用说明
1. 说明 作用 Rule.resource 用于定义哪些文件需要被当前规则处理。它是对传统 test、include、exclude 的更底层封装，支持更灵活的匹配方式。 与 test/include/exclude 的关系 test: /.js$/ 等价于resource: { test: /.js$/ } include: path.resolve(__dirname, ‘…...
【Docker项目实战】使用Docker部署Caddy+vaultwarden密码管理工具(详细教程）
【Docker项目实战】使用Docker部署vaultwarden密码管理工具 前言一、vaultwarden介绍1.1 vaultwarden简介1.2 主要特点二、本次实践规划2.1 本地环境规划2.2 本次实践介绍三、本地环境检查3.1 检查Docker服务状态3.2 检查Docker版本3.3 检查docker compose 版本四、拉取镜像五、…...
代码随想录算法训练营第五十九天 | 1.ford算法精讲 卡码网94.城市间货物运输
1.Bellman_ford 算法精讲 题目链接：94. 城市间货物运输 I 文章讲解：代码随想录 思路： 使用dijkstra，要求图中边的权值都为正数。 带负权值的单源最短路问题，轮到Bellman_ford 算法。Bellman_ford算法的核心思想是对…...
shell（1）
1.shell变量介绍 i.Linux Shell中的变量分为,系统变量和用户自定义变量. ii.系统变量:$HOME,$PWD, $SHELL,$USER 例echo $HOME iii.显示当前shell中的所有变量--set 2.shell变量的定义 基本语法 1.定义变量:变量名值 注意 号左右也不能有空格 2.撤销变量:unset 变量 3.声…...
KEPServerEX 6与西门子1500PLC进行OPC通讯
仿真效果与真实环境效果一至； 环境： 西门子软件：博图V20、S7-PLCSIM Advanced V5.0 OPC软件：KEPServerEX 6 创建S7-PLCSIM Advanced V5.0仿真环境 西门子1500plc组态 添加一个1500cpu，注意点击项目文件࿰…...
【概念】什么是 JWT Token？
—什么是 JWT Token？ JWT Token（JSON Web Token） 就是一张后端发给前端的小票，里面包含用户身份信息，用于做无状态认证（Stateless Authentication）。 每次前端访问后端接口，都拿着…...
【Castle-X机器人】一、模块安装与调试：机器人底盘
持续更新。。。。。。。。。。。。。。。 【ROS机器人】模块安装 一、Castle-X机器人底盘1.1 结构概述1.2 驱动执行结构1.3 环境传感器1.4 电气系统1.5 Castle-x机器人底盘测试激光雷达传感器测试及数据可视化超声波传感器实时数据获取防跌落传感器测试陀螺仪测试键盘控制测试…...
NSIS打包
以下是一篇详细的 NSIS 打包 EXE 的入门教程： NSIS 打包 EXE 入门教程 NSIS（Nullsoft Scriptable Install System）是一款开源的 Windows 安装包制作工具，支持脚本化定制安装流程。本教程将带你从零开始，创建一个简单的 EXE 安装程序。 1. 环境准备 1.1 下载 NSIS 访问官…...
62.不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？ 示例 …...
前端开发中shell的使用场景
Shell语言基础概念 Shell是用户与操作系统内核之间的接口，它接收用户输入的命令并解释执行。在Linux/Unix系统中，Shell是最常用的命令行界面。 基本语法和常用命令 变量定义和使用 # 定义变量 name"张三" age25# 使用变量 echo $name echo…...
基于javaweb的SSM投票管理系统设计与实现(源码+文档+部署讲解）
技术范围：SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容：免费功能设计、开题报告、任务书、中期检查PPT、系统功能实现、代码编写、论文编写和辅导、论文…...
)
uml类关系(实现、继承，聚合、组合，依赖、关联)
drawio和EA是架构设计时经常使用的画图工具。 drawio学习门槛低，使用灵活，但是功能仅仅限于画图。 EA学习门槛高，但是功能更加的丰富： ①在画图方面，EA严格满足UML标准，EA中的图和类是关联的，…...
力扣热题100题解（c++）—链表
160.相交链表 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。 图示两个链表在节点 c1 开始相交： 题目数据 保证 整个链式结构中不存在环。 注意，函数…...
MQ消息的不可靠性发生情况与解决方案
文章目录 问题：可能出现的情况： 解决流程与兜底方案第一个方面：确保生产者一定把消息发送到MQ1.生产者重试机制2.生产者确认机制 第二个方面：确保MQ不会将消息丢失数据持久化交换机持久化2.队列持久化3.消息持久化 LazyQueue控制台…...
线程池（五）：线程池使用场景问题
线程池（五）：线程池使用场景问题 线程池（五）：线程池使用场景问题1 线程池使用场景CountDownLatch、Future1.1 CountDownLatch原理示例代码 1.2 案例一（es数据批量导入）需求分析实现步…...
第十六届蓝桥杯网安初赛wp
解题列表 根据提示一步一步走，经过猜测，测试出app.py 经过仔细研读代码，找到密钥 编写python代码拿到flag key secret_key9828 flagd9d1c4d9e0d6c29e9aad71696565d99bc8d892a8979ec7a69b9a6868a095c8d89dac91d19ba9716f63b5 newbytearray(…...
)
8.学习笔记-Maven进阶(P82-P89)
（一）Maven-08-配置文件加载属性 通过maven可以做版本的集中管理，所以能不能通过maven进行配置文件（jdbc.properties）的集中管理。 （1）resource-》jdbc.properties 可以识别$符号 因为只能…...
基于 IPMI + Kickstart + Jenkins 的 OS 自动化安装
Author：Arsen Date：2025/04/26 目录 环境要求实现步骤自定义 ISO安装 ipmitool安装 NFS定义 ks.cfg安装 HTTP编写 Pipeline 功能验证 环境要求 目标服务器支持 IPMI / Redfish 远程管理（如 DELL iDRAC、HPE iLO、华为 iBMC）&…...
Ubuntu20.04部署Ragflow（Docker方式）
Ubuntu20.04部署Ragflow（Docker方式） Ubuntu20.04 RagflowRunning RagflowRunning Ollama 由于写这篇博客的时候电脑还没装输入法，所以先用半吊子英文顶着了…关于最后运行ollama的部分可以无视，因为我修改了端口所以才需要这么运…...
【C++语法】类和对象（2）
4.类和对象（2） 文章目录 4.类和对象（2）类的六个默认成员函数(1)构造函数：构造函数特点含有缺省参数的构造函数构造函数特点（续）注意事项构造函数补充 前面总结了有关对象概念，对比 C…...
JDK 17 与 Spring Cloud Gateway 新特性实践指南
一、环境要求与版本选择 1. JDK 17 的必要性 最低版本要求：Spring Boot 3.x 及更高版本（如 3.4）强制要求 JDK 17，以支持 Java 新特性（如密封类、模式匹配）和性能优化。JDK 17 核心特性： 密封类…...
深入了解及掌握AppScan不同测试策略的区别
引言 在当今数字化时代，应用程序安全至关重要。IBM AppScan作为一款强大的应用安全测试工具，提供了多种测试策略以适应不同的测试场景和需求。理解这些测试策略的区别，能够帮助安全测试人员更精准地开展测试工作，发现应用程序中潜藏的安全漏洞。本文将结合实际案例，深入剖…...
【Linux】web服务器的部署和优化
目录 nginx的安装与启用--/usr/share/nginx/html默认发布目录 nginx的主配置文件--/etc/nginx/nginx_conf nginx的端口 nginx默认发布文件--index.html nginx默认发布目录 nginx的访问控制 基于IP地址的访问控制 基于用户认证的访问控制 nginx的虚拟主机--/etc/nginx/…...
20250426在ubuntu20.04.2系统上解决问题mkfs.exfat command not found
20250426在ubuntu20.04.2系统上解决问题mkfs.exfat command not found 2025/4/26 21:11 缘起，使用NanoPi NEO开发板，编译FriendlyCore系统，打包eMMC固件的时候报错。 ./build.sh emmc-img -pack sd-card image, used to write frie…...
IDE使用技巧与插件推荐
一、高效使用技巧 1. 快捷键与操作优化 VS Code： 快速导航：Ctrl+P（Windows/Linux）或Cmd+P（macOS）打开文件搜索，输入文件名快速定位。多光标编辑：按住Alt（Windows/Linux）或Option（macOS）点击多个位置，同时编辑多处代码。Zen 模式：Ctrl+K Z（Windows/Linux）或Cmd…...
防火墙规则配置错误导致的网络问题排查
# 防火墙规则配置错误导致的网络问题排查指南 防火墙规则配置错误是网络连接问题的常见原因之一。以下是一套系统的排查步骤和方法： ## 1. 初步症状确认 - **常见表现**： - 特定服务无法访问 - 网络连接时断时续 - 部分IP地址或端口无法通信 …...
线性代数（一些别的应该关注的点）
一、矩阵 矩阵运算：线性变换 缩放、平移、旋转 无所不能的矩阵 - 三维图形变换_哔哩哔哩_bilibili...
思科路由器重分发（静态路由+OSPF动态路由+RIP动态路由）
路由器重分发（静态路由OSPF动态路由RIP动态路由） 开通端口并配置IP地址 OSPF路由 R1 Router>en Router#conf t Router(config)#int g0/0 Router(config-if)#no shut Router(config-if)#no shutdown Router(config-if)#ip add 192.168.10.254 255.…...
2.3java运算符
运算符 1. 算术运算符 算术运算符用于执行基本的数学运算，像加、减、乘、除等。 运算符描述示例加法int a 5 3; // a 的值为 8-减法int b 5 - 3; // b 的值为 2*乘法int c 5 * 3; // c 的值为 15/除法int d 6 / 3; // d 的值为 2%取模（取余&…...
元数据驱动的 AI 开发：从数据目录到模型训练自动化
元数据驱动的 AI 开发：从数据目录到模型训练自动化 一、引言 在人工智能技术蓬勃发展的当今时代，AI 开发已成为各行业实现创新的核心驱动力。然而，数据规模爆炸式增长、类型复杂多样、来源分散等问题，导致数据管理混乱、模型训练…...
从OpenAI收购实时数据引擎揭示AI数据库进化方向
第一章：一场技术并购背后的“数据战争” 1.1 OpenAI为何盯上Rockset？ 当OpenAI宣布收购Rockset时，数据库圈层炸开了锅。这家成立于2016年的公司，其创始人团队堪称“数据库界梦之队”：CTO Dhruba Borthakur曾主导Face…...
Linux0.11内存管理：相关代码
ch13_2 源码分析 boot/head.s 页表初始化： 目标：初始化分页机制，将线性地址空间映射到物理内存（前 16MB），为保护模式下的内存管理做准备。核心流程 分配页目录表和页表的物理内存空间（通过 .…...
ShaderToy学习笔记 03.多个形状和旋转
1. 正方形和旋转 1.1. 正方形 要绘制一个正方形，我们需要定义一个点到正方形边界的距离函数。对于中心在原点的正方形，其数学表达式为： 对于一个点 p(x,y) 到正方形边界的距离函数可以表示为: d max(|x|, |y|) - r 其中: |x| 和 |y| 分…...
Arduino+ESP01S烧录
这种办法不使用与ThonnyMircopython 前言 这里我们使用烧录器烧录，淘宝十几块钱一个的东西，ESP01S做一个WIFI继电器还是蛮有用的，就是烧录起来不太方便，传统的办法接线麻烦，需多次上电，也可能因为电源问题…...
什么是Lua模块？你会如何使用NGINX的Lua模块来定制请求处理流程？
大家好，我是锋哥。今天分享关于【什么是Lua模块？你会如何使用NGINX的Lua模块来定制请求处理流程？】面试题。希望对大家有帮助； 什么是Lua模块？你会如何使用NGINX的Lua模块来定制请求处理流程？ 1000道 互联…...
小白自学python第三天
学习python第三天 一、函数 1、函数介绍 函数就是组织好的，可重复使用的，用以实现特定功能的代码块。 现在我们现在需要统计多个字符串长度并且不考虑使用内置函数，你会怎么做？我们先用一种原始人办法看看吧： str…...
 C + Codeforces Round 1020 (Div. 3) DE)
【CF】Day44——Codeforces Round 908 (Div. 2) C + Codeforces Round 1020 (Div. 3) DE
C. Anonymous Informant 题目： 思路： 比这场的D难，虽然也不是很难 一个很容易想到的就是由当前状态推出初始状态，那么怎么推呢？ 一个性质就是如果对于某一个 x 它可以执行左移操作的话，那么它一定会到数组…...
深入理解HashMap：Hash冲突的解决机制
引言 HashMap 是 Java 集合框架中最常用的数据结构之一，它通过键值对的形式存储数据，并利用哈希算法实现高效的插入、删除和查询操作。然而，在实际使用中，由于哈希函数的有限性和哈希桶数量的限制，不可避免地会出现 哈…...
Datawhale AI春训营二期---使用AI实现老人的点餐效果（关于task2的相关思考）
文章目录 1.多次测试的结果2.分数是如何提高的3.关于上分点拨4.关于task2的收获 1.多次测试的结果 第一次和第二次的，都是使用的baseline: 第三次的： 2.分数是如何提高的 之前的几次都是通过这个baseline进行运行的，然后今天是了解了一下这…...
摩尔投票法详细介绍
原理 摩尔投票法（Boyer-Moore Voting Algorithm）是一种用于在存在多数元素的数组中，高效找出出现次数超过数组长度一半的元素的算法。其核心思想是通过元素抵消策略，逐步缩小候选范围，最终确定多数元素。 核心假设&a…...
DP之书架
现按一定顺序给出所有要放置于书架上的书，共有 n 本，第 i 本书有一个长度 hi。 书架有若干层，层与层之间的宽度不一定相等，但是一层的宽度不能小于其上所摆放的任何一本书的长度。同时，每层上的书的长度之和不能超过…...
Python Cookbook-6.11 缓存环的实现
任务 你想定义一个固定尺寸的缓存，当它被填满时，新加入的元素会覆盖第一个(最老的)元素。这种数据结构在存储日志和历史信息时非常有用。 解决方案 当缓存填满时，本节解决方案及时地修改了缓存对象，使其从未填满的缓存类变成了…...
计算机网络基本概念
层次名称主要功能第七层应用层直接面向用户，提供应用服务（如浏览网页、发邮件）第六层表示层处理数据格式、加密解密、压缩解压第五层会话层建立、管理、终止会话（连接）第四层传输层提供端到端的数据传输（如…...
Eigen线性代数求解器（分解类）
1. 核心分解类概览 Eigen 提供多种矩阵分解方法，适用于不同矩阵类型（稠密/稀疏、正定/非正定等）： 分解类适用矩阵类型分解形式典型应用场景PartialPivLU方阵（可逆）APLUAPLU通用线性方程组求解FullPivLU任…...
【Android】四大组件之Service
目录 一、什么是Service 二、启停 Service 三、绑定 Service 四、前台服务 五、远程服务扩展 六、服务保活 七、服务启动方法混用 你可以把Service想象成一个“后台默默打工的工人”。它没有UI界面，默默地在后台干活，比如播放音乐、下载文件、处理…...
VO包装类和实体类分别是什么？区别是什么？
VO包装类和实体类 1. 实体类（Entity Class）是什么？2. VO包装类（Value Object Class）是什么？3. VO包装类和实体类的区别4. 实际应用中的区别5. 举例5.1. 实体类（Entity Class）的定义与…...