当前位置: 首页 > news >正文

每天刷两道题——第十一天

1.1滑动窗口最大值

给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值

输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]

在这里插入图片描述

优先队列

优先队列具有队列的所有特性,包括队列的基本操作,只是在这基础上添加了内部的一个排序,它本质是一个堆实现的。
在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出,他和队列不同的就在于我们可以自定义其中数据的优先级,让优先级高的排在队列前面,优先出队。

python的heapq堆

堆是一个二叉树,有两种堆,最大堆与最小堆。 heapq库中的堆默认是最小堆
1.最小堆,树中各个父节点的值总是小于或等于任何一个子节点的值。
2.最大堆,树中各个父节点的值总是大于或等于任何一个子节点的值。

import heapq
q=heapq.heapify([3,6,4,1])  #将列表转化为堆
heapq.heappush(q,item)  #往堆q里面添加元素item
heapq.heappop(q) #删除q中顶部元素
heapq.heapreplace(q,100)  #删除顶部元素,加入新值100
#比较77和q中顶部元素,77如果大,删除并返回第一个元素,如果小,返回77,原堆不变
heapq.heappushpop(q,77)  
heapq.nlargest(n,q/[3,6,4,1])  #返回堆中最大的前n个
heapq.nsmallest(n,q/[3,6,4,1])  #返回堆中最小的前n个

代码
返回最大值,所以优先级采用负数

    def maxSlidingWindow(self,nums,k):n=len(nums)#heapq默认为小根堆,我们要找最大值,所以使用-nums[i]为优先级#-nums[i]为优先级  i为数据下标作为数据传入,前k个数据q=[(-nums[i],i) for i in range(k)] heapq.heapify(q)    #将列表转化为堆res=[-q[0][0]]  #q[0]=(-3,-1) -q[0][0]=3 第一个滑动窗口的最大值for i in range(k,n):heapq.heappush(q,(-nums[i],i))  #添加新元素#如果数据出现在滑动窗口的左侧将其从堆中删除while q[0][1]<=i-k:  #i是滑动窗口的右侧,i-k是滑动窗口的左侧heapq.heappop(q)res.append(-q[0][0])  #存储栈顶的元素return res

1.2最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。
注意:
对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量
如果 s 中存在这样的子串,我们保证它是唯一的答案

输入:s = “ADOBECODEBANC”, t = “ABC”
输出:“BANC”
解释:最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。

枚举

for i,item in enumerate([2,3,4]):print(i,item)
0 2
1 3
2 4for i,item in enumerate([2,3,4],start=10):print(i,item)
10 2
11 3
12 4

代码

    def minWindow(self, s: str, t: str) -> str:need = collections.defaultdict(int)for c in t:need[c] += 1  needCnt = len(t)i = 0  # 记录起始位置res = (0, float('inf'))  # 用两个元素,方便之后记录起终点# 三步骤:# 1. 增加右边界使滑窗包含tfor j, c in enumerate(s):if need[c] > 0:needCnt -= 1need[c] -= 1  # 这行放在外面不可以,看19行 need[c] == 0# 2. 收缩左边界直到无法再去掉元素   !注意,处理的是iif needCnt == 0: #此时已经包含了t所需的所有元素while True:c = s[i]if need[c] == 0:  # 表示再去掉就不行了(need>0)breakelse:need[c] += 1i += 1if j - i < res[1] - res[0]:  # 这里是否减一都可以,只要每次都是这样算的就行,反正最后也是输出子串而非长度res = (i, j)# 3. i多增加一个位置,准备开始下一次循环(注意这步是在 needCnt == 0里面进行的 )need[s[i]] += 1needCnt += 1  # 由于 移动前i这个位置 一定是所需的字母,因此NeedCnt才需要+1i += 1return "" if res[1] > len(s) else s[res[0]: res[1] + 1]

参考代码
参考博客
参考博客1
参考博客2

相关文章:

每天刷两道题——第十一天

1.1滑动窗口最大值 给你一个整数数组 nums&#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值 。 输入&#xff1a;nums [1,3,-1,-3,5,3,6,7], k 3 输出&…...

Git提交规范

一. 修改类型 每个类型值都表示了不同的含义&#xff0c;类型值必须是以下的其中一个&#xff1a; feat&#xff1a;提交新功能fix&#xff1a;修复了bugdocs&#xff1a;只修改了文档style&#xff1a;调整代码格式&#xff0c;未修改代码逻辑&#xff08;比如修改空格、格式…...

apache2的虚拟主机的配置

APACHE2的虚拟主机配置 本章中心概括&#xff1a; 虚拟web主机的初步认识&#xff0c;在redhat系列系统中如何配置&#xff0c;在Debian系列系统中如何配置。 什么是apache2虚拟主机&#xff1a; 简单点讲&#xff0c;就是在同一个物理机中配置多个虚拟主机&#xff0c;从而达…...

Provide/Inject 依赖注入(未完待续)

父组件传递给子组件数据&#xff0c;通过props&#xff0c;但是需要逐层传递 provide/Inject 的推出就是为了解决这个问题&#xff0c;它提供了一种组件之间共享此类值的方式,不必通过组件树每层级显示地传递props 目的是为了共享那些被 认为对于一个组件树而言是全局的数据 p…...

力扣173. 二叉搜索树迭代器

深度优先搜索 思路&#xff1a; 遍历二叉搜索树&#xff0c;左子树总比根节点小&#xff0c;右子树总比根节点大&#xff1b;先深度遍历左子树&#xff0c;然后返回其父节点&#xff0c;然后遍历其右子树节点&#xff1b;使用栈数据结构存储节点数据&#xff0c;借用其“后进先…...

电脑找不到d3dcompiler43.dll怎么修复,教你5个可靠的方法

d3dcompiler43.dll是Windows操作系统中的一个重要动态链接库文件&#xff0c;主要负责Direct3D编译器的相关功能。如果“d3dcompiler43.dll丢失”通常会导致游戏无法正常运行或者程序崩溃。为了解决这个问题&#xff0c;我整理了以下五个解决方法&#xff0c;希望能帮助到遇到相…...

5.3 Android BCC环境搭建(eadb版 上)

写在前面 eadb即eBPF Android Debug Bridge,它是基于adeb的重构。后者曾随aosp 10发布在platform/external目录下。 一,root权限 这里再HighLight下,当前整个专栏都是基于开发环境来展开的,也就是Android设备需要具有root权限。因此该专栏下每一篇博客都是默认了当前开发…...

【算法题】44. 通配符匹配

题目 给你一个输入字符串 (s) 和一个字符模式 (p) &#xff0c;请你实现一个支持 ? 和 * 匹配规则的通配符匹配&#xff1a; ? 可以匹配任何单个字符。 * 可以匹配任意字符序列&#xff08;包括空字符序列&#xff09;。 判定匹配成功的充要条件是&#xff1a;字符模式必须能…...

vscode配置与注意事项

中文设置 https://zhuanlan.zhihu.com/p/263036716 应用搜索输入“Chinese (Simplified) Language Pack for Visual Studio Code”并敲回车键 底部信息窗没有的话 首先使用快捷键ctrlshiftp&#xff0c;Mac用户使shiftcommandp&#xff0c;然后输入settings.json 将下面的选…...

设计模式篇章(3)——七种结构型模式

结构型设计模式主要思考的是如何将对象进行合理的布局来组成一个更大的功能体或者结构体&#xff0c;这个现在讲有点抽象&#xff0c;用大白话讲就是利用现有的对象进行组合或者配合&#xff0c;使得组合后的这个系统更加好。好是相对于不使用设计模式&#xff0c;按照自己的堆…...

Window端口占用处理

您好&#xff0c;我是码农飞哥&#xff08;wei158556&#xff09;&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f4aa;&#x1f3fb; 1. Python基础专栏&#xff0c;基础知识一网打尽&#xff0c;9.9元买不了吃亏&#xff0c;买不了上当。 Python从入门到精…...

算法实战(二)

基础算法编程 题目来源([PAT题目](https://pintia.cn/problem-sets/14/exam/problems/type/6))7-2 然后是几点7-3 逆序的三位数7-6 混合类型数据格式化输入 题目来源(PAT题目) 7-2 然后是几点 有时候人们用四位数字表示一个时间&#xff0c;比如 1106 表示 11 点零 6 分。现在…...

网工内推 | 上市公司网工,NP认证优先,最高15薪+项目奖金

01 广东轩辕网络科技股份有限公司 招聘岗位&#xff1a;网络工程师 职责描述&#xff1a; 1、主要负责教育行业园区网的有线及无线网络项目的实施、维护、巡检等工作&#xff1b; 2、协助windows/linux平台服务器OS的安装、部署、配置与维护&#xff1b; 3、协助服务器、存储、…...

【LLM 论文阅读】NEFTU N E: LLM微调的免费午餐

指令微调的局限性 指令微调对于训练llm的能力至关重要&#xff0c;而模型的有用性在很大程度上取决于我们从小指令数据集中获得最大信息的能力。在本文中&#xff0c;我们提出在微调正向传递的过程中&#xff0c;在训练数据的嵌入向量中添加随机噪声&#xff0c;论文实验显示这…...

JS新手入门笔记整理:对象

对象可以分为两种&#xff1a;一种是“自定义对象”&#xff0c;另外一种是“内置对象”。自定义对象&#xff0c;指的是需要我们自己定义的对象。内置对象&#xff0c;指的是不需要我们自己定义的&#xff08;即系统已经定义好的&#xff09;、可以直接使用的对象。在JavaScri…...

Python GIL 一文全知道!

GIL 作为 Python 开发者心中永远的痛&#xff0c;在最近即将到来的更新中&#xff0c;终于要彻底解决了&#xff0c;整个 Python 社群都沸腾了 什么是GIL&#xff1f; GIL是英文学名global interpreter lock的缩写&#xff0c;中文翻译成全局解释器锁。GIL需要解决的是线程竞…...

数据库级别的MD5加密(扩展)

首先&#xff0c;我们要知道什么是MD5? 1.主要是增强算法的复杂性和不可逆性 2.MD5不可逆&#xff0c;具体的值MD5是一样的 3.MD5破解网站的原理&#xff0c;背后有一个字典 代码案例&#xff1a; -- 加密 update testMD5 set pwdmd5(pwd) where id1; update testMD5 set…...

Docker安装Jenkins,配置Maven和Java

前言 这是一个java的springboot项目&#xff0c;使用maven构建 安装准备 需要将maven和jdk安装在服务器上&#xff0c;Jenkins需要用到&#xff0c;还有创建一个jenkins的目录&#xff0c;安装命令如下&#xff1a; docker run -d -uroot -p 9095:8080 -p 50000:50000 --n…...

游戏分组(100用例)C卷 (JavaPythonC语言C++Node.js)

部门准备举办一场王者荣耀表演赛,有10名游戏爱好者参与,分为两队,每队5人。 每位参与者都有一个评分,代表着他的游戏水平。为了表演赛尽可能精彩,我们需要把10名参赛者分为实力尽量相近的两队。一队的实力可以表示为这一队5名队员的评分总和。 现在给你10名参与者的游戏水…...

python函数装饰器保存信息

1 python函数装饰器保存信息 python函数装饰器&#xff0c;可以通过实例属性、全局变量、非局部变量和函数属性&#xff0c;来保存被装饰函数的状态信息。 1.1 统计调用并跟踪 描述 通过装饰器统计函数调用次数&#xff0c;并且用打印来跟踪调用记录。 此装饰器用类的__ca…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...