前言
- 回学校了,荒废了半天之后打算奋发图强猛猛刷题,找实习!赚钱!!
560. 和为 K 的子数组 - 力扣(LeetCode)
-
前缀法 + 哈希表
- 这个题解解释比官方清晰,截个图方便看,另一个题解的代码简洁
-
class Solution: def subarraySum(self, nums: List[int], k: int) -> int: prefixSumArray = {0:1} # 初始化一个字典,用于存储前缀和出现的次数,初始时前缀和为0出现了1次 count = 0 # 初始化计数器 prefixSum = 0 # 初始化前缀和为0 for ele in nums: # 遍历输入的nums列表 prefixSum += ele # 计算当前位置的前缀和 subArray = prefixSum - k # 计算符合条件的子数组和 if subArray in prefixSumArray: # 如果当前前缀和减去k的值在字典中 count += prefixSumArray[subArray] # 更新计数器,累加符合条件的子数组和的个数 ''' prefixSumArray.get(prefixSum, 0) 在hash table里查找key,如果有返回对应的value,反之返回0 ''' prefixSumArray[prefixSum] = prefixSumArray.get(prefixSum, 0) + 1 # 更新前缀和字典中前缀和出现的次数 return count # 返回符合条件的子数组和的个数
-
class Solution: def subarraySum(self, nums: List[int], k: int) -> int: # num_times 存储某“前缀和”出现的次数,这里用collections.defaultdict来定义它 # 如果某前缀不在此字典中,那么它对应的次数为0 num_times = collections.defaultdict(int) num_times[0] = 1 # 先给定一个初始值,代表前缀和为0的出现了一次 cur_sum = 0 # 记录到当前位置的前缀和 res = 0 for i in range(len(nums)): cur_sum += nums[i] # 计算当前前缀和 if cur_sum - k in num_times: # 如果前缀和减去目标值k所得到的值在字典中出现,即当前位置前缀和减去之前某一位的前缀和等于目标值 res += num_times[cur_sum - k] # 下面一句实际上对应两种情况,一种是某cur_sum之前出现过(直接在原来出现的次数上+1即可), # 另一种是某cur_sum没出现过(理论上应该设为1,但是因为此处用defaultdict存储,如果cur_sum这个key不存在将返回默认的int,也就是0) # 返回0加上1和直接将其置为1是一样的效果。所以这里统一用一句话包含上述两种情况 num_times[cur_sum] += 1 return res
239. 滑动窗口最大值 - 力扣(LeetCode)
-
单调队列
- 参考灵神的题解视频,单调队列的使用类似单调栈,复习一下C++实现
-
class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: ans = [] q = deque() # 双端队列 for i, x in enumerate(nums): # 1. 入 while q and nums[q[-1]] <= x: # 非空并且当前值大于队尾 q.pop() # 弹出队尾,维护 q 的单调递减性 q.append(i) # 入队,存下标 # 2. 出 if i - q[0] + 1 > k: # 队首已经离开窗口,弹出 q.popleft() # 3. 记录答案 if i >= k - 1: # 至少过了窗口大小再记录 # 由于队首到队尾单调递减,所以窗口最大值就是队首 ans.append(nums[q[0]]) return ans
76. 最小覆盖子串 - 力扣(LeetCode)
-
滑动窗口 + 哈希法
- 这题之前也解过,这次可以有更简洁的思路,只用一个mp即可
-
class Solution: def minWindow(self, s: str, t: str) -> str: mp = collections.defaultdict(int) # 避免不存在判空,默认0 # 将需要匹配的字符数存入哈希 for ch_t in t: mp[ch_t] += 1 lens, lent = len(s), len(t) count, res = lent, "" # count记录匹配相等,完全匹配为0 min_len = lens + 1 # 用于更新最小窗口长度 l = 0 # 左边界 # 最小滑窗,while里更新结果 for r in range(lens): if mp[s[r]] > 0: count -= 1 mp[s[r]] -= 1 # 消耗掉 # 如果完全匹配成功,收缩左边界 while count == 0: if r - l < min_len: # 如果窗口长度比之前的小就记录结果 min_len = r - l + 1 res = s[l:r+1] if mp[s[l]] == 0: # 如果是要匹配的字符就增加count count += 1 mp[s[l]] += 1 # 还回去 l += 1 # 收缩边界 return res
后言
- 快两周没碰代码了,果然还是生疏了,得持续地码,脚踏实地是解决焦虑的最佳手段
文章来源地址https://www.toymoban.com/news/detail-825856.html
文章来源:https://www.toymoban.com/news/detail-825856.html
到了这里,关于【力扣hot100】刷题笔记Day5的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!