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

力扣100题——子串

560.和为k的子数组

这道题目不是滑动窗口的类型,因为长度并不是固定的。(好的,我在说废话)

注意题目要求是子数组,且是连贯的。那这里的话,解法有很多,最简单的就是暴力解法,但在这里我想说的是前缀和加哈希表优化,嘿嘿,适当的参考了一下官方的解题办法。ok,来。

首先什么是前缀和,先看个列子:

有个数组:nums=[1,2,3,4,5,6],那么他的前缀和就是0,1,3,6,10,15,21。

当i=0的时候,前缀和是0,

当i=1的时候,前缀和是1,

当i=2的时候,前缀和是0+1+2=3,以此类推。

我们已经知道了前缀和的值和k的值,那想求的是题目要求的连续子数组和为k的数,那是不是只要把当前的前缀和-k就可以得到连续的子数组的和,我们之前是用一个数组来表示的,那如果说得到的那个值出现在了这个数组中,是不是就说明找到了,上代码:

class Solution {public int subarraySum(int[] nums, int k) {int count=0,pre=0;//定义一个map,来存放各个前缀和出现的次数HashMap<Integer,Integer> mp=new HashMap<>();//这个主要是用以考虑连续数组只有一个的情况,比如说例子2中的3mp.put(0,1);for(int i=0;i<nums.length;i++){pre+=nums[i];if(mp.containsKey(pre-k)){count+=mp.get(pre-k);}mp.put(pre,mp.getOrDefault(pre,0)+1);}return count;}
}

239、滑动窗口最大值

题解:这道题用了一个优先队列。在优先队列里面的元素是已经排列好的。要注意的是用C++和Python是不一样的。前者是默认从高到低对数组进行排列,而后者是从低到高,所以用python的时候需要注意要对其取负值。

解题思路:用优先队列,定义一个优先队列,然后将前面的k值放入队列中,将最大的那个元素存入数组中,接着利用for循环,从k值开始,将新元素放入队中,同时判断当前窗口中最大值是否在i-k中,如果不是则需要弹出

纠结点

1.就是用while循环弹出的是一系列吗?,存在的意义是什么。

while循环的目的在于弹出窗口中最大的元素,但要注意前提条件。如果此时窗口滑到了[-1,-1,-2],那前面所有大于这个窗口里面的最大值都要出队pop掉,看个例子吧,我放个代码,看看就懂了。

import heapq
class Solution:def maxSlidingWindow(nums, k):n = len(nums)# 注意 Python 默认的优先队列是小根堆q = [(-nums[i], i) for i in range(k)]#这里的作用是将其调整成为一个大根堆,q本身就发生了改变,并返回noneheapq.heapify(q)ans = [-q[0][0]]for i in range(k, n):heapq.heappush(q, (-nums[i], i))while q[0][1] <= i - k:# print("当前的k,i:",k,i)print("弹出的q值为:",q[0][0])#将q对列中弹出最小的元素heapq.heappop(q)# print("弹出之后的q值",q)ans.append(-q[0][0])print("q2的值为", q)return ans
nums=[1,0,-1,-3,5,3,6,7,9,10,-1,-1,-2,-3,3,2,3,1]
nums1=[1]
k=3
m=Solution.maxSlidingWindow(nums,k)
print(m)

2.python代码的误解

heapq.heappop(q),这串代码的意思是弹出q中最小的元素,所以print(q)是输出q这个队列里面的所有元素,而不只是队列中最大的元素

3、当窗口右移时,只需要判断最大值是否在滑动窗口中。所以说如果此时通过右移添加的元素是大于之前窗口中的最大值的,这种情况下此时while循环里面它的最大值就是当前元素,比较的下标也是当前元素的。所以就不要纠结为什么之前窗口最大的无法弹出了,因为它遇见了一个比它更大的,懂了吧。

下面的代码是我在pycharm编译器里面测试编写的,若要放在力扣上面的话记得改动一下。

代码:

import heapq
class Solution:def maxSlidingWindow(nums, k):n = len(nums)# 注意 Python 默认的优先队列是小根堆q = [(-nums[i], i) for i in range(k)]#这里的作用是将其调整成为一个大根堆,q本身就发生了改变,并返回noneheapq.heapify(q)ans = [-q[0][0]]for i in range(k, n):heapq.heappush(q, (-nums[i], i))while q[0][1] <= i - k:print("此时的i,k,q[0][1]分别为",i,k,q[0][1])print("弹出的q值为:",q[0][0])#将q对列中弹出最小的元素heapq.heappop(q)print("弹出之后的q值",q)ans.append(-q[0][0])print("q2的值为", q)return ans
nums=[1,0,-1,-3,5,3,6,7]
nums1=[1]
k=3
m=Solution.maxSlidingWindow(nums,k)
print(m)

76.最小覆盖子串

思路

这道题目的意思是要寻找s中覆盖t的连续最短子串,那我们可以用一个字典need来存储各个元素出现的次数,以及用needCnt来标识此时滑动窗口中的元素是否全部包括t中的元素,再用元组res来存储各个满足条件的窗口中的长度的下标。用i和j分别代表窗口的左边界和右边界,然后右移窗口,直到needCnt==0停止,这就代表着窗口中的元素已经全部包括t了,这里需要判断此时的元素出现的次数是否大于0,是的话长度得减1,减一和加一的标准是j++时,--,i++时,++。具体的大家看代码应该就能看懂了。加油!!!

代码:

class Solution:def minWindow(self, s: str, t: str) -> str:# 1.创建一个字典,用以存储各个字母出现的次数need=collections.defaultdict(int)# 循环遍历t数组,统计次数存入need中for c in t:need[c]+=1# 更新needCnt的值,此时就是t数组的长度,当其能匹配到S中相应的字符时,便减一直到为0needCnt=len(t)# 代表左边窗口i=0# 定义元组的大小,右边表示正无穷res=(0,float('inf'))# 循环遍历s数组for j,c in enumerate(s):#当s中的字符对应在字典中的值大于0时,needCnt--,因为只要是在右移的过程中,碰到的元素都是--的if need[c]>0:needCnt-=1need[c]-=1#当窗口中的元素的所有值都包含了t中的元素值之后,便开始移动左边窗口了if needCnt==0:while True:c=s[i]# 直到移动的元素是t中的,即need[c]==0,这里不考虑其他元素有没有可能为0的情况,因为如果为0,那就已经不在滑动窗口中了,目标元素在原始情况下是+1的,从此便区分开了if need[c]==0:breakneed[c]+=1i+=1#直到遇到t中元素的边界,这里就需要存储一下窗口大小,便于后续取出,之后便再次移动左边界,寻找遍历最短的包括t数组的连续数组if j-i<res[1]-res[0]:res=(i,j)need[s[i]]+=1needCnt+=1i+=1# 这里切片return '' if res[1]>len(s) else s[res[0]:res[1]+1]

相关文章:

力扣100题——子串

560.和为k的子数组 这道题目不是滑动窗口的类型&#xff0c;因为长度并不是固定的。&#xff08;好的&#xff0c;我在说废话&#xff09; 注意题目要求是子数组&#xff0c;且是连贯的。那这里的话&#xff0c;解法有很多&#xff0c;最简单的就是暴力解法&#xff0c;但在这…...

自然语言处理中的文本聚类:揭示模式和见解

一、介绍 在自然语言处理&#xff08;NLP&#xff09;领域&#xff0c;文本聚类是一种基本且通用的技术&#xff0c;在信息检索、推荐系统、内容组织和情感分析等各种应用中发挥着关键作用。文本聚类是将相似文档或文本片段分组为簇或类别的过程。这项技术使我们能够发现隐藏的…...

C/C++内存管理——“C++”

各位CSDN的uu们你们好呀&#xff0c;好久没有更新小雅兰的C专栏啦&#xff0c;下面&#xff0c;小雅兰继续开始更新C专栏的内容&#xff01;&#xff01;&#xff01;今天&#xff0c;小雅兰的内容是C和C的内存管理&#xff0c;下面&#xff0c;让我们进入C的世界吧&#xff01…...

jsp小知识

jsp小知识 1[单选题] 用户登录功能中&#xff0c;用到的数据库操作是&#xff08; &#xff09;。 正确答案: C 我的答案: C A. 增加 B. 删除 C. 查询 D. 修改 2[单选题] 下列说法错误的是&#xff08; &#xff09;。 正确答案: C 我的答案: C A. JDBC API包括一组支…...

Flutter:改变手机状态栏颜色,与appBar状态颜色抱持一致

前言 最近在搞app的开发&#xff0c;本来没怎么注意appBar与手机状态栏颜色的问题。但是朋友一说才注意到这两种的颜色是不一样的。 我的app 京东 qq音乐 这样一对比发现是有的丑啊&#xff0c;那么如何实现呢&#xff1f; 实现 怎么说呢&#xff0c;真不会。百度到的一些是…...

深入分析:一体化运维监控在金融行业的关键作用

金融行业&#xff0c;作为现代经济的核心支柱&#xff0c;对信息技术的依赖程度极高。在飞速发展的金融科技背景下&#xff0c;如何保障IT系统的稳定运行&#xff0c;成为了行业关注的焦点。一体化运维监控&#xff0c;通过实时监控、智能预警、快速定位及自动化恢复等功能&…...

物联网AI MicroPython学习之语法 network网络配置模块

学物联网&#xff0c;来万物简单IoT物联网&#xff01;&#xff01; network介绍 模块功能&#xff1a; 用于管理Wi-Fi和以太网的网络模块参考用法&#xff1a; import network import time nic network.WLAN(network.STA_IF) nic.active(True) if not nic.isconnected():…...

java根据前、中序遍历结果重新生成二叉树

1、首先写一个类表示二叉树 public class TreeNode {int num;TreeNode left;TreeNode right;public TreeNode(int num) {this.num num;}}2、根据前&#xff0c;中序遍历&#xff0c;在控制台我们可以得到两个结果pre 和 in&#xff1a; /*** 前序遍历* param node*/public st…...

利用检测结果实现半自动标注

1. 将目标检测结果保存为xml格式 #-----------------------------------------------------------------------------------# # 下面定义了xml里面的组成模块&#xff0c;无需改动。 #-----------------------------------------------------------------------------------…...

Android修行手册 - 万字梳理JNI开发正确技巧和错误缺陷

JNI 简介 JNI&#xff0c;Java Native Interface&#xff0c;是 native code 的编程接口。JNI 使 Java 代码程序可以与 native code 交互——在 Java 程序中调用 native code&#xff1b;在 native code 中嵌入 Java 虚拟机调用 Java 的代码。 它支持将 Java 代码与使用其他…...

C++学习 --类和对象之继承

目录 1&#xff0c; 继承的语法 1-1, 继承方式 1-1-1&#xff0c; 公共继承public 1-1-2&#xff0c; 私有继承private 1-1-3&#xff0c; 保护继承protected 2&#xff0c; 父类&#xff0c;子类同名属性处理 2-1&#xff0c; 成员变量同名 2-2&#xff0c; 成员函数同…...

Redis之缓存

文章目录 前言一、缓存使用缓存的原因 二、使用缓存实现思路提出问题 三、三大缓存问题缓存穿透缓存雪崩缓存击穿互斥锁实现逻辑过期时间实现 总结 前言 本篇文章即将探索的问题&#xff08;以黑马点评为辅助讲解&#xff0c;大家主要体会实现逻辑&#xff09; 使用redis缓存的…...

Redis6的IO多线程分析

性能测试 机器配置 C Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian CPU(s): 14 On-line CPU(s) list: 0-13 Mem: 62G性能 配置推荐 官方表示&#xff0c;当使用redis时有性能瓶…...

kali linux安装教程

安装 Kali Linux 非常简单&#xff0c;下面是基本的步骤&#xff1a; 首先下载 Kali Linux 的 ISO 镜像文件。你可以从官方网站 https://www.kali.org/downloads/ 下载。 确保你的计算机支持使用盘或者 USB 启动。你可以在计算机开机时按下 F12 或者其他类似的按键&#xff0c;…...

React进阶之路(四)-- React-router-v6、Mobx

文章目录 ReactRouter前置基本使用核心内置组件说明编程式导航路由传参嵌套路由默认二级路由404路由配置集中式路由配置 Mobx什么是Mobx环境配置基础使用observer函数*计算属性&#xff08;衍生状态&#xff09;异步数据处理模块化多组件数据共享Mobx和React职责划分 ReactRout…...

55基于matlab的1.高斯噪声2.瑞利噪声3.伽马噪声4.均匀分布噪声5.脉冲(椒盐)噪声

基于matlab的1.高斯噪声2.瑞利噪声3.伽马噪声4.均匀分布噪声5.脉冲&#xff08;椒盐&#xff09;噪声五组噪声模型&#xff0c;程序已调通&#xff0c;可直接运行。 55高斯噪声、瑞利噪声 (xiaohongshu.com)...

Codeforces Round 908 (Div. 2)视频详解

Educational Codeforces Round 157 &#xff08;A--D&#xff09;视频详解 视频链接A题代码B题代码C题代码D题代码 视频链接 Codeforces Round 908 (Div. 2)视频详解 A题代码 #include<bits/stdc.h> #define endl \n #define deb(x) cout << #x << "…...

电路综合-基于简化实频的SRFT集总参数切比雪夫低通滤波器设计

电路综合-基于简化实频的SRFT集总参数切比雪夫低通滤波器设计 6、电路综合-基于简化实频的SRFT微带线切比雪夫低通滤波器设计中介绍了使用微带线进行切比雪夫滤波器的设计方法&#xff0c;在此对集总参数的切比雪夫响应进行分析。 SRFT集总参数切比雪夫低通滤波器综合不再需要…...

Linux系统编程——实现cp指令(应用)

cp指令格式 cp [原文件] [目标文件] cp 1.c 2.c 功能是将原文件1.c复制后并改名成2.c(内容相同&#xff0c;实现拷贝) 这里需要引入main函数的参数解读&#xff1a; 我们在定义函数时许多都带有参数&#xff0c;输入参数后便可进行定义函数内的功能执行&#xff0c;而main…...

20231112_DNS详解

DNS是实现域名与IP地址的映射。 1.映射图2.DNS查找顺序图3.DNS分类和地址4.如何清除缓存 1.映射图 图片来源于http://egonlin.com/。林海峰老师课件 2.DNS查找顺序图 3.DNS分类和地址 4.如何清除缓存...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...