当前位置: 首页 > news >正文

【力扣hot100】刷题笔记Day5

前言

  • 回学校了,荒废了半天之后打算奋发图强猛猛刷题,找实习!赚钱!!

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:r+1]if mp[s[l]] == 0:  # 如果是要匹配的字符就增加countcount += 1mp[s[l]] += 1  # 还回去l += 1  # 收缩边界return res

后言

  •  快两周没碰代码了,果然还是生疏了,得持续地码,脚踏实地是解决焦虑的最佳手段
http://www.lryc.cn/news/301495.html

相关文章:

  • 解锁Spring Boot中的设计模式—04.桥接模式:探索【桥接模式】的奥秘与应用实践!
  • [talib][python]ta-lib所有whl文件下载地址汇总
  • 【开源】JAVA+Vue.js实现农村物流配送系统
  • 锁相放大器,数字锁相放大器.C和python版的源代码
  • (02)Hive SQL编译成MapReduce任务的过程
  • 【C++初阶】值得一刷的字符串string相关oj题
  • 《Go 简易速速上手小册》第10章:微服务与云原生应用(2024 最新版)
  • 代码随想录算法训练营第34天| Leetcode 860.柠檬水找零、406.根据身高重建队列、452. 用最少数量的箭引爆气球
  • 数据结构~二叉树(基础知识)
  • AI大模型学习笔记之四:生成式人工智能(AIGC)是如何工作的?
  • bat脚本 创建计划任务 一分钟设置ntp同步周期为60s
  • python数据分析numpy基础之mean用法和示例
  • 微服务学习 | Springboot整合Dubbo+Nacos实现RPC调用
  • 只允许访问固定网址,如何让电脑只能上指定的网站
  • 作业帮 x TiDB丨多元化海量数据业务的支撑
  • 文生图提示词:天气条件
  • 【nginx实践连载-3】发布VSTO应用
  • 【前端工程化面试题】使用 webpack 来优化前端性能/ webpack的功能
  • 思迈特再获国家权威认证:代码自主率98.78%
  • JavaScript排序
  • 【读书笔记】ICS设备及应用攻击(一)
  • 网络原理(HTTP篇)
  • 关于油封密封件你了解多少?
  • Leetcode 72 编辑距离
  • 羊大师揭秘,如何挑选出好牧场的奶羊,该怎么看
  • MySQL数据库基础(八):DML数据操作语言
  • (09)Hive——CTE 公共表达式
  • Spring 用法学习总结(四)之 JdbcTemplate 连接数据库
  • 第 385 场 LeetCode 周赛题解
  • 什么是RabbitMQ?