网站开发相关书籍,网站建设來超速云建站,中国机械外协加工网,wordpress模板是什么意思哎- -最近本来就没时间写算法 这算法怎么还这么难。。。
10、和为 K 的子数组
给你一个整数数组 nums 和一个整数 k #xff0c;请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1#xff1a;
输入#xff1a;nums [1,1,1]…哎- -最近本来就没时间写算法 这算法怎么还这么难。。。
10、和为 K 的子数组
给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1
输入nums [1,1,1], k 2
输出2
示例 2
输入nums [1,2,3], k 3
输出2
提示 1 nums.length 2 * 104 -1000 nums[i] 1000 -107 k 107
思路解答
前缀和计算数组的前缀和并使用一个哈希表来记录之前出现过的前缀和及其出现次数。遍历数组遍历数组对于每个元素计算当前的前缀和并查找之前是否出现过前缀和为 prefix_sum - k 的情况如果有则累加对应的子数组个数。更新哈希表在遍历过程中更新哈希表记录当前前缀和的出现次数。
def subarraySum(self, nums: list[int], k: int) - int:count 0prefix_sum 0# 初始化前缀和为0的个数为1prefix_sum_count {0: 1}for num in nums:prefix_sum num# 更新count加上之前出现的前缀和为prefix_sum - k的个数count prefix_sum_count.get(prefix_sum - k, 0)# 更新当前前缀和的个数prefix_sum_count[prefix_sum] prefix_sum_count.get(prefix_sum, 0) 1return count
11、滑动窗口最大值
给你一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口最大值。
示例 1
输入nums [1,3,-1,-3,5,3,6,7], k 3
输出[3,3,5,5,6,7]
解释
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7
示例 2
输入nums [1], k 1
输出[1]
提示 1 nums.length 105 -104 nums[i] 104 1 k nums.length
思路解答 使用双端队列维护一个双端队列队列中存储的是数组元素的索引且队列中的索引对应的元素值是递减的。 滑动窗口处理在遍历数组的过程中对于每个元素首先判断队列中的第一个索引是否在当前滑动窗口内如果不在则将其移除。然后将当前元素与队列尾部的元素比较如果比队尾元素大则将队尾元素移除直到队列为空或者当前元素小于等于队尾元素。然后将当前元素的索引加入队列。 获取最大值每次滑动窗口移动时队列的第一个元素对应的就是当前滑动窗口的最大值。
def maxSlidingWindow(self, nums: list[int], k: int) - list[int]:if not nums:return []result []#创建双端队列window collections.deque()for i, num in enumerate(nums):# 移除不在窗口内的元素if window and window[0] i - k 1:window.popleft()# 移除比当前元素小的元素while window and nums[window[-1]] num:window.pop()window.append(i)# 当窗口大小达到k时记录当前窗口的最大值if i k - 1:result.append(nums[window[0]])return result
12、最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 。
注意
对于 t 中重复字符我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如果 s 中存在这样的子串我们保证它是唯一的答案。
示例 1
输入s ADOBECODEBANC, t ABC
输出BANC
解释最小覆盖子串 BANC 包含来自字符串 t 的 A、B 和 C。
示例 2
输入s a, t a
输出a
解释整个字符串 s 是最小覆盖子串。
示例 3:
输入: s a, t aa
输出:
解释: t 中两个字符 a 均应包含在 s 的子串中
因此没有符合条件的子字符串返回空字符串。
提示
m s.lengthn t.length1 m, n 105s 和 t 由英文字母组成
思路解答 滑动窗口法使用滑动窗口来解决这个问题。我们维护两个指针一个指向窗口的起始位置一个指向窗口的结束位置。移动右指针扩大窗口直到窗口包含了所有 t 中的字符。 满足条件时收缩窗口当窗口包含了所有 t 中的字符后我们尝试缩小窗口移动左指针并在移动过程中更新最小子串的长度和起始位置。 维护字符频次使用字典来维护 t 中字符的频次以及窗口中字符的频次确保窗口中包含了 t 中所有字符。
def minWindow(self, s: str, t: str) - str:if not s or not t:return t_freq collections.Counter(t)required_chars len(t_freq)left 0right 0formed 0window_freq {}ans float(inf), None, Nonewhile right len(s):char s[right]window_freq[char] window_freq.get(char, 0) 1if char in t_freq and window_freq[char] t_freq[char]:formed 1while formed required_chars and left right:if right - left 1 ans[0]:ans (right - left 1, left, right)char s[left]window_freq[char] - 1if char in t_freq and window_freq[char] t_freq[char]:formed - 1left 1right 1return if ans[0] float(inf) else s[ans[1]:ans[2] 1]
