leetcode hot100_part4_子串

2024/4/20—4/21

560.和为K的子数组

        前缀和+哈希表,做二叉树的时候也有这个套路。注意细节,遍历到当前前缀和的时候是先找结果个数还是先加入哈希?应该先找结果个数,不然的话,当前位置也算上了(因为是前缀和相减,当前位置算的话(当前 - 当前),子数组就不存在了)。注意先放入一个,处理边界,也就是子数组的长度为0(肯定不算)或者当前全长。

        那个枚举的方法,也就是遍历嘛,主要是看懂时间复杂度的解释。

2024/9/10

        关于为什么先统计count,在把当前前缀加入map;可以从下标意义的角度去考虑;遍历到的当前位置的前缀和pre[i],对应的数组[0, i];map中已经存在的前缀数组下标为[0,j]; 重点是j的范围是0~i-1;如果有符合题目条件的子数组,它的下标范围肯定是[j+1,i];

        如果先把当前前缀和放入map,j就可以取到i,结合上面的分析如果此时[0,j] j=i是一个满足条件的pre[i] - k,那么对应的子数组长度为0;不存在,这种情况对应的k=0;

        同理可以明白为什么要先put(0,1);

239.滑动窗口最大值

直接看官方解法了

优先队列

  升序降序,大小顶堆写法

     

9/10

这里再说一下优先队列比较器的两种写法和排序规则

方法一:Javabean类实现Comparable接口指定比较规则

  1. 实现Comparable接口,重写compareTo方法;注意理解,compareTo( ) 方法中的参数是已经存在的元素(就理解为数组中存在的吧),this是新插入的元素,返回值一般都是新的减去旧的,结果大于0,记忆为新的更大,放到后面(旧的右边),所以是升序;
  2. 结果是0的话,下面是是基于TreeSet的,所以不允许重复;优先队列的话看上面,好像是不交换;
public class Student implements Comparable<Student>{private String name;private int age;@Override//this:表示当前要添加的元素//o:表示已经在(某种数据结构,TreeSet等)存在的元素//返回值://负数:表示当前要添加的元素是小的,存左边//正数:表示当前要添加的元素是大的,存右边//0 :表示当前要添加的元素已经存在,舍弃public int compareTo(Student o) {//指定排序的规则//只看年龄,我想要按照年龄的升序进行排列return this.getAge() - o.getAge();}
}

 方法二:创建集合对象的时候,传递比较器Comparator指定规则

  1. 和上面的一样,第一个参数是新要插入的元素,第二个参数是已经存在的元素,新的减旧的,按照方法一理解。就是升序,排出来的是个升序数组,优先队列基于堆,拿的第一个元素,是最小的,所以这种方式是小顶堆;
  2. 下面是两种写法

    public static void main(String[] args) {/*需求:请自行选择比较器排序和自然排序两种方式;要求:存入四个字符串, “c”, “ab”, “df”, “qwer”按照长度排序,如果一样长则按照首字母排序采取第二种排序方式:比较器排序*///1.创建集合//o1:表示当前要添加的元素//o2:表示已经在红黑树存在的元素//返回值规则跟之前是一样的TreeSet<String> ts = new TreeSet<>((o1, o2)->{// 按照长度排序int i = o1.length() - o2.length();//如果一样长则按照首字母排序i = i == 0 ? o1.compareTo(o2) : i;return i;});}

思路

        总体的思路,不着急删除(不要想着窗口动一次删一次),因为我们要的是每个窗口的最大值:窗口每移动一次,就把新遍历到的元素加入优先队列,然后取到优先队列的队头元素(队列里所有元素当前的最大值)。

        关键的是,如果这个元素不在当前的滑动窗口范围内,删除,继续取队头元素,直到取到的元素在当前窗口的范围内,再把这个答案放到结果集合里。

 算法竞赛中的常用JAVA API:PriorityQueue(优先队列)_java priorityqueue api-CSDN博客

单调队列

. - 力扣(LeetCode)灵山

        本质上单调是自己代码维护的,所以就是普通队列附加上代码维护的单调性;单调队列和单调栈的处理方式很像;

        关键是维护队头到队尾是降序的特性,并不也无法要求每个元素都在队列中,因为单调的性质总会淘汰一些元素。

  • 为了维护单调特性
    • 初始化前k个时,每个新的元素x被添加到队尾时,都要删除掉所有在x之前且比x大的元素
    • 滑动窗口移动时,添加新元素的时候也执行上述相同的操作
    • 取每个滑动窗口的结果时,队头元素就是max,但是如果它不在滑动窗口的范围内,需要不断删除队头元素,直到队头元素在当前滑动窗口范围内
  • 可以直接在单调队列里存入下标,不用存数字+下标,单调队列是双端队列Deque实现,不是Queue

分块+预处理

        这个方法自己看题解吧,就先不实现了

76.最小覆盖子串

        遍历长串,把所有的字符存到hashmap,key为字符,value为字符出现的位置集合。遍历目标串,拿到目标串每个字符的位置集合。

        对于目标串中的重复元素,

4/29

        看到一个题解说这题很像: 438找到字符串中所有字母异位词

9/10

滑动窗口

本质上就是滑动窗口,只不过是窗口移动时的判断条件变复杂了;

. - 力扣(LeetCode)灵山的题解,搭配视频理解,官方用的hashmap怎么遍历,后面有时间再写吧,这里先用数组;

        滑动窗口就是暴力遍历的上位解法,同向双指针,(就像二分查找是顺序数组暴力查找的上位一样);定义先定义左右指针都指向index = 0;以右指针为基准,随着r++,总会到达满足条件的状态,此时再去l++,区间缩减,左指针向着右指针靠近;直到不满足条件,在这个缩减的过程里更新结果,因为需要的是最小长度的嘛,再去移动右指针;

        再去看官方题解对滑动窗口的描述就很好理解了;

伪代码如下:其实也很好理解的,时间复杂度为O(n);虽然有两个循环

int len...
int l =0;
//for循环中定义r
for(int r = 0; r < len; r++){//r每到一个位置需要执行的操作状态更新while(满足条件){更新结果;状态更新移动左指针,l++;}
}
return 结果 

        接下来就是结合具体的条件了;用数组存储当前遍历到的字符串cur(l,r指针包含的串)和子串t的每个字符的出现次数;

  • 进入for循环,在每次移动r时,更新cur串的字符出现次数
  • while循序的条件是,cur串是否能顾覆盖子串t,字符种类和数量两个方面
    • while中将结果串的左右指针暂时更新为l,r(如果长度更小)
    • 因为要移动左指针,所以要提前更新l++造成的状态影响,最后再l++;这个顺序还是好好思考一下。
  • 优化点:
    • while的条件判断时,需要我们对cur和t进行覆盖的判断,需要遍历记录两个串字符数目的数组(或map),左右指针更新时都需要判断;
    • 要对上述过程进行优化,我们定义一个变量less,对于子串 t 的每种字符cur串中满足的个数,即cur串中是否包含这个字符,以及数量是否足够;
    • less的长度应为 t 的字符种类,数量是否够还是借助之前的数组判断;
  • 优化具体到代码:
    • r++之后,状态更新不仅要更新cur的字符数量,还要更新less,如果更新到的字符,能够包含了 t 中的某个字符,less--;这里有个坑,比较cur和 t 某个字符数量时,要用==判定为满足,因为这个字符在cur中只可能增加了;连续两个相同字符满足条件时,>=的话less会多减()。
    • while的条件为less == 0
    • while里的状态更新时,先假设l++带来的影响(当前 l 对其指向字符数量的变化,这个字,失去这个字符后还能满足覆盖t z中这个字符的条件);再进行l++

 啰嗦了;

最后还有一点思考,之所以可以不断l++到不满足条件,是因为l位置一旦是不满足条件了,后面的l都不会再满足条件

        

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/424163.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

架构师备考的一些思考(四)

前言 对于数学&#xff0c;我们之前学的是对的&#xff0c;但不是真的&#xff0c;所以我们没有数学思维。 对于计算机&#xff0c;我们学校教的是对的&#xff0c;但不是真的&#xff0c;所以仅仅从学校学习知识的应届毕业生&#xff0c;不论985,211&#xff0c;本科&#xff…

中国初创公司数量下降了98%

近年来&#xff0c;中国风险投资市场的风云变幻&#xff0c;通过IT Juzi&#xff08;IT桔子&#xff09;等权威数据服务提供商的透镜&#xff0c;得以清晰展现。数据显示&#xff0c;自2018年的鼎盛时期——拥有51,302家初创公司以来&#xff0c;这一数字在短短五年内急剧下降至…

如何通过网络找到自己想要的LabVIEW知识?

学习LabVIEW或其他编程技术时&#xff0c;无法依赖某一篇文章解决所有问题。重要的是通过多种途径获取灵感&#xff0c;并学会归纳总结&#xff0c;从而逐渐形成系统性的理解。这种持续学习和总结的过程是技术提升的基础。通过网络找到所需的LabVIEW知识可以通过以下几个步骤进…

编写注册接口与登录认证

编写注册接口 在UserController添加方法 PostMapping("/login")public Result login(Pattern(regexp "^\\S{5,16}$") String username,Pattern(regexp "^\\S{5,16}$") String password){ // 根据用户名查询用户User loginUser userS…

第二期: 第二节 , 裸机编程 , gpio

1 首先就是 看原理图&#xff1a; 这里有两个 &#xff2c;&#xff25;&#xff24; 核心板的原理图。 可以看到 是这个脚。 &#xff12; 然后就是 查看数据手册。 从 数据手册可以看出 &#xff0c;一共有这么多的 gpio 组&#xff0c; 但是这些 组 是有复用的&#xf…

跨平台开发新视角:利用Android WebView实现Web内容的原生体验

在移动应用开发领域&#xff0c;跨平台解决方案一直是一个热门话题。开发者们不断寻求能够同时在iOS和Android平台上提供一致用户体验的方法。而Android的WebView组件&#xff0c;作为一个强大的工具&#xff0c;允许开发者在Android应用中嵌入Web内容&#xff0c;为用户提供接…

瑞芯微Android6 内核编译报错解决方案

1、报错内容如下图所示 错误内容&#xff1a; Kernel: arch/arm/boot/zImage is ready make: *** [kernel.img] Error 127 2、分析与解决方法 由于之前在ubuntu环境下编译没问题&#xff0c;现在是在centos环境下重新编译的时候报错&#xff0c;所以经过分析对比两个环境的…

根据第七次人口普查数据探索中国平均预期寿命

一&#xff1a;数据介绍 数据来源&#xff1a;预期寿命数据集 - Heywhale.com 该数据提供了中国各地区在第七次人口普查&#xff08;2020年&#xff09;中的平均预期寿命&#xff0c;包括男性和女性的预期寿命。该表具有93行和3列。以下是关于这个数据表的具体信息&#xff1…

FTP搜索引擎爬虫设计与实现

博主介绍&#xff1a;专注于Java .net php phython 小程序 等诸多技术领域和毕业项目实战、企业信息化系统建设&#xff0c;从业十五余年开发设计教学工作 ☆☆☆ 精彩专栏推荐订阅☆☆☆☆☆不然下次找不到哟 我的博客空间发布了1000毕设题目 方便大家学习使用 感兴趣的可以…

摩尔信使MThings逻辑控制实例——交通灯

摩尔信使MThings提供了强大的数据配置和逻辑控制功能&#xff0c;可为用户带来一种高效且直观的方式进行管理和控制交通灯系统。与传统的PLC&#xff08;可编程逻辑控制器&#xff09;相比&#xff0c;MThings的界面更加用户友好&#xff0c;使得即使是非专业的用户也能够轻松地…

BSN六周年:迈向下一代互联网

当前&#xff0c;分布式技术作为现代计算机科学和信息技术的重要组成部分&#xff0c;在云计算、区块链等技术的推动下&#xff0c;正以多样化的形式蓬勃发展。 ​而区块链作为一种特殊的分布式系统&#xff0c;近年来也在各个领域得到了广泛关注。通过在区块链上运行智能合约…

YoloV10 训练自己的数据集(推理,转化,C#部署)

目录 一、下载 三、开始训练 train.py detect.py export.py 超参数都在这个路径下 四、C#读取yolov10模型进行部署推理 如下程序是用来配置openvino 配置好引用后就可以生成dll了 再创建一个控件&#xff0c;作为显示 net framework 4.8版本的 再nuget工具箱里下载 …

快速搭建最简单的前端项目vue+View UI Plus

1 引言 ‌‌Vue是一套用于构建Web前端界面的渐进式JavaScript框架。‌‌它以其易学易用、性能出色、灵活多变而深受开发者喜爱&#xff0c;并且与其他前端框架&#xff08;如‌React和‌Angular&#xff09;相比&#xff0c;在国内市场上受到了广泛的认可和使用。点击进入官方…

十四、centos7 yum报错:cannot find a valid baseurl for repo:base/7/x86_64的解决方案

&#x1f33b;&#x1f33b;目录&#x1f33b;&#x1f33b; 一、 centos7 yum报错&#xff1a;cannot find a valid baseurl for repo:base/7/x86_64二、分析错误三、解决方案3.1 检查网络连接3.2 检查DNS设置3.3 检查YUM仓库配置3.3.1 使用官方CentOS镜像配置3.3.2 使用阿里云…

【ArcGISProSDK】初识

ArcGIS Pro SDK 提供四种主要的可扩展性模式&#xff1a;加载项、托管配置、插件数据源和 CoreHost 应用程序。 各模块文件对比 API 核心 核心程序集位于 {ArcGIS Pro 安装文件夹}\bin 中。 程序集描述ArcGIS.Core.dll 提供 CIM、地理数据库、几何图形和公共设施网络 API。 …

JFLASH添加支持PY32F002芯片的方法

嵌入式及电子工程师、爱好者必备工具 0.91寸OLED屏幕大小的音频频谱&#xff0c;炫酷&#xff01; 0.96寸OLED控制器SSD1306其他两种显示模式 CX32l003 点亮0.96寸OLED屏幕 0.96寸OLED屏幕控制器SSD1306详解 JLINK无法烧写程序&#xff0c;原因让人意外 Luat开发板的烧写 …

计算机毕业设计Python知识图谱美团美食推荐系统 美团餐厅推荐系统 美团推荐系统 美食价格预测 美团爬虫 美食数据分析 美食可视化大屏

《Python知识图谱美团美食推荐系统》开题报告 一、研究背景与意义 随着信息技术的飞速发展和互联网应用的普及&#xff0c;人们的消费习惯逐渐从线下转移到线上&#xff0c;外卖行业迎来了前所未有的发展机遇。美团作为国内领先的生活服务电子商务平台&#xff0c;拥有庞大的…

Kafka 基于SASL/SCRAM动态认证部署,kafka加账号密码登录部署

文章目录 前言下载 kafka安装启动zookeeper添加账号密码 启动kafka修改kafka配置文件增加jaas授权文件修改启动文件&#xff0c;启动kafka检查是否部署成功 offset explore 连接 前言 其实挺简单的几个配置文件&#xff0c;问大模型一直没说到点上&#xff0c;绕晕了。SASL/SC…

ardunio超声波测距实验

工作原理 模块有2个超声波换能器&#xff08;如图所示&#xff09;&#xff0c;一个发出声波&#xff0c;另一个接收物体反射回来的声波&#xff0c;这中间所经过的时间即声波传播的时间&#xff0c;再结合声速就能计算出&#xff1a; 距离 声速 * 时间 2 如何使用HC-SR04模块…

域控操作十七点五:域用户无管理员权限下安装IT打包的软件

1&#xff0c;需要软件Runasspcadmin三件套和winrar压缩软件 2&#xff0c;将需要打包的软件放进这个文件夹内&#xff0c;使用播放器举个例子 3&#xff0c;打开runasspcadmin.exe 按图片写就行了 文件夹现在是这样的然后全选右击&#xff0c;用WinRAR添加到压缩包 这个可以自…