免费网站建设模板,一个页面多少钱,南昌模板建站定制,wordpress文章摘要字数文章目录一、 数组理论基础二、 二分查找2.1 解题思路2.2 练习题2.2.1 二分查找(题704)2.2.2 搜索插入位置#xff08;题35#xff09;2.2.3 查找排序数组元素起止位置#xff08;题34#xff09;2.2.4 有效的完全平方数#xff08;题367#xff09;2.2.5 x 的平方根题352.2.3 查找排序数组元素起止位置题342.2.4 有效的完全平方数题3672.2.5 x 的平方根题692.2.6 寻找峰值题1622.2.7 寻找旋转排序数组中的最小值题1532.2.8 搜索旋转排序数组 题33三 双指针法3.1 解题思路3.2 练习题3.2.1 删除排序数组中的重复项题263.2.2 移动零题2833.2.3 比较含退格的字符串题8443.2.4 有序数组的平方题9773.2.5 合并两个有序数组题883.2.6 两数之和 II - 输入有序数组题1673.2.7 移动零题2833.2.8 颜色分类题75四、滑动窗口4.1 解题思路4.2 练习题4.2.1 无重复字符的最长子串题34.2.2 字符串的排列题5674.2.3 最小覆盖子串题764.2.4 最短超串4.2.5 找到字符串中所有字母异位词题4384.2.6 串联所有单词的子串题30资源力扣题库、LeetCode 刷题列表、代码随想录 一、 数组理论基础 参考代码随想录《数组理论基础》 数组是存放在连续内存空间上的相同类型数据的集合数组可以方便的通过下标索引的方式获取到下标下对应的数据例如 有两点需要注意
数组下标都是从0开始的。数组内存空间的地址是连续的
正是因为数组的在内存空间的地址是连续的所以我们在删除或者增添元素的时候就难免要移动其他元素的地址。例如删除下标为3的元素需要对下标为3的元素后面的所有元素都要做移动操作如图所示 那么二维数组在内存的空间地址是连续的么不同编程语言的内存管理是不一样的。在C中二维数组是连续分布的Java是没有指针的同时也不对程序员暴露其元素的地址寻址操作完全交给虚拟机。
二、 二分查找
2.1 解题思路 二分法的前提条件数组为有序数组 循环不变量规则在二分查找的过程中区间的定义是不变量所以在while寻找中每一次边界的处理都要坚持根据区间的定义来操作。 区间的定义决定了二分法的代码应该如何写。区间的定义一般为两种左闭右闭即[left, right]或者左闭右开即[left, right)。
具体思路 1. 左闭右闭写法 因为定义target在[left, right]区间所以有如下两点
while (left right) 要使用 因为left right是有意义的所以使用 if (nums[middle] target) right 要赋值为 middle - 1因为当前这个nums[middle]一定不是target那么接下来要查找的左区间结束下标位置就是 middle - 1
2. 左闭右开写法 因为定义target在[left, right)区间所以有如下两点
while (left right)这里使用 ,因为left right在区间[left, right)是没有意义的if (nums[middle] target) right 更新为 middle因为当前nums[middle]不等于target去左区间继续寻找而寻找区间是左闭右开区间所以right更新为middle即下一个查询区间不会去比较nums[middle]
2.2 练习题
2.2.1 二分查找(题704)
解法一左闭右闭:
class Solution:def search(self, nums: List[int], target: int) - int:left, right 0, len(nums) - 1 # 定义target在左闭右闭的区间里[left, right]while left right:middle left (right - left) // 2 # 防止溢出 等同于(left right)/2 if nums[middle] target:right middle - 1 # target在左区间所以[left, middle - 1]elif nums[middle] target:left middle 1 # target在右区间所以[middle 1, right]else:return middle # 数组中找到目标值直接返回下标return -1 # 未找到目标值解法二左闭右开
class Solution:def search(self, nums: List[int], target: int) - int:left, right 0, len(nums) # 定义target在左闭右开的区间里即[left, right)while left right: # 因为left right的时候在[left, right)是无效的空间所以使用 middle left (right - left) // 2if nums[middle] target:right middle # target 在左区间在[left, middle)中elif nums[middle] target:left middle 1 # target 在右区间在[middle 1, right)中else:return middle # 数组中找到目标值直接返回下标return -1 # 未找到目标值2.2.2 搜索插入位置题35
要在数组中插入目标值无非是这四种情况
目标值在数组所有元素之前目标值等于数组中某一个元素就是上一题目标值插入数组中的位置nums[pos−1]target≤nums[pos]目标值在数组所有元素之后
对于数组中没有目标值的情况其实就是寻找升序数组中第一个大于等于target\textit{target}target 的下标。经过测试可知这个下标是right1left所以本题答案为
class Solution(object):def searchInsert(self, nums, target)::type nums: List[int]:type target: int:rtype: intleft,right0,len(nums)-1 anslen(nums) while leftright:mid(leftright)//2if nums[mid]target:leftmid1elif nums[mid]target:rightmid-1else:return midreturn right12.2.3 查找排序数组元素起止位置题34 直观的思路肯定是从前往后遍历一遍。用两个变量记录第一次和最后一次遇见 target\textit{target}target 的下标但这个方法的时间复杂度为 O(n)O(n)O(n)没有利用到数组升序排列的条件。由于数组已经排序因此整个数组是单调递增的我们可以利用二分法来加速查找的过程。 考虑target开始和结束位置其实就是查找数组中第一个等于target 的位置记为start和第一个大于target 的位置减1记为 end。为了代码的复用我们定义 lower_bound(nums,target)函数表示在 numsnumsnums 数组中二分查找 targettargettarget的位置。 最后因为 targettargettarget可能不存在数组中因此我们需要重新校验我们得到的两个下标看是否符合条件如果符合条件就返回[start,end]不符合就返回[−1,−1]。
class Solution(object):def searchRange(self, nums, target)::type nums: List[int]:type target: int:rtype: List[int]def lower_bound(nums,target):# lower_bound返回最小的满足nums[i]targrt的ileft,right0,len(nums)-1 while leftright:mid(leftright)//2if nums[mid]target:leftmid1else:rightmid-1 return right1 # 或leftstartlower_bound(nums,target) # 第一个大于等于target的下标if startlen(nums) or nums[start]!target:# 分别对应target大于整个数组和target不在数组中return [-1,-1]else:endlower_bound(nums,target1)-1 # 第一个大于target 的下标return [start,end]2.2.4 有效的完全平方数题367
class Solution:def isPerfectSquare(self, num: int) - bool:left,right1,numwhile leftright:mid(leftright)//2if mid*midnum:rightmid-1elif mid*midnum:leftmid1else:return Truereturn False2.2.5 x 的平方根题69 由于 x 平方根的整数部分ans 是满足 k2≤xk^2 \leq xk2≤x的最大 k 值因此我们可以对 k进行二分查找从而得到答案。 二分查找的下界为 0上界可以粗略地设定为 x。在二分查找的每一步中我们只需要比较中间元素 mid 的平方与 x 的大小关系并通过比较的结果调整上下界的范围。由于我们所有的运算都是整数运算不会存在误差因此在得到最终的答案 ans 后也就不需要再去尝试 ans1 了。
class Solution(object):def mySqrt(self, x)::type x: int:rtype: intleft,right0,xwhile leftright:mid(leftright)//2if mid*midx: # 根据牛顿迭代法可以写mid**2xleftmid1else:rightmid-1return right2.2.6 寻找峰值题162 使用两个指针 left、right 。left 指向数组第一个元素right 指向数组最后一个元素。取区间中间节点 mid并比较 nums[mid] 和 nums[mid 1] 的值大小。
如果 nums[mid] 小于 nums[mid 1]则右侧存在峰值令 left mid 1。如果 nums[mid] 大于等于 nums[mid 1]则左侧存在峰值令 right mid。 最后当 left right 时跳出循环返回 left。
class Solution(object):def findPeakElement(self, nums)::type nums: List[int]:rtype: intleft,right0,len(nums)-1while leftright:mid left (right - left) // 2if nums[mid] nums[mid 1]:left mid 1else:right midreturn left 2.2.7 寻找旋转排序数组中的最小值题153 二分查找的前提条件是数组有序本题数组经过旋转之后前半部分和后半部分也都是有序的所以也可以使用二分查找。 数组经过「旋转」之后会有两种情况第一种就是原先的升序序列另一种是两段升序的序列。第一种的最小值在最左边。第二种最小值在第二段升序序列的第一个元素。 解说视频见官方题解 如果 nums[mid] nums[right]则最小值一定在 mid 右侧则令left mid 1 继续查找右侧区间。如果 nums[mid] ≤ nums[right]则最小值一定在 mid 左侧或者 mid 位置令 right mid 继续查找左侧区间。
class Solution(object):def findMin(self, nums)::type nums: List[int]:rtype: intleft,right0,len(nums)-1while leftright: # 不能取等号保证查找区间至少有一个元素mid(leftright)//2if nums[mid]nums[right]:leftmid1else:rightmidreturn nums[left]类似题目还有154. 寻找旋转排序数组中的最小值 II 代码如下
class Solution:def findMin(self, nums: List[int]) - int:left 0right len(nums) - 1while left right:mid left (right - left) // 2if nums[mid] nums[right]:left mid 1elif nums[mid] nums[right]:right midelse: # 无法判断在 mid 的哪一侧可以采用 right right - 1 逐步缩小区域right right - 1return nums[left]2.2.8 搜索旋转排序数组 题33 原本为升序排列的数组 nums 经过「旋转」之后会有两种情况第一种就是原先的升序序列另一种是两段升序的序列。其实我们可以把第一种情况中的整个数组看做是左半部分然后右半部分为空数组。所以将旋转后的数组看成左右两个升序部分左半部分和右半部分。 创建两个指针 left、right分别指向数组首尾。让后计算出两个指针中间值 mid。将 mid 与两个指针做比较并考虑与 target 的关系。 如果 mid[mid] target说明找到了 target直接返回下标。 如果 nums[mid] ≥ nums[left]则 mid 在左半部分因为右半部分值都比 nums[left] 小。 如果 nums[mid] ≥ target并且 target ≥ nums[left]则 target 在左半部分并且在 mid 左侧此时应将 right 左移到 mid - 1 位置。如果 nums[mid] ≤ target则 target 在左半部分并且在 mid 右侧此时应将 left 右移到 mid 1 位置。如果 nums[left] target则 target 在右半部分应将 left 移动到 mid 1 位置。 如果 nums[mid] nums[left]则 mid 在右半部分因为右半部分值都比 nums[left] 小。 如果 nums[mid] target并且 target ≤ nums[right]则 target 在右半部分并且在 mid 右侧此时应将 left 右移到 mid 1 位置。如果 nums[mid] ≥ target则 target 在右半部分并且在 mid 左侧此时应将 right 左移到 mid - 1 位置。如果 nums[right] target则 target 在左半部分应将 right 左移到 mid - 1 位置
class Solution:def search(self, nums: List[int], target: int) - int:left 0right len(nums) - 1while left right:mid left (right - left) // 2if nums[mid] target:return midif nums[mid] nums[left]:if nums[mid] target and target nums[left]:right mid - 1else:left mid 1else:if nums[mid] target and target nums[right]:left mid 1else:right mid - 1return -1与之类似的还有搜索旋转排序数组 II区别是数组元素会重复。 如果 nums[mid] nums[left]则 mid 在左半部分因为右半部分值都比 nums[left] 小。 如果 nums[mid] ≥ target并且 target ≥ nums[left]则 target 在左半部分并且在 mid 左侧此时应将 right 左移到 mid - 1 位置。否则如果 nums[mid] target则 target 在左半部分并且在 mid 右侧此时应将 left 右移到 mid 1。否则如果 nums[left] target则 target 在右半部分应将 left 移动到 mid 1 位置。 如果 nums[mid] nums[left]则 mid 在右半部分因为右半部分值都比 nums[left] 小。 如果 nums[mid] target并且 target ≤ nums[right]则 target 在右半部分并且在 mid 右侧此时应将 left 右移到 mid 1 位置。否则如果 nums[mid] ≥ target则 target 在右半部分并且在 mid 左侧此时应将 right 左移到 mid - 1 位置。否则如果 nums[right] target则 target 在左半部分应将 right 左移到 mid - 1 位置。 最终判断 nums[left] 是否等于 target如果等于则返回 True否则返回 False。
class Solution:def search(self, nums: List[int], target: int) - bool:n len(nums)if n 0:return Falseleft 0right len(nums) - 1while left right:mid left (right - left) // 2if nums[mid] nums[left]:if nums[left] target and target nums[mid]:right midelse:left mid 1elif nums[mid] nums[left]:if nums[mid] target and target nums[right]:left mid 1else:right midelse:if nums[mid] target:return Trueelse:left left 1return nums[left] target三 双指针法
3.1 解题思路
以 移除元素27举例介绍双指针法。
暴力解法这个题目暴力的解法就是两层for循环一个for循环遍历数组元素 第二个for循环更新数组。删除过程如下
很明显暴力解法的时间复杂度是O(n2)O(n^2)O(n2)空间复杂度O(1)O(1)O(1)。
双指针法快慢指针法 右指针 right 指向当前将要处理的元素左指针left 指向下一个将要赋值的位置。通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。 如果右指针指向的元素不等于 val它一定是输出数组的一个元素我们就将右指针指向的元素复制到左指针位置然后将左右指针同时右移如果右指针指向的元素等于 val它不能在输出数组里此时左指针不动右指针右移一位。 整个过程保持不变的性质是区间[0,left) 中的元素都不等于 val。当左右指针遍历完输入数组以后left 的值就是输出数组的长度。这样的算法在最坏情况下输入数组中没有元素等于val左右指针各遍历了数组一次。
class Solution:def removeElement(self, nums: List[int], val: int) - int:fast 0 # 快指针slow 0 # 慢指针size len(nums)while fast size: # a size 时nums[a] 会越界slow 用来收集不等于 val 的值如果 fast 对应值不等于 val则把它与 slow 替换同时slow1。fast不管是否等于val始终都有fast1if nums[fast] ! val:nums[slow] nums[fast]slow 1fast 1return slow双指针优化 思路如果要移除的元素恰好在数组的开头例如序列 [1,2,3,4,5]当 val 为 1时我们需要把每一个元素都左移一位。注意到题目中说「元素的顺序可以改变」。实际上我们可以直接将最后一个元素 5 移动到序列开头取代元素 1得到序列 [5,2,3,4]同样满足题目要求。这个优化在序列中val 元素的数量较少时非常有效。算法实现方面我们依然使用双指针两个指针初始时分别位于数组的首尾向中间移动遍历该序列。 如果左指针 left 指向的元素等于 val此时将右指针right 指向的元素复制到左指针 left 的位置然后右指针 right 左移一位。如果赋值过来的元素恰好也等于val可以继续把右指针 right 指向的元素的值赋值过来左指针left 指向的等于val 的元素的位置继续被覆盖直到左指针指向的元素的值不等于 val 为止。 当左指针left 和右指针right 重合的时候左右指针遍历完数组中所有的元素。 这样的方法两个指针在最坏的情况下合起来只遍历了数组一次。与方法一不同的是方法二避免了需要保留的元素的重复赋值操作。
class Solution(object):def removeElement(self, nums, val)::type nums: List[int]:type val: int:rtype: intslow,fast0,len(nums)-1while slow fast:if nums[slow] val:nums[slow]nums[fast]fast-1else:slow1return slow3.2 练习题
3.2.1 删除排序数组中的重复项题26
class Solution(object):def removeDuplicates(self, nums)::type nums: List[int]:rtype: intfast 1 # 快指针,因为后面会用到fast-1所以fast赋值从1开始slow 1 # 慢指针size len(nums)while fast size: # a size 时nums[a] 会越界if nums[fast] ! nums[fast-1]: # 判断很前一个数是否重复nums[slow] nums[fast]slow 1fast 1return slow3.2.2 移动零题283
思路使非0元素左移等同于使0往右移。 算法使用双指针右指针不断向右移动。每次右指针指向非零数则将左右指针对应的数交换同时左指针右移否则只有右指针右移左指针不动。 每次交换都是将左指针的零与右指针的非零数交换结果就是左右指针之间都是0。
class Solution(object):def moveZeroes(self, nums)::type nums: List[int]:rtype: None Do not return anything, modify nums in-place instead.left,right 0,0 while right len(nums): # a size 时nums[a] 会越界if nums[right] ! 0: nums[left],nums[right] nums[right], nums[left] left 1right1return nums也可以看做是参考了快速排序的思想用0当做这个中间点把不等于0(注意题目没说不能有负数)的放到中间点的左边等于0的放到其右边。使用两个指针left和right只要nums[right]!0我们就交换nums[left]和nums[right] 用for循环写出来就是
class Solution(object):def moveZeroes(self, nums)::type nums: List[int]:rtype: None Do not return anything, modify nums in-place instead. left 0 for right in range(len(nums)):# 当前元素!0就把其交换到左边等于0的交换到右边if nums[right]:nums[left],nums[right] nums[right],nums[left]left 1如果right指针指向末尾来进行交换会改变非0元素顺序。
3.2.3 比较含退格的字符串题844 栈有后进先出的特性比如网页的后退、文本编辑中的撤销操作等这些操作的特性都契合这个特性本题也是一样所以可以考虑用栈来处理。 方法一重构字符串用栈处理遍历过程每次我们遍历到一个字符
如果它是退格符那么我们将栈顶弹出如果它是普通字符那么我们将其压入栈中。 class Solution(object):def backspaceCompare(self, s, t)::type s: str:type t: str:rtype: booldef build(s):ls list()for ch in s:if ch ! #:ls.append(ch)elif ls:ls.pop()return .join(ls)return build(s) build(t)复杂度分析
时间复杂度O(NM)O(NM)O(NM)其中 N 和 M分别为字符串 S 和 T 的长度。我们需要遍历两字符串各一次。空间复杂度O(NM)O(NM)O(NM)其中 N 和 M 分别为字符串 S 和 T 的长度。主要为还原出的字符串的开销。
方法二双指针
class Solution(object):def backspaceCompare(self, s, t)::type s: str:type t: str:rtype: booldef back(s):slist(s)slow,fast0,0while fastlen(s):# 只要快指针不是指向#就将其赋值给慢指针同时慢指针右移if s[fast]!#: s[slow]s[fast]slow1else: # 当快指针指向#时慢指针后退一格if slow0: # 慢指针指向空不再退格slow-1fast1return s[:slow]return back(s)back(t)方法三双指针官方 一个字符是否会被删掉只取决于该字符后面的退格符而与该字符前面的退格符无关。因此当我们逆序地遍历字符串就可以立即确定当前字符是否会被删掉。 具体地我们定义skip 表示当前待删除的字符的数量。每次我们遍历到一个字符
若该字符为退格符则我们需要多删除一个普通字符我们让skip 1若该字符为普通字符 若skip 为 0则说明当前字符不需要删去若 skip 不为 0则说明当前字符需要删去我们让skip - 1。 所以可以定义两个指针分别指向两字符串的末尾。每次我们让两指针逆序地遍历两字符串直到两字符串能够各自确定一个字符然后将这两个字符进行比较。重复这一过程直到找到的两个字符不相等或遍历完字符串为止。
class Solution(object):def backspaceCompare(self, s, t)::type s: str:type t: str:rtype: boolup,downlen(s)-1,len(t)-1skip_s,skip_t0,0while up0 or down0: #同时遍历两个字符串while up0: # 先逆序遍历s中字符串找到不需要删除的普通字符if s[up]#:skip_s1up-1else:if skip_s0:up-1skip_s-1else:breakwhile down0: # 先逆序遍历s中字符串找到不需要删除的普通字符if t[down]#:skip_t1down-1else:if skip_t0:down-1skip_t-1else:break# 开始进行字符对比if up0 and down0:if s[up]!t[down]:return False# 存在一个字符串遍历完而另一个还没遍历完的情况此时也是返回Falseelif up0 or down0: return False# 无论何种情况都要开始遍历到下一个位置up-1down-1return True3.2.4 有序数组的平方题977 本题主要思路是原数组nuns本身是有序的只不过负数的平方反过来成了降序。比如[-3,-2,-1]是升序的其平方[9,4,1]成了降序。这样造成数组每个元素平方之后是一个两边大中间小的结构
输入nums [-4,-1,0,3,10]
平方nums [16,1,0,9,100]此时可以考虑使用一个额外的列表ls初始化为与nums等长。然后使用指针idx从后往前遍历ls则每次最大的元素一定是从nums的两端往中间取至于具体是左端还是右端比较这两个元素就行。故考虑使用左右指针left和right分别从0和-1的位置开始遍历。具体的
若 nums[left]**2nums[right]**2则ls[idx]nums[right]**2同时左指针往右一格遍历nums左侧的下一个元素若 nums[left]**2nums[right]**2则ls[idx]nums[left]**2同时右指针往左一格遍历nums右侧的下一个元素每次ls赋值完指针idx都左移一格即idx-1。
参考别人图解则是 class Solution(object):def sortedSquares(self, nums)::type nums: List[int]:rtype: List[int]# 初始化额外数组ls初始赋值nums左右指针和数组ls的末端指针idx ls[-1]*len(nums)left,right,idx0,len(nums)-1,len(nums)-1# 开始从末端遍历ls最大值只会来自nums的两端故遍历左右指针更大的数赋值给ls[idx]while left right:if nums[left]**2nums[right]**2:ls[idx]nums[right]**2# 右侧更大则赋值给ls[idx]同时right和idx都右移一位right-1idx-1else:ls[idx]nums[left]**2left1idx-1return ls3.2.5 合并两个有序数组题88 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2其元素个数分别是 m 和 n 。请你 合并 nums2 到 nums1 中使合并后的数组同样按 非递减顺序 排列。 注意最终合并后数组不应由函数返回而是存储在数组 nums1 中。为了应对这种情况nums1 的初始长度为 m n其中前 m 个元素表示应合并的元素后 n 个元素为 0 应忽略。nums2 的长度为 n 。
示例
输入nums1 [1,2,3,0,0,0], m 3, nums2 [2,5,6], n 3输出[1,2,2,3,5,6]解释需要合并 [1,2,3] 和 [2,5,6] 。合并结果是 [1,2,2,3,5,6] 其中斜体加粗标注的为 nums1 中的元素。nums1.length m n0 m, n 200 这道题和上一题很相似两个数组都是有序的为了利用这一性质我们可以使用双指针方法每次将两个数组中更大的元素放在nums1末尾。这样做是为了不使用额外的存储空间所以需要倒序遍历。
class Solution(object):def merge(self, nums1, m, nums2, n)::type nums1: List[int]:type m: int:type nums2: List[int]:type n: int:rtype: None Do not return anything, modify nums1 in-place instead.# p1和p2分别指向两个数组的末尾倒序遍历p1,p2m-1,n-1idxmn-1# p1、p2如果不限制可以为负值也能表示下标所以不能单纯设置idx》0while p10 and p20:# print(p1,p2,idx)if nums1[p1]nums2[p2]:# 这里写nums1[idx]nums1[p1]结果也正确下同nums1[idx],nums1[p1]nums1[p1],nums1[idx]p1-1else:nums1[idx],nums2[p2]nums2[p2],nums1[idx]p2-1idx-1 # 当nums1序列中大数排完后p10,循环终止此时p2可能还有剩下的数这些数都是最小的一部分直接接到nums1前面# print(nums2[:p21] )nums1[:p21]nums2[:p21] return nums13.2.6 两数之和 II - 输入有序数组题167 这道题和两数之和题3的区别是数组是有序的。所以可以考虑使用两个指针分别遍历数组如果两个元素之和小于目标值则将左侧指针右移一位。如果两个元素之和大于目标值则将右侧指针左移一位。重复上述操作直到找到答案。
class Solution:def twoSum(self, numbers: List[int], target: int) - List[int]:low, high 0, len(numbers) - 1while low high:total numbers[low] numbers[high]if total target:return [low 1, high 1]elif total target:low 1else:high - 1return [-1, -1]3.2.7 移动零题283
class Solution(object):def moveZeroes(self, nums)::type nums: List[int]:rtype: None Do not return anything, modify nums in-place instead. left 0 # 两个指针l和rfor right in range(len(nums)):# 当前元素!0就把其交换到左边等于0的交换到右边if nums[right]:nums[left],nums[right] nums[right],nums[left]left 13.2.8 颜色分类题75
方法一单指针 这道题和上一题很类似最简单的方法是遍历两次先将0排到最前面再接着将1排到前面
class Solution:def sortColors(self, nums: List[int]) - None:Do not return anything, modify nums in-place instead.# 两次遍历先排0再排1left0for i in range(len(nums)):if nums[i]0:nums[left],nums[i]nums[i],nums[left]left1 rightleft # 前面left个位置已经排好了0 for j in range(right,len(nums)):if nums[j]1:nums[right],nums[j]nums[j],nums[right]right1return nums方法二双指针官方题解 我们可以额外使用一个指针即使用两个指针分别用来交换 0 和1。具体地我们用指针 p0p_0p0来交换 0p1p_1p1来交换 1初始值都为 0。当我们从左向右遍历整个数组时
如果找到了 1那么将其与 nums[p1]nums[p_1]nums[p1] 进行交换并将 p1p_1p1向后移动一个位置这与方法一是相同的如果找到了 0那么将其与 nums[p0]nums[p_0]nums[p0] 进行交换并将 p0p_0p0向后移动一个位置。这样做是正确的吗 我们可以注意到因为连续的 0 之后是连续的 1因此如果我们将 0 与nums[p0]nums[p_0]nums[p0] 进行交换那么我们可能会把一个 1 交换出去。当 p0p1p_0 p_1p0p1时我们已经将一些 1 连续地放在头部此时一定会把一个 1 交换出去导致答案错误。因此如果p0p1p_0 p_1p0p1那么我们需要再将 nums[i]nums[i]nums[i] 与nums[p1]nums[p_1]nums[p1]进行交换其中 i 是当前遍历到的位置。 在进行了第一次交换后nums[i]nums[i]nums[i]的值为 1我们需要将这个 1 放到「头部」的末端。在最后无论是否有 p0p1p_0 p_1p0p1我们需要将 p0p_0p0 和 p1p_1p1均向后移动一个位置而不是仅将 p0p_0p0向后移动一个位置。
class Solution:def sortColors(self, nums: List[int]) - None:Do not return anything, modify nums in-place instead.# 两个指针分别用于交换0和1p0p10for i in range(len(nums)):if nums[i]1:nums[i],nums[p1]nums[p1],nums[i]p11elif nums[i]0:nums[i],nums[p0]nums[p0],nums[i]if p0p1:nums[i],nums[p1]nums[p1],nums[i]p11p01return nums方法三快速排序 我们也可以借鉴快速排序算法中的 partition 过程将 1 作为基准数 pivot然后将序列分为三部分0即比 1 小的部分、等于 1 的部分、2即比 1 大的部分。具体步骤如下
使用两个指针 left、right分别指向数组的头尾。left 表示当前处理好红色元素的尾部right 表示当前处理好蓝色的头部。再使用一个下标 index 遍历数组如果遇到 nums[index] 0就交换 nums[index] 和 nums[left]同时将 left 右移。如果遇到 nums[index] 2就交换 nums[index] 和 nums[right]同时将 right 左移。直到 index 移动到 right 位置之后停止遍历。遍历结束之后此时 left 左侧都是红色right 右侧都是蓝色。注意移动的时候需要判断 index 和 left 的位置因为 left 左侧是已经处理好的数组所以需要判断 index 的位置是否小于 left小于的话需要更新 index 位置。
class Solution:def sortColors(self, nums: List[int]) - None:left 0right len(nums) - 1index 0while index right:if index left:index 1elif nums[index] 0:nums[index], nums[left] nums[left], nums[index]left 1elif nums[index] 2:nums[index], nums[right] nums[right], nums[index]right - 1else:index 1四、滑动窗口
4.1 解题思路
下面以长度最小的子数组题209这一题讲解滑动窗口的思路。 给定一个含有 n 个正整数的数组nums和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl1, …, numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。
示例1 输入s 7, nums [2,3,1,2,4,3] 输出2 解释子数组 [4,3] 是该条件下的长度最小的子数组。输出2解释子数组 [4,3] 是该条件下的长度最小的子数组。 示例2 输入target 11, nums [1,1,1,1,1,1,1,1]输出0 解法一暴力解法 使用两个for循环然后不断的寻找符合条件的子序列时间复杂度很明显是O(n2)O(n^2)O(n2)。 具体的先初始化子数组的最小长度为无穷大枚举数组nums 中的每个下标作为子数组的开始下标对于每个开始下标 i需要找到大于或等于 i 的最小下标 j使得从 [nums[i] , nums[j] ]的元素和大于或等于 s并更新子数组的最小长度此时子数组的长度是 j−i1。
class Solution:def minSubArrayLen(self, s: int, nums: List[int]) - int:if not nums:return 0n len(nums)ans n 1 # 存储最小数组长度for i in range(n):total 0for j in range(i, n): # 计算位置i到位置j的元素和total nums[j]if total s:ans min(ans, j - i 1)breakreturn 0 if ans n 1 else ans解法二滑动窗口 思路使用一个动态区间维护整个区间的和都是大于等于target从左往右遍历并不断更新动态区间的长度。以题目中的示例来举例target 7, nums [2,3,1,2,4,3]来看一下查找的过程 其实从动画中可以发现滑动窗口也可以理解为双指针法的一种只不过这种解法更像是一个窗口的移动所以叫做滑动窗口更适合一些。 在本题中实现滑动窗口主要确定如下三点
窗口内是什么满足其和 ≥ s 的长度最小的 连续 子数组。如何移动窗口的起始位置如果当前窗口的值大于s了窗口就要向前移动了如何移动窗口的结束位置窗口的结束位置就是遍历数组的指针 具体的将右指针right遍历到数组的最右端遍历过程中求出当前子数组的和使用一个变量total来维护。在total target时我们就缩小区间即左指针移右移此时需要total-nums[left]更新区间和并更新区间长度ans。然后 右指针继续右移这样我们总是保证了total target。 最终右指针右移到数组末尾依旧没找到total target或者找到最短子数组长度ans。 注意只有total target时左指针才会移动。因此当右指针移动到下一个位置时总是有前缀和total s。可以看作是每次左指针移动都是在找到一个新的更短的符合条件的连续子数组因此维护的总和total一定是s的而答案一定是更新的。 class Solution(object):def minSubArrayLen(self, target, nums):if len(nums)0:return 0else:n len(nums)# 初始化左右指针、区间和以及区间长度left, right 0, 0total 0ans n 1# 移动右指针计算当前子数组的和while right n:total nums[right]# 只要和大于目标值左指针就一直右移while total target: ans min(ans, right - left 1) # 先更新区间长度再移动指针 total - nums[left] # 区间和减去刚刚舍去的左指针的值left 1right 1return 0 if ans n 1 else ans滑动窗口的精妙之处在于根据当前子序列和大小的情况不断调节子序列的起始位置。从而将O(n2)O(n^2)O(n2)暴力解法降为O(n)O(n)O(n)。
4.2 练习题
4.2.1 无重复字符的最长子串题3
给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。
输入: s “abcabcbb”输出: 3解释: 因为无重复字符的最长子串是 “abc”所以其长度为 3。 方法一官方解法 使用两个指针表示最长子串的左右边界依次递增地枚举子串的起始位置left。假设leftk我们得到了不含重复字符的最长子串的结束位置为right。那么下一次遍历到leftk1时k1到right这个区间字符串仍是不重复的。由于left左移区间缩小故right应该右移遍历直到右侧出现了重复字符为止。 在上面的流程中我们还需要使用一种数据结构来判断是否有重复的字符可以直接使用集合。在左指针右移动的时候我们从集合中移除一个字符在右指针向右移动的时候我们往集合中添加一个字符。
class Solution:def lengthOfLongestSubstring(self, s: str) - int:# 哈希集合记录每个字符是否出现过se set()# 右指针初始值为 -1相当于我们在字符串的左边界的左侧还没有开始移动right, ans -1, 0for i in range(len(s):if i ! 0: # 从第二个字符开始删除# 左指针向右移动一格移除一个字符se.remove(s[i - 1])while right 1 len(nums) and s[right 1] not in se:# 不断地移动右指针se.add(s[right 1])right 1# 第 i 到 rk 个字符是一个极长的无重复字符子串ans max(ans, right - i 1)return ans方法二滑动窗口
class Solution(object):def lengthOfLongestSubstring(self, s)::type s: str:rtype: intleft,right0,0# 因为重复的元素会出现在任何位置比如abccd不能简单的用列表pop(0)# 和位置无关的位置结构可以选用集合seset() ans0 # 子串长度初始化为0当s为空时不会进入for循环此时长度依旧为0for right in range(len(s)):# 指针右移首先添加第一个元素 while s[right] in se:# 当右指针遇到重复元素时左指针右移当前长度减一# 直到右指针不再和集合中元素重复 se.remove(s[left])left1ansmax(ans,right-left1) se.add(s[right]) return ans 注意应该将se.add(s[right]) 放在 while 循环之后否则每次集合先添加就肯定可以进while循环了。 方法三
class Solution(object):def lengthOfLongestSubstring(self, s)::type s: str:rtype: int# 定义当前最长不重复子串的长度le 0# 定义字典用于记录每个字符最后一次出现的位置d {}# 定义left指针用于维护当前子串left -1for r in range(len(s)): if s[r] in d: # 如果当前字符已经在字典中出现过 left max(left, d[s[r]]) # 更新left指针位置d[s[r]] r # 更新当前字符最后一次出现的位置# 更新最长不重复子串的长度le max(le, r - left)return le上面代码中首先定义了当前最长不重复子串的长度 le用于记录结果字典 d用于记录每个字符最后一次出现的位置left指针用于维护当前子串。 接下来使用for循环遍历字符串s对于每个字符如果当前字符已经在字典中出现过那么left指针应该跳到该字符上一次出现的位置的后面一个位置这样才能保证当前子串中没有重复字符。然后更新当前字符最后一次出现的位置遍历right指针并更新答案即可。 需要注意的是重复字符上一次出现的位置可能会更小比如’abbac’故需要设置为max(left, d[s[r]])。
4.2.2 字符串的排列题567 给你两个字符串 s1 和 s2 写一个函数来判断 s2 是否包含 s1 的排列。如果是返回 true 否则返回 false 。换句话说s1 的排列之一是 s2 的 子串 。
输入s1 “ab” s2 “eidbaooo”输出true解释s2 包含 s1 的排列之一 (“ba”). 这道题是 76. 最小覆盖子串 的简单版本。解题思路滑动窗口 字典 分析一 题目要求 s1 的排列之一是 s2 的一个子串。而子串必须是连续的所以要求的 s2 子串的长度跟 s1 长度必须相等。 分析二 那么我们有必要把 s1 的每个排列都求出来吗当然不用。如果字符串 a 是 b 的一个排列那么当且仅当它们两者中的每个字符的个数都必须完全相等。 所以根据上面两点分析我们已经能确定这个题目可以使用 滑动窗口 字典 来解决。 我们使用一个长度和 s1 长度相等的固定窗口大小的滑动窗口在 s2 上面从左向右滑动判断 s2 在滑动窗口内的每个字符出现的个数是否跟 s1 每个字符出现次数完全相等。 我们定义 counter1 是对 s1 内字符出现的个数的统计定义 counter2 是对 s2 内字符出现的个数的统计。在窗口每次右移的时候需要把右边新加入窗口的字符个数在 counter2 中加 1把左边移出窗口的字符的个数减 1。 if counter1 counter2 那么说明窗口内的子串是 s1 的一个排列返回 True如果窗口已经把 s2 遍历完了仍然没有找到满足条件的排列返回 False。 对于题目给的示例一s1 “ab” s2 “eidbaooo”我制作了滑动窗口过程的动画帮助理解 gif动图裁剪压缩网站 躲坑指南
本题中的 counter 可以用字典也可以用数组来实现。用字典的时候需要注意如果移除 left 元素后若 counter2[s2[left]] 0 那么需要从字典中删除 s2[left] 这个key。因为 {a:0, b:1} 和 {b:1} 是不等的。窗口的定义一定要搞清楚是否包含两边的端点比如我定义的窗口是 [left, right] 两个端点都包含那么就需要把两个端点的元素也放入 counter2 中。counter2 初始化的时候只放了 [0, right - 1] 个元素因为在 while 循环中的第一行就是把 right 元素放到 counter2 中。
class Solution(object):def checkInclusion(self, s1, s2)::type s1: str:type s2: str:rtype: bool# 统计 s1 中每个字符出现的次数counter1 collections.Counter(s1)N len(s2)# 定义滑动窗口的范围是 [left, right]闭区间长度与s1相等left ,right 0,len(s1) - 1# 统计窗口s2[left, right - 1]内的元素出现的次数counter2 collections.Counter(s2[0:right])while right N:# 把 right 位置的元素放到 counter2 中counter2[s2[right]] 1# 如果滑动窗口内各个元素出现的次数跟 s1 的元素出现次数完全一致返回 Trueif counter1 counter2:return True# 窗口向右移动前把当前 left 位置的元素出现次数 - 1counter2[s2[left]] - 1# 如果当前 left 位置的元素出现次数为 0 需要从字典中删除否则这个出现次数为 0 的元素会影响两 counter 之间的比较if counter2[s2[left]] 0:del counter2[s2[left]]# 窗口向右移动left 1right 1return False写法二『 一招吃遍七道 』滑动窗口的应用 在窗口滑动的过程中我们维持一个长度为 len(s1) 的滑动窗口当窗口中待匹配的字符数目为 0我们就找到了一个满足要求的子串。此题更进一步的思路可以看下一题最小覆盖子串题76的解答。
class Solution:def checkInclusion(self, s1: str, s2: str) - bool:if len(s1)len(s2):return Falseelse:from collections import Countercount1dict(Counter(s1))needlen(s1) #所需字符的总次数for right in range(len(s2)):chs2[right]如果ch是所需的字符就将ch需要的次数减一但是ch次数0时才表示这个字符还需要此时才有need1而且要先计算need次数因为ch次数先操作会导致need统计错误类似于计算窗口的值再移动窗口if ch in count1:if count1[ch]0: need-1count1[ch]-1窗口是固定大小左指针跟随右指针移动同时维护需求字典 一开始窗口还不到s1长度此时left会小于0。left0是窗口第一次右移leftright-len(s1)if left0:chs2[left]if ch in count1:if count1[ch]0:need1count1[ch]1if need0:return Truereturn False4.2.3 最小覆盖子串题76 这道题和剑指 Offer II 017. 含有所有字符的最短字符串几乎是一样的区别仅仅在于本题的最短子串只有唯一一个而后者可能出现多个只要求取其中任意一个就行。所以二者的代码可以是完全一样的。 我们以哈希表cnt记录目标字符串 t 中待匹配的各字符的数目并在 s 中维护一个变长的滑动窗口期望使得窗口中的字符能够覆盖 t。具体地设定一个非负变量 need 表示当前窗口还需要匹配到的字符总数 当窗口新增一位字符 ch 时 若cnt[ch]0说明 待加入的字符ch 是当前窗口还需要的此时新加入的 ch 能够使得 need-1若cnt[ch]≤0说明 当前窗口不需要这个字符need不变无论cnt[ch]是否大于0由于窗口一直右移cnt[ch]本身的次数是要减一的。所以cnt[ch] 可以为负值这表示表示当前窗口中字符 ch 过多。 当窗口滑出一位字符 ch 时 若cnt[ch]≥0说明 待加入的字符ch 是当前窗口还需要的滑出去需求更大了此时滑出的 ch 能够使得 need1若cnt[ch]0说明 当前窗口不需要这个字符need不变无论cnt[ch]是否大于0由于窗口一直右移cnt[ch]本身的次数是要加一的。 当 need0 时说明找到了覆盖子串 在记录下答案的同时我们还需要尝试收缩窗口左边界参照上一步。
class Solution:def minWindow(self, s: str, t: str) - str:if len(t)len(s):return elif st:return selse:from collections import Countercntdict(Counter(t)) # 哈希表记录需要匹配到的各个字符的数目left0 needlen(t) # 需匹配的字符总数。每次右指针匹配到所需字符need-1所以need0表示匹配到了完整的覆盖子串 lelen(s)1 # 最短长度result # 覆盖子串即返回的结果for right in range(len(s)):chs[right] if ch in cnt: # 窗口右端新加入的字符ch若位于s1中就将其次数-1。可以是负数表示ch有多余的if cnt[ch]0: # 但是只有字符ch大于0才表示这个字符还需要need-1need-1cnt[ch]-1while need0: # 只要所需字符为0就一直移动左指针chs[left]if ch in cnt: # 刚滑出的字符位于s1中操作同上if cnt[ch]0:need1cnt[ch]1# 下面这一段写在while语句之前也可以只要left1在最后一行if right-leftle:leright-leftresults[left:right1]left1return if lelen(s)1 else result4.2.4 最短超串 题目链接 这题和上一题差不多改一下输出结果的格式就行。 class Solution(object):def shortestSeq(self, big, small)::type big: List[int]:type small: List[int]:rtype: List[int]from collections import Countercntdict(Counter(small)) # 哈希表记录需要匹配到的各个字符的数目left0 needlen(small) # 需匹配的字符总数。每次右指针匹配到所需字符need-1所以need0表示匹配到了完整的覆盖子串 lelen(big)1 # 记录最短子串长度 result[] # 返回的结果for right in range(len(big)):chbig[right] if ch in cnt: # 窗口右端新加入的字符ch若位于s1中就将其次数-1。可以是负数表示ch有多余的if cnt[ch]0: # 但是只有字符ch大于0才表示这个字符还需要need-1need-1cnt[ch]-1while need0: # 只要所需字符为0就一直移动左指针chbig[left]if ch in cnt: # 刚滑出的字符位于s1中操作同上if cnt[ch]0:need1cnt[ch]1# 下面这一段写在while语句之前也可以只要left1在最后一行# 只要子串更短就覆盖结果所以即使最短子串有多个也只会返回第一个if right-leftle: #leright-leftresult[left,right]left1return [] if lelen(big)1 else result4.2.5 找到字符串中所有字母异位词题438
给定两个字符串 s 和 p找到 s 中所有 p 的 异位词 的子串返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串包括相同的字符串。
输入: s “cbaebabacd”, p “abc”输出: [0,6]解释: 起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。 这道题和题567几乎一样只是需要返回每个子串的起始位置答案就不写了同样的题还有《剑指 Offer II 015. 字符串中的所有变位词》。
class Solution(object):def findAnagrams(self, s, p)::type s: str:type p: str:rtype: List[int]if len(p)len(s):return []else:from collections import Countercount1dict(Counter(p))needlen(p) #所需字符的总次数result[]for right in range(len(s)):chs[right]如果ch是所需的字符就将ch需要的次数减一但是ch次数0时才表示这个字符还需要此时才有need1而且要先计算need次数因为ch次数先操作会导致need统计错误类似于计算窗口的值再移动窗口if ch in count1:if count1[ch]0: need-1count1[ch]-1窗口是固定大小左指针跟随右指针移动同时维护需求字典 一开始窗口还不到s1长度此时left会小于0。left0是窗口第一次右移leftright-len(p)if left0:chs[left]if ch in count1:if count1[ch]0:need1count1[ch]1if need0:result.append(left1)return result4.2.6 串联所有单词的子串题30 题目链接 class Solution:def findSubstring(self, s: str, words: List[str]) - List[int]: # word的所有排列组合和元素顺序无关可以考虑使用字典不看具体单词只看元素from collections import Counter# 将words中每个元素统计其次数存入字典cnwdict(Counter(words))le1len(.join(words)) # 匹配子串总长度也等于滑动窗口长度le2len(words[0]) # 每个word等长needlen(words) # need表示总共需要的元素数,不等于cnw长度因为有键是多个坑死我了res[] # 记录匹配子串的起始位置for start in range(0,le2): # s的分词方式有多种都需要遍历到#print(start:,start)for right in range(startle2,len(s)1,le2):#还是要分割成若干个单词间隔le2# 遍历右指针如果碰到需要的单词就将其需要次数减1如果次数大于0就将总次数减1# 假如word长为3即le23右指针就从3开始遍历每次加入的字符长度都是3chs[right-le2:right]if ch in cnw:if cnw[ch]0:need-1cnw[ch]-1#print(r:,ch,cnw,need)leftright-le1 # 窗口是固定大小长为le。left0时刚好是要第一次滑动窗口if leftle2:chs[left-le2:left]if ch in cnw:if cnw[ch]0:need1cnw[ch]1#print(ch,cnw,need)if need0:res.append(left)# 每次起点位置遍历完need 和cnw上一次被改了需要重置needlen(words)cnwdict(Counter(words))return res后续有空再补。 904-水果成篮(opens new window) 159-至多包含两个不同字符的最长子串 340-至多包含 K 个不同字符的最长子串 30-串联所有单词的子串 239- 滑动窗口最大值 632-最小区间 727.-最小窗口子序列
