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

leetcode分类刷题:滑动窗口(二、重复元素类型)

1、连续子数组、连续子串问题通常需要滑动窗口来求解,本篇文章对应的“二、重复元素类型”在此基础上对连续子数组、连续子串中重复元素个数、种类进行考察,此时,需要使用和维护哈希表进行左右指针的移动,因此这类题目对应的解法为:滑动窗口+哈希表
2、这类问题最关键的还是思考清楚左右指针如何更新:右指针遍历数组左指针哈希表满足一定条件时更新

904. 水果成篮

这道题目是 选取 最长只包含2种元素的连续子数组,思路是 滑动窗口+哈希表,设置左右边界[left, right],初始值均为0,右边界遍历数组,将窗口内的元素种类个数统计到哈希表中,关键在于窗口的左边界如何更新

from typing import List
import collections'''
904. 水果成篮
题目描述:你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示,其中 fruits[i] 是第 i 棵树上的水果 种类 。
示例 1:输入:fruits = [1,2,3,2,2]输出:4解释:可以采摘 [2,3,2,2] 这四棵树。
题眼:选取 最长只包含2种元素的连续子数组
思路:滑动窗口+哈希表,设置左右边界[left, right],初始值均为0,右边界遍历数组,将窗口内的元素种类个数统计到哈希表中,关键在于窗口的左边界如何更新
'''class Solution:def totalFruit(self, fruits: List[int]) -> int:# 请款1、数组长度小于等于2if len(fruits) <= 2:return len(fruits)# 情况2、滑动窗口+哈希表result = 2  # 取当前情况中 可能的最小值left, right = 0, 0  # 双指针分别负责滑动窗口的左右边界hashTable = {}  # 滑动窗口对应的子串需要哈希表统计while right < len(fruits):# 1、当移动right扩大窗口,进行哪些操作if fruits[right] in hashTable:hashTable[fruits[right]] += 1else:hashTable[fruits[right]] = 1# 2、什么条件下,窗口应该暂停扩大,开始移动left缩小窗口while len(hashTable) == 3:# 3、缩小窗口进行哪些操作hashTable[fruits[left]] -= 1if hashTable[fruits[left]] == 0:hashTable.pop(fruits[left])left += 1# 4、更新结果result = max(result, right - left + 1)  # 滑窗[left, right]是左闭右闭区间,子数组长度==元素个数right += 1return resultif __name__ == '__main__':obj = Solution()while True:try:in_line = input().strip().split('=')[1].strip()[1: -1]nums = []if in_line != '':for n in in_line.split(','):nums.append(int(n))# print(nums)print(obj.totalFruit(nums))except EOFError:break

3. 无重复字符的最长子串

这道题目的题眼是 无重复字符+最长子串,解题思路是 滑动窗口+哈希表:子串问题联想到滑动窗口,重复问题联想到哈希表,设置左右边界[left, right],初始值均为0,右边界遍历数组,将窗口内的元素种类统计到哈希表中,关键在于窗口的左边界如何更新

'''
3. 无重复字符的最长子串
题目描述:给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度
示例 1:输入: s = "abcabcbb"输出: 3解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
题眼:无重复字符+最长子串
思路:滑动窗口+哈希表:子串问题联想到滑动窗口,重复问题联想到哈希表,设置左右边界[left, right],初始值均为0,右边界遍历数组,
将窗口内的元素种类统计到哈希表中,关键在于窗口的左边界如何更新
'''class Solution:def lengthOfLongestSubstring(self, s: str) -> int:# 情况1、字符串长度小于等于1if len(s) <= 1:return len(s)# 情况2、滑动窗口+哈希表result = 1  # 取当前情况中 可能的最小值left, right = 0, 0hashTable = {}  # 滑动窗口对应的子串需要哈希表统计while right < len(s):# 1、当移动right扩大窗口,进行哪些操作if s[right] not in hashTable:hashTable[s[right]] = 1else:hashTable[s[right]] += 1# 2、什么条件下,窗口应该暂停扩大,开始移动left缩小窗口while hashTable[s[right]] > 1:# 3、缩小窗口进行哪些操作hashTable[s[left]] -= 1left += 1# 4、更新结果result = max(result, right - left + 1)  # 滑窗[left, right]是左闭右闭区间,子数组长度==元素个数right += 1return resultif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')[1].strip()[1: -1]s = ""if in_line != "":s = in_lineprint(obj.lengthOfLongestSubstring(s))except EOFError:break

相关文章:

leetcode分类刷题:滑动窗口(二、重复元素类型)

1、连续子数组、连续子串问题通常需要滑动窗口来求解&#xff0c;本篇文章对应的“二、重复元素类型”在此基础上对连续子数组、连续子串中重复元素个数、种类进行考察&#xff0c;此时&#xff0c;需要使用和维护哈希表进行左右指针的移动&#xff0c;因此这类题目对应的解法为…...

MySQL—buffer pool

一、buffer pool的介绍 Buffer pool是什么 一个内存区域&#xff0c;为了提⾼数据库的性能&#xff0c;数据库操作数据的时候&#xff0c;把硬盘上的数据加载到buffer pool&#xff0c;不直接和硬盘打交道&#xff0c;操作的是 buffer pool的数据&#xff0c;数据库的增删改查…...

《C和指针》笔记8: 枚举类型

枚举 (enumerated)类型就是指它的值为符号常量而不是字面值的类型&#xff0c;它们以下面这种形式声明&#xff1a; enum Jar_Type { CUP, PINT, QUART, HALF_GALLON, GALLON };这条语句声明了一个类型&#xff0c;称为Jar_Type。这种类型的变量按下列方式声明&#xff1a; e…...

Python爬虫框架之Selenium库入门:用Python实现网页自动化测试详解

概要 是否还在为网页测试而烦恼&#xff1f;是否还在为重复的点击、等待而劳累&#xff1f;试试强大的Selenium&#xff01;让你的网页自动化测试变得轻松有趣&#xff01; 一、Selenium库到底是什么&#xff1f; Selenium 是一个强大的自动化测试工具&#xff0c;它可以让你直…...

docker swarm 部署服务网络问题

docker swarm 服务部署问题 docker swarm 部署服务时可能会出现&#xff0c;启动服务特别慢的情况&#xff0c;甚至一个service 启动后&#xff0c;容器会长时间处于 preparing 状态&#xff0c;直到 状态切换成 running 状态后&#xff0c;才会启动下一个service。然后查询资…...

1.00001git源码clone后进行编译(带调试)

– 新建用户 useradd postgres passwd postgres – 用户加入sude组 先cd到/etc/sudoers目录下 由于sudoers文件为只读权限&#xff0c;所以需要添加写入权限&#xff0c;chmod uw sudoers vim sudoers 找到root ALL (ALL) ALL这一行&#xff0c;在下一行加入username ALL (A…...

使用StorageClass动态创建pv

rook-ceph安装部署到位后&#xff0c;就可以开始来尝试使用StorageClass来动态创建pv了。 有状态的中间件在kubernetes上落地基本上都会用到StorageClass来动态创建pv&#xff08;对于云上应用没有那么多烦恼&#xff0c;云硬盘很好用&#xff0c;但是对于自己学习和练习来说还…...

数据结构(Java实现)-ArrayList与顺序表

什么是List List是一个接口&#xff0c;继承自Collection。 List的使用 List是个接口&#xff0c;并不能直接用来实例化。 如果要使用&#xff0c;必须去实例化List的实现类。在集合框架中&#xff0c;ArrayList和LinkedList都实现了List接口。 线性表 线性表&#xff08;lin…...

性能优化维度

CPU 首先检查 cpu&#xff0c;cpu 使用率要提升而不是降低。其次CPU 空闲并不一定是没事做&#xff0c;也有可能是锁或者外部资源瓶颈。常用top、vmstat命令查看信息。 vmstat 命令: top: 命令 IO iostat 命令&#xff1a; Memory free 命令&#xff1a; 温馨提示&#xff1a…...

PMP P-06 Resource Management

...

【C++】map的奇葩用法:和函数结合

2023年8月26日&#xff0c;周六下午 今天才发现map居然还能这样用... #include <iostream> #include <map> #include <functional>void printOne() {std::cout << "已经打印出1" << std::endl; }void printTwo() {std::cout <<…...

关于JVM的参数类型

JVM参数类型&#xff0c;主要是可以分为三类。分别是&#xff1a; 标准参数 例如&#xff1a; -help-server-client-version-showversion-cp-classpath 等等&#xff0c;这类参数的特点是在jdk各版本里基本不会变的&#xff0c;相对稳定。 X参数 X参数也就是非标准化参数&am…...

HTTP协议中的Content-Type及其常见类型

什么是Content-Type&#xff1f; Content-Type是HTTP协议中的一个头部字段&#xff0c;用于指示请求或响应中所传输的实体的媒体类型。 为什么使用Content-Type&#xff1f; 使用Content-Type可以告知接收方如何解析和处理传输的数据&#xff0c;确保数据能够正确地被解析和…...

android Junit4编写自测用例

10多年的android开发经验&#xff0c;一直以来呢&#xff0c;也没有使用过android自带的测试代码编写。说来也惭愧。今天也花了点时间稍微研究了下。还挺简单。接下来就简单的说一下。 新建工程 直接默认新建一个工程&#xff0c;就会有两个目录androidTest和test(unitTest)两…...

arcgis:画一幅自己城市的shp地图

首先打开ArcGis10.6&#xff0c;点击带黄底的小加号&#xff0c;添加底图。 可以选择中国地图彩色版&#xff0c;然后双击&#xff0c;转动鼠标滑轮找到属于自己的城市。 点击-目录&#xff0c;在新建的文件夹里右击-新建-shapefile。 格式选择折线&#xff0c;先把主要河流道路…...

采购油封时要考虑的因素

对于依赖机械和设备的行业来说&#xff0c;油封的选择是一个关键的决定&#xff0c;以确保平稳运行并防止流体泄漏。由于有多种选择&#xff0c;了解购买油封时要考虑的关键因素对于确保适合特定应用至关重要。让我们深入研究一下在此选择过程中发挥关键作用的考虑因素。 1、运…...

【无标题】科目一笔记

载人超过核定人数 校车/公路客运汽车/旅游客运汽车 未达到20%&#xff0c;-6超过20%以上&#xff0c;-12 七座以上载客汽车 1. 超过20%以上未达到50%&#xff0c;-6 2. 超过50%以上未达到100%&#xff0c;-9 其他载客汽车 1. 超过20%以上未达到50%&#xff0c;-3 2. 超过50…...

java八股文面试[数据结构]——HashMap和HashTable区别

HashMap源码中的重要常量 DEFAULT_INITIAL_CAPACITY: HashMap的默认容量&#xff0c;16 MAXIMUM_CAPACITY&#xff1a; HashMap的最大支持容量&#xff0c;2^30 TREEIFY_THRESHOLD&#xff1a;Bucket中链表长度大于该默认值&#xff0c;转化为红黑树。 UNTREEIFY_THRESHOLD…...

乐趣无限:10款基于Pygame的经典游戏合集

​​​​​​引言 游戏开发一直是许多程序员和游戏爱好者追求的梦想。而Pygame作为一款功能强大的游戏开发库&#xff0c;为我们提供了实现各种有趣游戏的工具和接口。在本文中&#xff0c;我将向大家介绍10款基于Pygame的经典游戏合集&#xff0c;从简单的猜数字到刺激的飞机…...

php检测数组是否存在某个键,和是否存在某个变量

一、array_key_exists() array_key_exists() 是一个 PHP 内置的函数&#xff0c;用于判断数组中是否存在指定的键。该函数接收两个参数&#xff0c;第一个是键名&#xff0c;第二个是数组。 $arr array(name > Jack, age > 20, country > China);if (array_key_exi…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...

django blank 与 null的区别

1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是&#xff0c;要注意以下几点&#xff1a; Django的表单验证与null无关&#xff1a;null参数控制的是数据库层面字段是否可以为NULL&#xff0c;而blank参数控制的是Django表单验证时字…...