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

2024-01-10 15:36
文章标签 每天 两道 第十一天

本文主要是介绍每天刷两道题——第十一天,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

这篇关于每天刷两道题——第十一天的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/591264

相关文章

每天认识几个maven依赖(ActiveMQ+activemq-jaxb+activesoap+activespace+adarwin)

八、ActiveMQ 1、是什么? ActiveMQ 是一个开源的消息中间件(Message Broker),由 Apache 软件基金会开发和维护。它实现了 Java 消息服务(Java Message Service, JMS)规范,并支持多种消息传递协议,包括 AMQP、MQTT 和 OpenWire 等。 2、有什么用? 可靠性:ActiveMQ 提供了消息持久性和事务支持,确保消

两道笔试题

“char a='\72'”是什么意思? 这么理解:\为转义字符,\072转义为一个八进制数072,也就是十进制数的58买一送一,将转义字符对照表也一并贴给你吧:转义字符 意义 ASCII码值(十进制) \a 响铃(BEL) 007 \b 退格(BS) 008 \f 换页(FF) 012 \n 换行(LF) 010 \r 回车(CR) 013 \t 水平制表(HT) 009 \v 垂直制表(VT

每天一道面试题(2):fail-safe 机制与 fail-fast 机制分别有什么作用?

当谈论Java集合的 fail-fast 和 fail-safe 机制时,涉及的是在集合被并发修改时的行为和处理方式。这些机制对保证程序的正确性和稳定性非常重要,尤其是在多线程环境中。 1. Fail-Fast 机制 定义: Fail-fast 机制的核心是在检测到集合在遍历过程中被修改时,立即抛出 ConcurrentModificationException 异常,从而中断迭代操作。这种

【销售预测 ARIMA模型】ARIMA模型预测每天的销售额

输入数据txt格式: 2017-05-01 100 2017-05-02 200 ……. python 实现arima: # encoding: utf-8"""function:时间序列预测ARIMA模型预测每天的销售额author:donglidate:2018-05-25"""# 导入库import numpy as np # numpy库from statsmode

每天一个数据分析题(五百二十七)- word2vec模型

Word2vec,是一群用来产生词向量的相关模型。这些模型为浅而双层的神经网络,用来训练以重新建构语言学之词文本。关于word2vec模型,下面说法不正确的是: A. 得到的词向量维度小,可以节省存储和计算资源 B. 考虑了全局语料库的信息 C. 无法解决多义词的问题 D. 可以表示词和词之间的关系 数据分析认证考试介绍:点击进入 数据分析考试大纲下载 题目来源于CDA模拟题库 点

今日早报 每日精选15条新闻简报 每天一分钟 知晓天下事 9月6日,星期五

每天一分钟,知晓天下事! 2024年9月6日 星期五 农历八月初四 1、 “摩羯”加强为17级超强台风,6日广东深圳、珠海、湛江等多地全市停课。 2、 两部门:事业单位不得自行制定面向特定人员的专项招聘、加分等倾斜政策。 3、 央行:降准还有一定空间;存贷款利率进一步下行面临一定约束。 4、 我国天问三号任务计划2028年前后实施两次发射任务,实现火星样品返回地球。 5、 山东、四川、吉

每天掌握一个软测高级技巧:接口自动化神器apin进阶操作

之前写了一篇关于接口自动化框架 apin 入门使用是文章,主要介绍了 apin 的安装以及用例编写的方法。 今天这篇文章来给大家聊聊,apin 中的一些高级使用技巧。比如依赖接口的变量提取和引用,用例断言,以及函数工具的使用。 变量提取和引用 变量提取和引用主要是为了解决接口之间的参数依赖问题。 使用场景:接口 A 的参数中需要使用接口 B 返回的某个数据,那么就要在请求 B 接口之后,提

今日早报 每日精选15条新闻简报 每天一分钟 知晓天下事 9月5日,星期四

每天一分钟,知晓天下事! 2024年9月5日 星期四 农历八月初三 1、 气象台发布台风红色预警:“摩羯”或为近十年影响海南最强台风,海口5日12时起在全市范围内分批启动“六停”措施。 2、 国家医保局:将人工耳蜗等高值医用耗材纳入采购范围。 3、 食用油散装运输强制性国标启动制订:要求专用容器+核查运输记录。 4、 包装不得超三层、不得使用红木等,中秋节前多地启动

10天计划:每天5小时睡眠

Day 1 - Day 2: 适应期 目标:适应减少睡眠时间的变化。 睡眠:00:00 - 05:00(5小时)早晨(5:00 - 7:00):轻度运动(瑜伽、拉伸、散步)、20分钟冥想。上午(7:00 - 12:00):专注高强度任务(需要逻辑思考或创作)。中午(12:00 - 13:00):午餐,午间20分钟小睡。下午(13:00 - 17:00):处理日常任务和会议,做较轻松的工作。晚上

每天分享一个FPGA开源代码(3)- I2C

​ I2C(Inter-Integrated Circuit)是一种两线式串行总线。   ​   一、主要特点 1. 简单性:只使用两根线,即串行数据线(SDA)和串行时钟线(SCL),减少了硬件连接的复杂性。 2. 多设备连接:可以连接多个具有 I2C 接口的设备到同一总线,每个设备都有唯一的地址,通过地址来区分和通信。 3. 双向通信:SDA 线允许数据在主设备和从设备之间双