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

[LeetCode-Python版] 定长滑动窗口1(1456 / 643 / 1343 / 2090 / 2379)

思路

把问题拆解成三步:入-更新-出。

  • 入:下标为 i 的元素进入窗口,更新相关统计量。如果 i<k−1 则重复第一步。
  • 更新:更新答案。一般是更新最大值/最小值。
  • 出:下标为 i−(k-1) 的元素离开窗口,更新相关统计量。

题单链接

1456. 定长子串中元音的最大数目

题目

给你字符串 s 和整数 k ,请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

英文中的 元音字母 为(a, e, i, o, u)。

示例 1:
输入:s = “abciiidef”, k = 3
输出:3
解释:子字符串 “iii” 包含 3 个元音字母。

示例 2:
输入:s = “aeiou”, k = 2
输出:2
解释:任意长度为 2 的子字符串都包含 2 个元音字母。

示例 3:
输入:s = “leetcode”, k = 3
输出:2
解释:“lee”、“eet” 和 “ode” 都包含 2 个元音字母。

示例 4:
输入:s = “rhythms”, k = 4
输出:0
解释:字符串 s 中不含任何元音字母。

示例 5:
输入:s = “tryhard”, k = 4
输出:1

提示:

  • 1 <= s.length <= 1 0 5 10^5 105
  • s 由小写英文字母组成
  • 1 <= k <= s.length

题目链接

题解

class Solution:def maxVowels(self, s: str, k: int) -> int:res = vowel = 0for i, c in enumerate(s):if c in "aeiou":vowel += 1print(i,c,vowel)# 1. 入if i < k-1: # 先统计前 k−1 个字母的元音个数print("-")continue# 2. 更新res = max(res,vowel)# 3. 出if s[i-(k-1)] in "aeiou":vowel -=1return res

643. 子数组最大平均数 I

题目

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k ,请你找出平均数最大且 长度为 k 的连续子数组,并输出该最大平均数。

任何误差小于 10-5 的答案都将被视为正确答案。

示例 1:
输入:nums = [1,12,-5,-6,50,3], k = 4
输出:12.75
解释:最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

示例 2:
输入:nums = [5], k = 1
输出:5.00000

提示:

  • n == nums.length
  • 1 <= k <= n <= 1 0 5 10^5 105
  • − 1 0 4 -10^4 104 <= nums[i] <= 1 0 4 10^4 104

题目链接

题解

class Solution:def findMaxAverage(self, nums: List[int], k: int) -> float:res = float("-inf") #为什么-10**4不行sum_n = 0for i,num in enumerate(nums):#1.入sum_n += numif i < k-1:continue #2.更新res = max(res,sum_n)#3.出 sum_n -= nums[i-(k-1)]return res/k

1343. 大小为 K 且平均值大于等于阈值的子数组数目

题目

给你一个整数数组 arr 和两个整数 k 和 threshold 。

请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。

示例 1:
输入:arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
输出:3
解释:子数组 [2,5,5],[5,5,5] 和 [5,5,8] 的平均值分别为 4,5 和 6 。其他长度为 3 的子数组的平均值都小于 4 (threshold 的值)

示例 2:
输入:arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
输出:6
解释:前 6 个长度为 3 的子数组平均值都大于 5 。注意平均值不是整数。

提示:

  • 1 <= arr.length <= 1 0 5 10^5 105
  • 1 <= arr[i] <= 1 0 4 10^4 104
  • 1 <= k <= arr.length
  • 0 <= threshold <= 1 0 4 10^4 104

题目链接

题解

class Solution:def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:res = 0sum_n = 0for i,num in enumerate(arr):sum_n += num# 入if i < k-1:continue# 更新   if sum_n/k >= threshold:res += 1# 出   sum_n -=arr[i-(k-1)]return res

2090. 半径为 k 的子数组平均值

题目

给你一个下标从 0 开始的数组 nums ,数组中有 n 个整数,另给你一个整数 k 。

半径为 k 的子数组平均值 是指:nums 中一个以下标 i 为 中心 且 半径 为 k 的子数组中所有元素的平均值,即下标在 i - k 和 i + k 范围(含 i - k 和 i + k)内所有元素的平均值。如果在下标 i 前或后不足 k 个元素,那么 半径为 k 的子数组平均值 是 -1 。

构建并返回一个长度为 n 的数组 avgs ,其中 avgs[i] 是以下标 i 为中心的子数组的 半径为 k 的子数组平均值 。

x 个元素的 平均值 是 x 个元素相加之和除以 x ,此时使用截断式 整数除法 ,即需要去掉结果的小数部分。

例如,四个元素 2、3、1 和 5 的平均值是 (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75,截断后得到 2 。

示例 1:
在这里插入图片描述

输入:nums = [7,4,3,9,1,8,5,2,6], k = 3
输出:[-1,-1,-1,5,4,4,-1,-1,-1]
解释:

  • avg[0]、avg[1] 和 avg[2] 是 -1 ,因为在这几个下标前的元素数量都不足 k 个。
  • 中心为下标 3 且半径为 3 的子数组的元素总和是:7 + 4 + 3 + 9 + 1 + 8 + 5 = 37 。
    使用截断式 整数除法,avg[3] = 37 / 7 = 5 。
  • 中心为下标 4 的子数组,avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4 。
  • 中心为下标 5 的子数组,avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4 。
  • avg[6]、avg[7] 和 avg[8] 是 -1 ,因为在这几个下标后的元素数量都不足 k 个。

示例 2:
输入:nums = [100000], k = 0
输出:[100000]
解释:

  • 中心为下标 0 且半径 0 的子数组的元素总和是:100000 。
    avg[0] = 100000 / 1 = 100000 。

示例 3:
输入:nums = [8], k = 100000
输出:[-1]
解释:

  • avg[0] 是 -1 ,因为在下标 0 前后的元素数量均不足 k 。

提示:

  • n == nums.length
  • 1 <= n <= 105
  • 0 <= nums[i], k <= 105

题目链接

题解

思路如下图所示:
在这里插入图片描述

class Solution:def getAverages(self, nums: List[int], k: int) -> List[int]:if k==0: return numsres = [-1]*len(nums)sum_n = 0for i, num in enumerate(nums):sum_n+=numif i< 2*k:continueres[i-k] = sum_n//(2*k+1)sum_n -= nums[i-2*k]return res

2379. 得到 K 个黑块的最少涂色次数

题目

给你一个长度为 n 下标从 0 开始的字符串 blocks ,blocks[i] 要么是 ‘W’ 要么是 ‘B’ ,表示第 i 块的颜色。字符 ‘W’ 和 ‘B’ 分别表示白色和黑色。

给你一个整数 k ,表示想要 连续 黑色块的数目。

每一次操作中,你可以选择一个白色块将它 涂成 黑色块。

请你返回至少出现 一次 连续 k 个黑色块的 最少 操作次数。

示例 1:
输入:blocks = “WBBWWBBWBW”, k = 7
输出:3
解释:
一种得到 7 个连续黑色块的方法是把第 0 ,3 和 4 个块涂成黑色。
得到 blocks = “BBBBBBBWBW” 。
可以证明无法用少于 3 次操作得到 7 个连续的黑块。
所以我们返回 3 。

示例 2:
输入:blocks = “WBWBBBW”, k = 2
输出:0
解释:
不需要任何操作,因为已经有 2 个连续的黑块。
所以我们返回 0 。

提示:

  • n == blocks.length
  • 1 <= n <= 100
  • blocks[i] 要么是 ‘W’ ,要么是 ‘B’ 。
  • 1 <= k <= n

题目链接

题解

出现一次连续 k 个黑色块的最少操作次数问题可以转化成求连续 k 个块中白色块最少的个数

class Solution:def minimumRecolors(self, blocks: str, k: int) -> int:res = float("inf")w_num = 0for i, block in enumerate(blocks):if block == 'W':w_num +=1if i<k-1:continueres = min(res, w_num)if blocks[i-(k-1)] == 'W':w_num -=1return res

Q&A

  1. 子数组最大平均数 I题目中为什么res = float("-inf"),而-10**4不行?

    res = float("-inf") 表示将 res 初始化为一个非常小的负数,其目的是确保在后续的比较中,任何子数组的平均数都会大于这个初始值,因为子数组的平均数不可能是负无穷大。而 -10**4 这样的值虽然在大多数情况下也可以作为初始值,但是它存在问题:

    • 范围限制:题目中提到 − 1 0 4 -10^4 104 <= nums[i] <= 1 0 4 10^4 104,这意味着数组中的元素值是有限制的。如果有 k 个元素都是 − 1 0 4 -10^4 104,那么它们的和就是 − 1 0 4 ∗ k -10^4 * k 104k,此时res大于sum_n,导致结果错误。
    • 精度问题:浮点数在计算机中是有精度限制的。使用一个非常大的负数作为初始值可能会导致精度损失,尤其是在进行减法和除法操作时。

    因此,使用 float(“-inf”) 作为初始值是一个更安全、更稳定的做法,它可以确保在所有情况下都能正确地找到最大平均数,而不会因为数值范围或者精度问题导致错误的结果。

相关文章:

[LeetCode-Python版] 定长滑动窗口1(1456 / 643 / 1343 / 2090 / 2379)

思路 把问题拆解成三步&#xff1a;入-更新-出。 入&#xff1a;下标为 i 的元素进入窗口&#xff0c;更新相关统计量。如果 i<k−1 则重复第一步。更新&#xff1a;更新答案。一般是更新最大值/最小值。出&#xff1a;下标为 i−(k-1) 的元素离开窗口&#xff0c;更新相关…...

imx6ull qt多页面控制系统(正点原子imx系列驱动开发)

开题答辩完了也考完了四六级&#xff0c;赶紧来更新一下一个月前留下的坑吧 QAQ首先&#xff0c;因为毕业设计需要用到这些知识所以就从网络上找了一个智能车机系统&#xff0c;借鉴了一下大佬的项目思路&#xff0c;缝缝补补一个月终于完成了这一内容。 在这里先感谢从两位大佬…...

OCR:文字识别

使用场景: 远程身份认证 自动识别录入用户身份/企业资质信息&#xff0c;应用于金融、政务、保险、电商、直播等场景&#xff0c;对用户、商家、主播进行实名身份认证&#xff0c;有效降低用户输入成本&#xff0c;控制业务风险 文档电子化 识别提取各类办公文档、合同文件、企…...

SQL Server通过存储过程实现自定义邮件格式并定时发送

在 SQL Server 中,可以通过存储过程实现自定义邮件格式并定时发送。这通常涉及以下几个步骤: 1. 配置 Database Mail:首先需要配置 SQL Server 的 Database Mail 功能。 2. 创建存储过程:编写存储过程来生成自定义邮件格式并发送邮件。 3. 设置 SQL Server 代理作…...

【进阶编程】MVC和MVVM实现前后端分离的实现

在 WPF 开发中&#xff0c;通常使用 MVVM&#xff08;Model-View-ViewModel&#xff09;架构来分离视图和业务逻辑&#xff0c;但在某些情况下&#xff0c;你可能希望将 MVC&#xff08;Model-View-Controller&#xff09;模式与 MVVM 结合使用。这种结合有时是为了兼顾不同的架…...

HT81297 18W内置升压单声道D类音频功放

1、特征 扩频技术 输出功率 18W(VBAT3.7V, RL4Ω, THDN10%, fN 1kHz) 16W(VBAT3.7V,RL-4Ω,THDN1%,fN1kHz) 8W(VBAT3.3V,RL-8Ω,THDN1%, fN1kHz) VBAr供电范围:3.0V至12V 高效H类升压功能 -自适应功放功率的升压轨&#xff0c;延长电池播放时间 (HT81297A) -可调节最大限流值&…...

linux ipmitool配置机器的BMC(服务器管理后台)

前置&#xff1a;mgnt口和网卡1连接入内网&#xff0c;并分配静态ip 1. 安装 ipmitool Debian/Ubuntu: sudo apt-get update sudo apt-get install ipmitool CentOS/RHEL: sudo yum install ipmitool2. 配置 BMC 的 IP 地址 #打印当前ipmi 地址配置信息。 ipmitool lan p…...

【项目实战】location.href 实现文件下载

应用场景 最近在项目中看到一种新的文件下载方式,原理是将[后台地址接口地址请求参数]拼接成一个url,直接将下载任务丢给浏览器去执行.但是在需要校验token的项目中,需要后台单独给这个接口放开token校验 location.href 相关内容 window.location.protocol: 返回当前 URL 的…...

【Threejs】从零开始(十)--加载gltf模型和压缩后的模型

一.加载普通的gltf模型 glTF&#xff08;gl传输格式&#xff09;是一种开放格式的规范 &#xff08;open format specification&#xff09;&#xff0c; 用于更高效地传输、加载3D内容。该类文件以JSON&#xff08;.gltf&#xff09;格式或二进制&#xff08;.glb&#xff09;…...

国标GB28181平台EasyGBS在安防视频监控中的信号传输(电源/视频/音频)特性及差异

在现代安防视频监控系统中&#xff0c;国标GB28181协议作为公共安全视频监控联网系统的国家标准&#xff0c;该协议不仅规范了视频监控系统的信息传输、交换和控制技术要求&#xff0c;还为不同厂商设备之间的互联互通提供了统一的框架。EasyGBS平台基于GB28181协议&#xff0c…...

Day9 神经网络的偏导数基础

多变量函数与神经网络 在神经网络中&#xff0c;我们经常遇到多变量函数。这些函数通常描述了网络的输入、权重、偏置与输出之间的关系。例如&#xff0c;一个简单的神经元输出可以表示为&#xff1a; z f ( w 1 x 1 w 2 x 2 … w n x n b ) z f(w_1x_1 w_2x_2 \ldots…...

day4:tomcat—maven-jdk

一&#xff0c;java项目部署过程 编译&#xff1a;使用javac命令将.java源文件编译成.class宇节码文件打包&#xff1a;使用工具如maven或Gradle将项目的依赖、资源和编译后的字节码打包成一个分发格式&#xff0c;如.jar文件&#xff0c;或者.war文件(用于web应用&#xff09…...

apache-tomcat-6.0.44.exe Win10

apache-tomcat-6.0.44.exe Win10...

Redis(2)常用命令

安装Redis 现在我们安装Redis 5&#xff0c;Redis安装在Linux上面安装&#xff0c;如果想在本机上面安装多个Redis的话&#xff0c;就要使用Docker。 在Ubuntu上面安装&#xff1a; 切换到root用户使用apt命令搜索相关的软件包&#xff08;apt search redis&#xff09;apt …...

【原生js案例】ajax的简易封装实现后端数据交互

ajax是前端与后端数据库进行交互的最基础的工具&#xff0c;第三方的工具库比如jquery,axios都有对ajax进行第二次的封装&#xff0c;fecth是浏览器原生自带的功能&#xff0c;但是它与ajax还是有区别的&#xff0c;总结如下&#xff1a; ajax与fetch对比 实现效果 代码实现 …...

安卓环境配置及打开新项目教程,2024年12月20日最新版

1.去官网下载最新的Android Studio&#xff0c;网址&#xff1a;https://developer.android.com/studio?hlzh-cn 2.下载加速器&#xff0c;注册账号&#xff0c;开启加速器。网址&#xff1a;放在文末。 3.下载安卓代码&#xff0c;项目的路径上不能有中文&#xff0c;特别是…...

Docker 安装 禅道-21.2版本-外部数据库模式

Docker 安装系列 1、拉取最新版本&#xff08;zentao 21.2&#xff09; [rootTseng ~]# docker pull hub.zentao.net/app/zentao Using default tag: latest latest: Pulling from app/zentao 55ab1b300d4b: Pull complete 6b5749e5ef1d: Pull complete bdccb03403c1: Pul…...

写SQL太麻烦?免费搭建 Text2SQL 应用,智能写 SQL | OceanBase AI 实践

自OceanBase 4.3.3版本推出以来&#xff0c;向量检索的能力受到了很多客户的关注&#xff0c;也纷纷表达希望OB能拓展更多 多模数据库大模型 的AI应用实践。 在上篇文章 &#x1f449; OceanBase LLM&#xff0c;免费构建你的专属 AI 助手 &#xff0c;我们介绍了如何去搭建一…...

数据分析实战—鸢尾花数据分类

1.实战内容 (1) 加载鸢尾花数据集(iris.txt)并存到iris_df中,使用seaborn.lmplot寻找class&#xff08;种类&#xff09;项中的异常值&#xff0c;其他异常值也同时处理 。 import pandas as pd from sklearn.datasets import load_iris pd.set_option(display.max_columns, N…...

【专题】2024抖音电商母婴行业分析报告汇总PDF洞察(附原数据表)

原文链接&#xff1a;https://tecdat.cn/?p38651 在数字化浪潮的席卷下&#xff0c;抖音电商母婴行业正经历着深刻变革。当下&#xff0c;年轻一代父母崛起&#xff0c;特别是 24 至 30 岁以及 18 至 23 岁的群体成为抖音母婴行业兴趣人群的主力军。他们带来全新育儿理念&…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...