刷题记录-HOT 100（一）40道

2024-09-02 06:52
文章标签 记录 100 刷题 40 hot

本文主要是介绍刷题记录-HOT 100（一）40道，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

记录题解和思路。

一、哈希表解决问题

1、两数之和

思路：

  • 创建哈希表： 初始化了一个空字典来存储已经访问过的数字及其对应的索引。

  • 遍历数组： 逐一遍历数组中的每个元素。在遍历过程中，针对每个元素 num，计算出它需要的配对数，即 target - num。

  • 查找配对： 检查哈希表中是否存在这个配对数。如果存在，说明找到了目标数对，此时返回这两个数的索引（即哈希表中存储的索引和当前数的索引）。

  • 更新哈希表： 如果没有找到对应的配对数，将当前数 num 和它的索引存入哈希表中，以备后续查找使用。

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:hashtable=dict()for i,num in enumerate(nums):if target-num in hashtable:return [hashtable[target-num],i]hashtable[num]=ireturn []

时空复杂度都是O(n) 。

enumerate 是 Python 内置的一个非常有用的函数，它用于在遍历可迭代对象（如列表、元组或字符串）时，同时获取元素的索引和值。

enumerate(iterable, start=0)

2、字母异位词分组

思路：

字母异位词是由相同字符组成的不同排列形式。我们可以利用这一特性，通过对每个字符串的字符进行计数，将相同字符组成的字符串归到同一组中。

  • 初始化字典：首先，我们需要一个字典来存储分组的结果，键为字符计数的元组，值为对应字母异位词的列表。
  • 遍历字符串列表：对于每个字符串，创建一个长度为 26 的数组，用于记录每个字母的出现次数。
  • 更新计数并存储：根据字符串中的字符更新计数数组，然后将计数数组转换为元组作为字典的键，将字符串添加到相应的字典列表中。
  • 返回结果：最后，我们从字典中提取所有的值（即所有字母异位词的分组），并返回这些分组作为结果。
class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:mp = collections.defaultdict(list)for st in strs:counts = [0] * 26for ch in st:counts[ord(ch) - ord("a")] += 1# 需要将 list 转换成 tuple 才能进行哈希mp[tuple(counts)].append(st)return list(mp.values())

时空复杂度为O(nk)，n是字符串个数，k是字符串的平均长度。 

3、最长连续序列

可以利用集合（set）的特性高效地判断某个数字是否存在。具体而言，对于每个数字，如果它的前驱（即该数字减去 1）不存在，那么这个数字可能是某个连续序列的起点。我们通过迭代来寻找最长的连续序列。

  1. 初始化变量：首先，初始化一个变量 longest_streak 用来记录最长的连续序列长度，同时将输入的数组转换为集合 num_set 以便快速查找。
  2. 遍历集合：遍历集合中的每一个数字 num。如果 num-1 不在集合中，说明 num 是某个连续序列的起点。
  3. 查找连续序列：从起点开始，查找该数字的下一个连续数字（即 num+1、num+2 等），直到找不到为止。记录当前序列的长度。
  4. 更新最长序列长度：将当前序列的长度与 longest_streak 进行比较，如果当前序列更长，则更新 longest_streak。
  5. 返回结果：最后返回 longest_streak 作为最长的连续序列长度。
class Solution:def longestConsecutive(self, nums: List[int]) -> int:longest_streak = 0num_set = set(nums)for num in num_set:if num - 1 not in num_set:current_num = numcurrent_streak = 1while current_num + 1 in num_set:current_num += 1current_streak += 1longest_streak = max(longest_streak, current_streak)return longest_streak

时空复杂度为O(n)。 

二、双指针

1、移动零

一个指针遍历数组，另一个指针记录非零元素应该放置的位置。

  • 初始化指针：我们初始化两个指针 left 和 right。left 用于跟踪下一个非零元素应该放置的位置，而 right 用于遍历数组中的每个元素。
  • 遍历数组：right 指针从数组的第一个元素开始，遍历整个数组。
  • 交换元素：如果 right 指针指向的元素不是 0，那么我们将该元素与 left 指针指向的位置交换，同时将 left 指针右移一位。right 指针无论如何都会继续右移。
  • 完成移动：遍历完成后，所有非零元素都被移动到数组的前面，剩下的位置自动填充为 0（因为未被覆盖的元素自然就是 0）。
class Solution:def moveZeroes(self, nums: List[int]) -> None:n = len(nums)left = right = 0while right < n:if nums[right] != 0:nums[left], nums[right] = nums[right], nums[left]left += 1right += 1

时间复杂度是O(n)，空间复杂度是O(1)。

2、盛最多水的容器

通过双指针的方法来解决这一问题：指针 l 从数组左端开始，指针 r 从数组右端开始，通过计算两个指针间形成的矩形面积来找到最大容积。每次根据两边柱子高度的比较移动指针，以期找到可能更大的容积。

  • 初始化指针和结果变量：我们初始化两个指针，l 指向数组的左端，r 指向数组的右端。同时，初始化 ans 变量用于记录当前找到的最大容积。
  • 遍历数组：在 l < r 的条件下，计算 l 和 r 指向的柱子形成的容积。使用较小的柱子高度乘以指针间的距离来计算面积。
  • 更新最大容积：如果当前计算的面积大于已记录的最大容积，则更新 ans。
  • 移动指针：移动指针的方法是：总是移动高度较小的那一端的指针，原因是希望通过增大或减小指针位置来找到可能的更大容积。
  • 返回结果：循环结束后，返回 ans，即最大容积。
class Solution:def maxArea(self, height: List[int]) -> int:l, r = 0, len(height) - 1ans = 0while l < r:area = min(height[l], height[r]) * (r - l)ans = max(ans, area)if height[l] <= height[r]:l += 1else:r -= 1return ans

时间复杂度是O(n)，空间复杂度是O(1)。

3、三数之和

我们首先对数组进行排序，然后通过固定一个元素，再在剩下的部分中使用双指针寻找符合条件的另外两个元素，从而找到所有满足条件的三元组。 

  • 排序数组：首先对数组进行排序，这样可以方便地避免重复的组合，并且可以通过双指针技巧有效地搜索剩余的两个数。
  • 遍历数组，固定第一个数：使用一个循环来固定第一个数 a，对于每一个固定的数，我们希望找到另外两个数 b 和 c，使得 a + b + c = 0。
  • 避免重复元素：在遍历过程中，如果当前的数与前一个数相同，我们可以跳过它以避免重复的三元组。
  • 使用双指针搜索剩余的两个数：固定 a 后，我们使用双指针的方法在剩下的部分寻找 b 和 c。其中，一个指针从左侧开始，另一个指针从右侧开始，并根据三者的和来调整指针的位置。
  • 避免重复结果：在找到一个符合条件的三元组后，移动指针时跳过重复的元素，确保结果中没有重复的三元组。
  • 返回结果：最后将所有找到的三元组返回。
class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:n = len(nums)nums.sort()ans = list()# 枚举 afor first in range(n):# 需要和上一次枚举的数不相同if first > 0 and nums[first] == nums[first - 1]:continue# c 对应的指针初始指向数组的最右端third = n - 1target = -nums[first]# 枚举 bfor second in range(first + 1, n):# 需要和上一次枚举的数不相同if second > first + 1 and nums[second] == nums[second - 1]:continue# 需要保证 b 的指针在 c 的指针的左侧while second < third and nums[second] + nums[third] > target:third -= 1# 如果指针重合，随着 b 后续的增加# 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环if second == third:breakif nums[second] + nums[third] == target:ans.append([nums[first], nums[second], nums[third]])return ans

时间复杂度是O(N²)，空间复杂度是O(logN)

4、接雨水

整体思路

接雨水问题的核心在于计算每个位置上方可以存储的水量。对于每个位置，能够存储的水量取决于它左边和右边最高柱子的较小值减去当前位置的高度。

参考：【盛最多水的容器 接雨水】https://www.bilibili.com/video/BV1Qg411q7ia?vd_source=b93b9c2a7846dd3e8bd33feb227c4ac5

思路1

为了快速计算每个位置的左侧最大高度和右侧最大高度，可以分别构建前缀最大值数组和后缀最大值数组。然后遍历每个位置，利用这两个数组计算水量并累加。

  • 构建前缀最大值数组：prefix[i] 表示从左到右扫描数组时，位置 i 及其左侧的最大高度。
  • 构建后缀最大值数组：suffix[i] 表示从右到左扫描数组时，位置 i 及其右侧的最大高度。
  • 计算总水量：对于每个位置，利用 prefix 和 suffix 数组中的值，计算当前位置可以存储的水量并累加。

第i个柱子能存储的水量取决于它左侧柱子的最大高度和右侧柱子的最大高度中的较小值。要在当前位置存储水量，必须形成两侧高中间低的“低洼”形态。根据“短板效应”，存水量取决于两侧高度中较低的那一侧。

以图中粉线框柱的部分举例，柱子的高度为1，它左侧高度最大值为2，右侧高度最大值是3，此时形成了一个低洼。接下来考虑水量存储，如果存水高度高于了左侧最高点，那么水会从左侧溢出，因此限制存水量的就是现在左侧的最高点2，所以当前位置的存水量是2-1=1。

因此，用公式表达第i个位置的存水量为：min(leftmax,rightmax)-height[i]，按照这个思路就可以得到以下代码：

class Solution:def trap(self, height: List[int]) -> int:ans=0;n=len(height)prefix=[0]*n;prefix[0]=height[0]suffix=[0]*n;suffix[-1]=height[-1]for i in range(1,n):prefix[i]=max(prefix[i-1],height[i])for i in range(n-2,-1,-1):suffix[i]=max(suffix[i+1],height[i])for h,pre,suf in zip(height,prefix,suffix):ans+=min(pre,suf)-hreturn ans

时间复杂度和空间复杂度都是O(n)。 

思路2

  • 初始化变量：我们需要两个指针 left 和 right，分别指向数组的左右两端。此外，还需要两个变量 leftMax 和 rightMax，用于记录当前左边和右边的最大高度。ans 变量用于累计雨水总量。
  • 遍历数组：在 left 指针小于 right 指针的情况下，逐步遍历数组。
  • 更新左右最大高度：对于每个位置，我们更新 leftMax 和 rightMax，分别表示当前左侧和右侧的最大高度。
  • 计算雨水量：如果 height[left] 小于 height[right]，说明左侧的最大高度决定了当前能存储的雨水量，雨水量为 leftMax - height[left]，然后左指针右移。否则，右侧的最大高度决定当前能存储的雨水量，雨水量为 rightMax - height[right]，然后右指针左移。
  • 返回结果：循环结束后，ans 中存储了整个柱子之间可以储存的总雨水量，返回该值。

利用双指针，从左向右和从右向左两个方向遍历数组。维护两个变量指示左右两侧最大高度，一个是leftmax用来指示当前left指针所指位置及其左侧的最高高度，一个是rightmax用来指示当前right指针所指位置及其右侧的最高高度。

在Left小于right的情况下遍历数组，如果height[left]<height[right]就说明左侧更低，leftmax限制left所指位置的最大盛水量【height[left]<height[right]<=rightmax，所以水肯定不会从left所指位置的右边流出去，右边高，限制最大盛水量的是低的那侧。】

class Solution:def trap(self, height: List[int]) -> int:ans=0;n=len(height)left,right=0,n-1leftmax,rightmax=0,0while left<right:leftmax=max(leftmax,height[left])rightmax=max(rightmax,height[right])if height[left]<height[right]:ans+=leftmax-height[left]left+=1else:ans+=rightmax-height[right]right-=1return ans

三、滑动窗口

1、无重复字符的最长子串

使用滑动窗口，滑动窗口通过两个指针来动态维护一个子串，保证子串内的字符没有重复。在遍历过程中，动态调整窗口的大小，并记录最长的无重复子串长度。

  • 初始化：使用一个字典 char 来记录当前窗口内每个字符的出现次数。两个指针 left 和 right 分别指向窗口的左边界和右边界。res 记录最长无重复子串的长度。

  • 扩展窗口：右指针 right 向右移动，将新字符加入窗口，并更新其在字典中的计数。

  • 收缩窗口：如果加入的字符在窗口中出现次数超过一次，说明有重复字符。通过移动左指针 left 来收缩窗口，直到窗口内没有重复字符。

  • 更新结果：每次调整窗口后，计算当前窗口的长度，并更新 res，确保它始终记录最大长度。

  • 继续扩展：移动右指针，继续扩展窗口，直到遍历完整个字符串。

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:char=collections.defaultdict(int)n=len(s);res=0left,right=0,0while right<n:char[s[right]]+=1while left<n and char[s[right]]>1:char[s[left]]-=1left+=1res=max(res,right-left+1)right+=1return res

注：滑动窗口问题模板

//外层循环扩展右边界，内层循环扩展左边界
for (int l = 0, r = 0 ; r < n ; r++) {//当前考虑的元素while (l <= r && check()) {//区间[left,right]不符合题意//扩展左边界}//区间[left,right]符合题意，统计相关信息
}

2、找到字符串中所有字母异位词

通过滑动窗口，我们可以将 p 的长度作为窗口的大小，在 s 上滑动窗口，逐步检查当前窗口是否为 p 的异位词。

不用设置left了，因为窗口大小是固定的，只移动一个指针就可以了。

class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:n, m = len(s), len(p)cntp = Counter(p)cnts = Counter()ans = []for i, x in enumerate(s):cnts[x]+=1if i+1>=m:if cntp == cnts:ans.append(i+1-m)cnts[s[i+1-m]]-=1return ans

时间复杂度：O(n+m+Σ)，其中 n 为字符串 s 的长度，m 为字符串 p 的长度，其中Σ 为所有可能的字符数。空间复杂度：O(Σ)。用于存储滑动窗口和字符串 p 中每种字母数量的差。

三、子串

1、和为k的子数组

整体思路是利用了前缀和，求和为k的连续子数组。如果我们知道了两个前缀和 prefix[j] 和 prefix[i]，并且 prefix[j]-prefix[i]==k，那么说明从 i + 1 到 j 之间的子数组的和为 k。

  • 初始化：

    • pre：用于记录当前的前缀和，即从数组起始位置到当前元素的累加和。
    • count：用于记录和为 k 的子数组的数量。
    • mp：一个 defaultdict（默认值为 0），用于记录前缀和出现的次数。初始时，mp[0] = 1，这是为了处理从数组起始位置开始的子数组情况。

  • 遍历数组：

    • 对于数组中的每个元素 num，更新前缀和 pre。
    • 检查 pre - k 是否存在于哈希表 mp 中。如果存在，说明从之前某个位置到当前元素的子数组和为 k，因此累加 mp[pre - k] 到 count 中。【因为数组中的元素并非都是正值，因此可能有多个位置的前缀和相同】
    • 最后，将当前前缀和 pre 的出现次数记录在哈希表 mp 中，以便后续使用。

  • 返回结果：

    • 最后，返回 count，即满足条件的子数组数量。
class Solution:def subarraySum(self, nums: List[int], k: int) -> int:pre=0;count=0mp=collections.defaultdict(int)mp[0]=1for num in nums:pre+=numif pre-k in mp:count+=mp[pre-k]mp[pre]+=1return count

2、滑动窗口内找最大值

  • 使用 deque 来存储当前窗口中的元素索引，deque 中的元素按它们在 nums 中对应值的大小递减排列，确保 deque 的头部始终是当前窗口的最大值。
  • 随着窗口的滑动，你移除已经不在当前窗口中的索引，并添加新的索引，始终保持 deque 中的元素有效并且顺序正确。
class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:n=len(nums);ans=[]q=collections.deque()i=0while i<len(nums):if q and q[0]<i-k+1:q.popleft()while q and nums[q[-1]]<=nums[i]:q.pop()q.append(i)if i-k+1>=0:ans.append(nums[q[0]])i+=1return ans

这篇关于刷题记录-HOT 100（一）40道的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1129304。

相关文章

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

Spring Boot 配置文件之类型、加载顺序与最佳实践记录

《SpringBoot配置文件之类型、加载顺序与最佳实践记录》SpringBoot的配置文件是灵活且强大的工具,通过合理的配置管理,可以让应用开发和部署更加高效,无论是简单的属性配置,还是复杂... 目录Spring Boot 配置文件详解一、Spring Boot 配置文件类型1.1 applicatio
阅读更多...
MySQL INSERT语句实现当记录不存在时插入的几种方法

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面：本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE
阅读更多...
Python 中的异步与同步深度解析(实践记录)

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步：深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步
阅读更多...
Python Dash框架在数据可视化仪表板中的应用与实践记录

Python Dash框架在数据可视化仪表板中的应用与实践记录

《PythonDash框架在数据可视化仪表板中的应用与实践记录》Python的PlotlyDash库提供了一种简便且强大的方式来构建和展示互动式数据仪表板,本篇文章将深入探讨如何使用Dash设计一... 目录python Dash框架在数据可视化仪表板中的应用与实践1. 什么是Plotly Dash？1.1
阅读更多...
Spring Boot中定时任务Cron表达式的终极指南最佳实践记录

Spring Boot中定时任务Cron表达式的终极指南最佳实践记录

《SpringBoot中定时任务Cron表达式的终极指南最佳实践记录》本文详细介绍了SpringBoot中定时任务的实现方法,特别是Cron表达式的使用技巧和高级用法,从基础语法到复杂场景,从快速启... 目录一、Cron表达式基础1.1 Cron表达式结构1.2 核心语法规则二、Spring Boot中定
阅读更多...
国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)

国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)

《国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)》本文给大家利用deepseek模型搭建私有知识问答库的详细步骤和遇到的问题及解决办法,感兴趣的朋友一起看看吧... 目录1. 第1步大家在安装完ollama后，需要到系统环境变量中添加两个变量2. 第3步 “在cmd中
阅读更多...
Spring Retry 实现乐观锁重试实践记录

Spring Retry 实现乐观锁重试实践记录

《SpringRetry实现乐观锁重试实践记录》本文介绍了在秒杀商品SKU表中使用乐观锁和MybatisPlus配置乐观锁的方法,并分析了测试环境和生产环境的隔离级别对乐观锁的影响,通过简单验证,... 目录一、场景分析 二、简单验证 2.1、可重复读 2.2、读已提交 三、最佳实践 3.1、配置重试模板
阅读更多...
在 Spring Boot 中使用异步线程时的 HttpServletRequest 复用问题记录

在 Spring Boot 中使用异步线程时的 HttpServletRequest 复用问题记录

《在SpringBoot中使用异步线程时的HttpServletRequest复用问题记录》文章讨论了在SpringBoot中使用异步线程时,由于HttpServletRequest复用导致... 目录一、问题描述：异步线程操作导致请求复用时 Cookie 解析失败1. 场景背景2. 问题根源二、问题详细分
阅读更多...
关于Spring @Bean 相同加载顺序不同结果不同的问题记录

关于Spring @Bean 相同加载顺序不同结果不同的问题记录

《关于Spring@Bean相同加载顺序不同结果不同的问题记录》本文主要探讨了在Spring5.1.3.RELEASE版本下,当有两个全注解类定义相同类型的Bean时,由于加载顺序不同,最终生成的... 目录问题说明测试输出1测试输出2@Bean注解的BeanDefiChina编程nition加入时机总结问题说明
阅读更多...
将sqlserver数据迁移到mysql的详细步骤记录

将sqlserver数据迁移到mysql的详细步骤记录

《将sqlserver数据迁移到mysql的详细步骤记录》：本文主要介绍将SQLServer数据迁移到MySQL的步骤,包括导出数据、转换数据格式和导入数据,通过示例和工具说明,帮助大家顺利完成... 目录前言一、导出SQL Server 数据二、转换数据格式为mysql兼容格式三、导入数据到MySQL数据
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2