个人网站备案名和运营,设计公司网站公司详情,站长工具seo查询5g5g,室内设计公司经营范围1、连续子数组、连续子串问题通常需要滑动窗口来求解#xff0c;本篇文章对应的“二、重复元素类型”在此基础上对连续子数组、连续子串中重复元素个数、种类进行考察#xff0c;此时#xff0c;需要使用和维护哈希表进行左右指针的移动#xff0c;因此这类题目对应的解法为… 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:break3. 无重复字符的最长子串 这道题目的题眼是 无重复字符最长子串解题思路是 滑动窗口哈希表子串问题联想到滑动窗口重复问题联想到哈希表设置左右边界[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
