HOT 100 | 【子串】76.最小覆盖子串、【普通数组】53.最大子数组和、【普通数组】56.合并区间
一、【子串】76.最小覆盖子串
1. 解题思路
定义两个哈希表分别用于 t 统计字符串 t 的字符个数,另一个sub_s用于统计字符串 t 在 s 的子串里面字符出现的频率。
为了降低时间复杂度,定义一个变量t_count用于统计 t 哈希表中元素的个数。哈希表sub_s是一边遍历字符串s一边构建的,所以定义一个变量have用于统计有几个元素满足了t哈希表的条件。当且仅当t_count == have,则表明子串sub_s是涵盖t中所有字符。
暴力枚举所有s的子串,然后在满足条件的子串中选出长度最小的返回即可,但是这种方法时间复杂度为O(n^2),我们可以选择时间复杂度更优的滑动窗口来解决(时间复杂度O(n))。
(1)从s开始进行遍历,如果该字符在t中存在,那么更新sub_s和have后,若没有满足条件t_count == have,那么则移动滑动窗口的右边界;如果该字符在t中不存在,那么窗口右边界直接继续向右移动。
(2)直到满足条件t_count == have,则记录当前窗口的长度length和起点start,然后将窗口的左边界向右移动后,更新sub_s和have。
(3)如果sub_s和have不满足t_count == have,则重复步骤(1)。
(4)如果再次遇到满足条件的子串,则判断其长度是否小于length,如果是则更新length和start。
2. 代码实现
class Solution:def minWindow(self, s:str, t:str)->str:ans_left = -1ans_right = len(s)cnt_s = Counter()cnt_t = Counter(t)left = 0for right, c in enumerate(s):cnt_s[c] += 1while cnt_s >= cnt_t:if right-left < ans_right-ans_left:ans_left, ans_right = left, right cnt_s[s[left]] -= 1left += 1return "" if ans_left < 0 else s[ans_left:ans_right+1]
二、【普通数组】53.最大子数组和
1. 解题思路
本题采用动态规划五部曲进行解答。
(1)定义dp数组:dp[i]表示的是以nums[i]结尾的最大连续子序列的和。
(2)递推公式:可以发现,连续子序列的和dp[i]分为两种状态可以得到,一是dp[i-1]+nums[i],也就是延续前面的子序列;另一种是nums[i],也就是从该元素开始的子序列。因此,得到递推公式:dp = max(dp[i-1]+nums[i], nums[i] )
(3)初始化:dp[0]必须初始化为数组的头元素,即dp[0] = nums[0],其余的元素可以初始化任意值,因为随着状态转移其真正的值会覆盖初始值。
(4)遍历顺序:正常的遍历顺序即可。
(5)打印:注意最后输出的不是dp[i],因为最大子数组和不一定是最后一个元素结尾的。
2. 代码实现
class Solution:def maxSubArray(self, nums: List[int])->int:dp = [0] * len(nums)dp[0] = nums[0]for i in range(1, len(nums)):dp[i] = max(dp[i-1]+nums[i], nums[i])return max(dp)
三、【普通数组】56.合并区间
1. 解题思路
本题采用贪心算法。
(1)为了方便对区间进行合并,需要对区间按照左边界或者右边界进行排序。
(2)判断区间是否发生重叠:当前区间的左边界是否小于等于上一个区间的右边界,如果是则说明这两个区间发生了重叠,那么需要合并区间;如果不是则说明没有发生重叠,那么定义一个新数组存放将当前区间。
(3)注意:在合并区间的过程中,是更新区间的右边界,但最新的右边界并不一定是当前区间的右边界,因为可能存在上一个区间右边界大于当前区间右边界的情况,所以在进行合并的时候,更新右边界应该是取当前区间右边界和上一个区间右边界的最大值。
2. 代码实现
class Solution:def merge(self, intervals:List[List[int]])->List[List[int]]:# 定义一个变量result用于存放结果集result = []# 判断给出的intervals是否为空if len(intervals) == 0:return result# 按照左边界对区间进行排序intervals.sort(key = lambda x: x[0])# 将第一个区间加入到结果集中,再进行更新即可result.append(intervals[0])# 遍历区间,从1开始是因为为了防止i-1异常for i in range(1, len(intervals)):# 判断区间是否重叠if result[-1][1]>=intervals[i][0]:result[-1][1] = max(result[-1][1], intervals[i][1])else:result.append(intervals[i])return result
相关文章:
HOT 100 | 【子串】76.最小覆盖子串、【普通数组】53.最大子数组和、【普通数组】56.合并区间
一、【子串】76.最小覆盖子串 1. 解题思路 定义两个哈希表分别用于 t 统计字符串 t 的字符个数,另一个sub_s用于统计字符串 t 在 s 的子串里面字符出现的频率。 为了降低时间复杂度,定义一个变量t_count用于统计 t 哈希表中元素的个数。哈希表sub_s是一…...
基于CNN的猫狗图像分类系统
一、系统概述 本系统是基于PyTorch框架构建的智能图像分类系统,专门针对CIFAR-10数据集中的猫(类别3)和狗(类别5)进行分类任务。系统采用卷积神经网络(CNN)作为核心算法,结合图形用…...
《时序数据库全球格局:国产与国外主流方案的对比分析》
引言 时序数据库(Time Series Database, TSDB)是专门用于存储、查询和分析时间序列数据的数据库系统,广泛应用于物联网(IoT)、金融、工业监控、智能运维等领域。近年来,随着大数据和物联网技术的发展&…...
力扣-2.两数相加
题目描述 给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。 请你将两个数相加,并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外,这两个数都…...
富乐德传感技术盘古信息 | 锚定“未来工厂”新坐标,开启传感器制造行业数字化转型新征程
在数字化浪潮下,制造业正经历深刻变革。 传感器作为智能制造的核心基础部件,正面临着质量精度要求升级、交付周期缩短、成本管控严苛等多重挑战。传统依赖人工纸质管理、设备数据孤岛化的生产模式,已成为制约高端传感器制造突破“高精度、高…...
RT-Thread 深入系列 Part 2:RT-Thread 内核核心机制深度剖析
摘要: 本文从线程管理、调度器原理、中断处理与上下文切换、IPC 同步机制、内存管理五大核心模块出发,深入剖析 RT-Thread 内核实现细节,并辅以源码解读、流程图、时序图与性能数据。 目录 线程管理与调度器原理 1.1 线程控制块(T…...
uni-app,小程序自定义导航栏实现与最佳实践
文章目录 前言为什么需要自定义导航栏?基本实现方案1. 关闭原生导航栏2. 自定义导航栏组件结构3. 获取状态栏高度4. 样式设置 内容区域适配跨平台适配要点iOS与Android差异处理 常见导航栏效果实现1. 透明导航栏2. 滚动渐变导航栏3. 自定义返回逻辑 解决常见问题1. …...
小程序消息订阅的整个实现流程
以下是微信小程序消息订阅的完整实现流程,分为 5个核心步骤 和 3个关键注意事项: 一、消息订阅完整流程 步骤1:配置订阅消息模板 登录微信公众平台进入「功能」→「订阅消息」选择公共模板或申请自定义模板,获取模板IDÿ…...
istio in action之Gateway流量入口与安全
入口网关,简单来说,就是如何让外部世界和我们精心构建的集群内部服务顺畅地对话。在网络安全领域,有一个词叫流量入口,英文叫Ingress。这指的是那些从我们自己网络之外,比如互联网,发往我们内部网络的流量。…...
LeetCode 1722. 执行交换操作后的最小汉明距离 题解
示例: 输入:source [1,2,3,4], target [2,1,4,5], allowedSwaps [[0,1],[2,3]] 输出:1 解释:source 可以按下述方式转换: - 交换下标 0 和 1 指向的元素:source [2,1,3,4] - 交换下标 2 和 3 指向的元…...
区块链详解
1. 引言 1.1 背景 在数字化时代,信息的存储、传输和验证面临诸多挑战,如数据篡改、信任缺失、中心化风险等。区块链技术应运而生,作为一种分布式账本技术,它通过去中心化、去信任化、不可篡改等特性,为解决这些问题提…...
申能集团笔试1
目录 注意 过程 注意 必须开启摄像头和麦克风 只能用网页编程,不能用本地环境 可以用Index进行测试 过程 我还以为是编程,没想到第一次是企业人际关系、自我评价的选择题,哈哈哈有点轻松,哦对他要求不能泄漏题目,…...
机器人手臂的坐标变换:一步步计算齐次矩阵过程 [特殊字符]
大家好!今天我们来学习如何计算机器人手臂的坐标变换。别担心,我会用最简单的方式解释这个过程,就像搭积木一样简单! 一、理解问题 我们有一个机器人手臂,由多个关节组成。每个关节都有自己的坐标系,我们需要计算从世界坐标系(W)到末端执行器(P₃)的完整变换。 二、已…...
神经元和神经网络定义
在深度学习中,神经元和神经网络是构成神经网络模型的基本元素。让我们从基础开始,逐步解释它们的含义和作用。 1️⃣ 神经元是什么? 神经元是神经网络中的基本计算单元,灵感来自于生物神经系统中的神经元。每个人的脑中有数以亿…...
Vue——Axios
一、Axios 是什么 Axios 是一个基于 promise 网络请求库,作用于 node.js 和浏览器中。 它是 isomorphic 的 ( 即同一套代 码可以运行在浏览器和 node.js 中 ) 。在服务端它使用原生 node.js http 模块 , 而在客户端 ( 浏览端 ) 则使 用 XMLHttpRequest…...
力扣:轮转数组
题目 给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。 例子 示例 1: 输入: nums [1,2,3,4,5,6,7], k 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5…...
TCP/IP协议的体系结构
文章目录 前言数据链路层网络层传输层应用层 前言 TCP/IP通信体系主要分为四个层次,从底至上分别为: 数据链路层 >网络层 > 传输层 >应用层 该体系的工作原理主要依靠封装与分用的使用完成对信息的传递与解析。 1. 所谓封装,就是上层…...
Vue3 中 ref 与 reactive 的区别及底层原理详解
一、核心区别 1. 数据类型与使用场景 • ref 可定义基本类型(字符串、数字、布尔值)和对象类型的响应式数据。对于对象类型,ref 内部会自动调用 reactive 将其转换为响应式对象。 语法特点:需通过 .value 访问或修改数据&#…...
MySQL 与 Elasticsearch 数据一致性方案
MySQL 与 Elasticsearch 数据一致性方案 前言一、同步双写(Synchronous Dual Write)🔄二、异步双写(Asynchronous Dual Write)📤三、定时同步(Scheduled Synchronization)ǵ…...
rust-candle学习笔记11-实现一个简单的自注意力
参考:about-pytorch 定义ScaledDotProductAttention结构体: use candle_core::{Result, Device, Tensor}; use candle_nn::{Linear, Module, linear_no_bias, VarMap, VarBuilder, ops};struct ScaledDotProductAttention {wq: Linear,wk: Linear,wv: …...
RabbitMQ-运维
文章目录 前言运维-集群介绍多机多节点单机多节点 多机多节点下载配置hosts⽂件配置Erlang Cookie启动节点构建集群查看集群状态 单机多节点安装启动两个节点再启动两个节点验证RabbitMQ启动成功搭建集群把rabbit2, rabbit3添加到集群 宕机演示仲裁队列介绍raft算法协议 raft基…...
101 alpha——8 学习
alpha (-1 * rank(((sum(open, 5) * sum(returns, 5)) - delay((sum(open, 5) * sum(returns, 5)),这里我们操作符都明白,现在来看金融意义 金融意义 里层是这个 (sum(open, 5) * sum(returns, 5)) - delay((sum(open, 5) * sum(returns, 5)), 10 这里是两个相减…...
YOLOv1模型架构、损失值、NMS极大值抑制
文章目录 前言一、YOLO系列v11、核心思想2、流程解析 二、损失函数1、位置误差2、置信度误差3、类别概率损失 三、NMS(非极大值抑制)总结YOLOv1的优缺点 前言 YOLOv1(You Only Look Once: Unified, Real-Time Object Detection)由…...
webpack代理天地图瓦片
1.安装 npm install http-proxy-middleware --save-dev2.webpack代理 const { createProxyMiddleware } require(http-proxy-middleware);module.exports {devServer: {port: 8080, // 改为你需要的端口https: false, // 如果你启用了 https,这里要对应before(a…...
RabbitMQ-高级特性1
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言消息确认机制介绍手动确认方法代码前言代码编写消息确认机制的演示自动确认automanual 持久化介绍交换机持久化队列持久化消息持久化 持久化代码持久化代码演示…...
Git_idea界面进行分支合并到主分支详细操作
最近闲着也是闲着,再来讲一下Git合并分支的操作吧。基本上咱们干开发的都会用到git吧,比如我们在大数据开发中,有一个主分支master,还有其他的诸多分支dev1.1.0,dev1.2.0......等。 以我近期开发的代码来讲,在开发分支开发完毕后&…...
MOS关断时波形下降沿振荡怎么解决
问题阐述: 一个直流电机控制电路,部分原理图如下: 波形如下: 原因分析: L:线路寄生电感(如PCB走线、MOS管引脚电感)。 C:MOS管输出电容(Coss)、…...
【Day 23】HarmonyOS开发实战:从AR应用到元宇宙交互
一、空间感知开发实战 1. 环境语义建模(NEXT增强) // 构建3D空间语义地图 spatialMapper.createMap({mode: SEMANTIC, // 语义分割模式objectTypes: [WALL, FLOOR, TABLE, DOOR ],onUpdate: (mesh) > {this.arScene.updateMesh(mesh) // 实时更新3D…...
ZYNQ笔记(十九):VDMA VGA 输出分辨率可调
版本:Vivado2020.2(Vitis) 任务:以 VDAM IP 为核心实现 VGA 彩条图像显示,同时支持输出分辨率可调。 (PS 端写入彩条数据到 DDR 通过 VDMA 读取出来输出给 VGA 进行显示) 目录 一、介绍 二、硬…...
江西同为科技有限公司受邀参展2025长江流域跨博会
江西同为科技有限公司是一家专注于电力保护设备研发与生产的高新技术企业,深耕于电气联接与保护领域,同时产品远销海外,在国内国际市场与客户保持长期稳定的合作。江西同为在跨境电子商务领域运营多年,有着深厚、丰富的行业经验&a…...
2025 SD省集总结
文章目录 DAY1时间安排题解T1. 花卉港湾T2. 礎石花冠T3.磷磷开花 DAY2时间安排题解T1. MEX 求和T2.最大异或和T3.前缀最值 DAY3时间安排题解T1.重建: 地下铁道T2.走过安眠地的花丛T3.昔在、今在、永在的题目 DAY4时间安排题解T1.崩坏世界的歌姬T2.色彩褪去之后T3.每个人的结局 …...
代码随想论图论part06冗余连接
图论part06 冗余连接 代码随想录 冗余边就是已经边已经在并查集里了,从图的角度来说构成了环(冗余连接2要用到这个概念) 代码其他部分为:并查集初始化,查根,判断是否在集合里,加入集合 冗余…...
SCADA|KIO程序导出变量错误处理办法
哈喽,你好啊,我是雷工! 最近在用KingSCADA3.52版本的软件做程序时,在导出变量进行批量操作时遇到问题,现将解决办法记录如下。 以下为解决过程。 01 问题描述 在导出KIO变量时,选择*.xls格式和*.xlsx时均会报错: 报如下错误: Unknown error 0x800A0E7A ADODB Connectio…...
AUTOSAR图解==>AUTOSAR_SWS_V2XBasicTransport
AUTOSAR V2X 基础传输协议 (V2XBasicTransport) 详解 AUTOSAR经典平台中V2X通信基础传输层的规范解析 目录 1. 引言与功能概述 1.1 架构概述1.2 功能概述 2. V2XBtp模块架构 2.1 AUTOSAR架构中的V2XBtp位置2.2 主要组件与职责 3. V2XBtp模块接口 3.1 接口结构3.2 数据类型和依…...
从代码学习深度学习 - 区域卷积神经网络(R-CNN)系列 PyTorch版
文章目录 前言R-CNNFast R-CNN兴趣区域汇聚层 (RoI Pooling)代码示例:兴趣区域汇聚层 (RoI Pooling) 的计算方法Faster R-CNNMask R-CNN双线性插值 (Bilinear Interpolation) 与兴趣区域对齐 (RoI Align)兴趣区域对齐层的输入输出全卷积网络 (FCN) 的作用掩码输出形状总结前言…...
RT-THREAD RTC组件中Alarm功能驱动完善
使用Rt-Thread的目的为了更快的搭载工程,使用Rt-Thread丰富的组件和第三方包资源,解耦硬件,在更换芯片时可以移植应用层代码。你是要RTT的目的什么呢? 文章项目背景 以STM32L475RCT6为例 RTC使用的为LSE外部低速32 .756k Hz 的…...
VSCode如何解决打开html页面中文乱码的问题
VSCode如何解决打开html页面中文乱码的问题 (1)打开扩展商店: (2)点击左侧菜单栏的扩展图标(或使用快捷键CtrlShiftX)。 (3)搜索并安装插件: …...
Java学习手册:单体架构到微服务演进
一、单体架构概述 单体架构是一种传统的软件架构风格,所有的功能模块都构建在一个统一的部署单元中。这种架构的优点是简单直接,便于开发、测试和部署。然而,随着应用规模的增长和需求的复杂化,单体架构的弊端逐渐显现࿰…...
android动态调试
在 Android 应用逆向工程中,动态调试 Smali 代码是分析应用运行时行为的重要手段。以下是详细的步骤和注意事项: 1. 准备工作 工具准备: Apktool:反编译 APK 生成 Smali 代码。Android Studio/IntelliJ IDEA:安装 smal…...
Google的A2A和MCP什么关系
作者:蛙哥 原文:https://zhuanlan.zhihu.com/p/1893738350252385035 Agent2Agent和MCP在功能上各有侧重,A2A专注于Agent之间的协作,MCP关注于Agent与外部数据源的集成。因此,MCP并不完全覆盖 A2A 的能力场景࿰…...
计算几何图形算法经典问题整理
几何算法经典问题 文章目录 几何算法经典问题一、几何基础问题1. 判断两条线段是否相交2. 判断点是否在多边形内3. 凸包计算4. 判断一个有序点集的方向(顺时针 or 逆时针)5. 求多边形面积和重心 二、 高阶图形问题6. 最小外接矩形(Minimum Bo…...
系分论文《论多云架构治理的分析和应用》
系统分析师论文范文系列 【摘要】 2022年3月,我所在公司承接了某金融机构“混合云资源管理与优化平台”的设计与实施项目。我作为系统分析师,主导了多云架构的规划与治理工作。该项目旨在构建一个兼容多家公有云及私有云资源的统一管理平台,解…...
(三)毛子整洁架构(Infrastructure层/DapperHelper/乐观锁)
文章目录 项目地址一、Infrastructure Layer1.1 创建Application层需要的服务1. Clock服务2. Email 服务3. 注册服务 1.2 数据库服务1. 表配置Configurations2. Respository实现3. 数据库链接Factory实现4. Dapper的DataOnly服务实现5. 所有数据库服务注册 1.3 基于RowVersion的…...
Femap许可使用数据分析
在当今竞争激烈的市场环境中,企业对资源使用效率和成本控制的关注日益增加。Femap作为一款业界领先的有限元分析软件,其许可使用数据分析功能为企业提供了深入洞察和智能决策的支持。本文将详细介绍Femap许可使用数据分析工具的特点、优势以及如何应用这…...
进入虚拟机单用户模式(Linux系统故障排查)
故障概述 虚拟机备份或者克隆后,无法通过编辑虚拟机IP,且忘记虚拟机密码,无法通过登录控制台修改虚拟机网络配置: 解决步骤 重启虚拟机并进入单用户模式修改网络配配置、设置密码等、大致两个步骤: 1、重启虚拟机 2、进…...
Python 数据分析与可视化:开启数据洞察之旅(5/10)
一、Python 数据分析与可视化简介 在当今数字化时代,数据就像一座蕴藏无限价值的宝藏,等待着我们去挖掘和探索。而 Python,作为数据科学领域的明星语言,凭借其丰富的库和强大的功能,成为了开启这座宝藏的关键钥匙&…...
7、三维机械设计、装配与运动仿真组件 - /设计与仿真组件/3d-mechanical-designer
76个工业组件库示例汇总 三维机械设计、装配与运动仿真通用组件 这是一个基于Three.js开发的三维机械设计、装配与运动仿真通用组件,可以实现工业机器人关节结构设计与运动仿真功能。 功能特点 直观的三维设计界面:提供基于WebGL的3D设计空间&#x…...
传统数据展示 vs 可视化:谁更打动人心?
数据,每天都在我们身边流动:从你手机里的健康步数,到企业财报中的营收增长,再到国家发布的经济指标。但问题是——你怎么“看”这些数据? 过去,我们习惯用表格、文字和报告来展示数据,这种方式…...
CSdiy java 07
1 || 运用逻辑运算符 在 Java 代码里,|| 是逻辑或(Logical OR)运算符,它的作用是对两个布尔表达式进行逻辑或运算。下面结合具体的代码片段来详细说明: 一、|| 的基本含义 在 Java 中,|| 运算符遵循以下…...
从零打造企业级Android木马:数据窃取与远程控制实战
简介 木马病毒已从简单的恶意软件演变为复杂的攻击工具,尤其在2025年企业级攻击中,木马病毒正成为黑客组织的主要武器之一。 本文将深入探讨如何制作具备数据窃取和远程控制功能的Android木马,从基础原理到企业级防御绕过技术,同时提供详细的代码实现,帮助开发者理解木马…...