乐昌网站建设,wordpress 自动推送,长沙网站建设搭建,外包公司与劳务派遣区别前言
回学校了#xff0c;荒废了半天之后打算奋发图强猛猛刷题#xff0c;找实习#xff01;赚钱#xff01;#xff01;
560. 和为 K 的子数组 - 力扣#xff08;LeetCode#xff09; 前缀法 哈希表 这个题解解释比官方清晰#xff0c;截个图方便看#xff0c;另一…前言
回学校了荒废了半天之后打算奋发图强猛猛刷题找实习赚钱
560. 和为 K 的子数组 - 力扣LeetCode 前缀法 哈希表 这个题解解释比官方清晰截个图方便看另一个题解的代码简洁 class Solution:def subarraySum(self, nums: List[int], k: int) - int:prefixSumArray {0:1} # 初始化一个字典用于存储前缀和出现的次数初始时前缀和为0出现了1次count 0 # 初始化计数器prefixSum 0 # 初始化前缀和为0for 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来定义它# 如果某前缀不在此字典中那么它对应的次数为0num_times collections.defaultdict(int)num_times[0] 1 # 先给定一个初始值代表前缀和为0的出现了一次cur_sum 0 # 记录到当前位置的前缀和res 0for 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] 1return 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记录匹配相等完全匹配为0min_len lens 1 # 用于更新最小窗口长度l 0 # 左边界# 最小滑窗while里更新结果for r in range(lens):if mp[s[r]] 0:count - 1mp[s[r]] - 1 # 消耗掉# 如果完全匹配成功收缩左边界while count 0: if r - l min_len: # 如果窗口长度比之前的小就记录结果min_len r - l 1res s[l:r1]if mp[s[l]] 0: # 如果是要匹配的字符就增加countcount 1mp[s[l]] 1 # 还回去l 1 # 收缩边界return res
后言 快两周没碰代码了果然还是生疏了得持续地码脚踏实地是解决焦虑的最佳手段
