刷题记录-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。

相关文章

Node.js学习记录（二）

Node.js学习记录（二）

目录 一、express 1、初识express 2、安装express 3、创建并启动web服务器 4、监听 GET&POST 请求、响应内容给客户端 5、获取URL中携带的查询参数 6、获取URL中动态参数 7、静态资源托管 二、工具nodemon 三、express路由 1、express中路由 2、路由的匹配 3、路由模块化 4、路由模块添加前缀 四、中间件
阅读更多...
记录每次更新到仓库 —— Git 学习笔记 10

记录每次更新到仓库 —— Git 学习笔记 10

记录每次更新到仓库 文章目录 文件的状态三个区域检查当前文件状态跟踪新文件取消跟踪（un-tracking）文件重新跟踪（re-tracking）文件暂存已修改文件忽略某些文件查看已暂存和未暂存的修改提交更新跳过暂存区删除文件移动文件参考资料 咱们接着很多天以前的 取得Git仓库 这篇文章继续说。 文件的状态 不管是通过哪种方法，现在我们已经有了一个仓库，并从这个仓
阅读更多...
学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一：循环解法二：递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1：（图一）输入：head = [1,1,2]输出：[1,2]示例 2：（图
阅读更多...
【每日刷题】Day113

【每日刷题】Day113

【每日刷题】Day113 🥕个人主页：开敲🍉 🔥所属专栏：每日刷题🍍 🌼文章目录🌼 1. 91. 解码方法 - 力扣（LeetCode） 2. LCR 098. 不同路径 - 力扣（LeetCode） 3. 63. 不同路径 II - 力扣（LeetCode） 1. 91. 解码方法 - 力扣（LeetCode） //思路：动态规划。 cl
阅读更多...
perl的学习记录——仿真regression

perl的学习记录——仿真regression

1 记录的背景 之前只知道有这个强大语言的存在，但一直侥幸自己应该不会用到它，所以一直没有开始学习。然而人生这么长，怎就确定自己不会用到呢？ 这次要搭建一个可以自动跑完所有case并且打印每个case的pass信息到指定的文件中。从而减轻手动跑仿真，手动查看log信息的重复无效低质量的操作。下面简单记录下自己的思路并贴出自己的代码，方便自己以后使用和修正。 2 思路整理 作为一个IC d
阅读更多...
SSM项目使用AOP技术进行日志记录

SSM项目使用AOP技术进行日志记录

本步骤只记录完成切面所需的必要代码 本人开发中遇到的问题： 切面一直切不进去，最后发现需要在springMVC的核心配置文件中中开启注解驱动才可以，只在spring的核心配置文件中开启是不会在web项目中生效的。 之后按照下面的代码进行配置，然后前端在访问controller层中的路径时即可观察到日志已经被正常记录到数据库，代码中有部分注释，看不懂的可以参照注释。接下来进入正题 1、导入m
阅读更多...
flume系列之：记录一次flume agent进程被异常oom kill -9的原因定位

flume系列之：记录一次flume agent进程被异常oom kill -9的原因定位

flume系列之：记录一次flume agent进程被异常oom kill -9的原因定位 一、背景二、定位问题三、解决方法 一、背景 flume系列之：定位flume没有关闭某个时间点生成的tmp文件的原因，并制定解决方案在博主上面这篇文章的基础上，在机器内存、cpu资源、flume agent资源都足够的情况下，flume agent又出现了tmp文件无法关闭的情况 二、
阅读更多...
【LeetCode热题100】前缀和

【LeetCode热题100】前缀和

这篇博客共记录了8道前缀和算法相关的题目，分别是：【模版】前缀和、【模版】二维前缀和、寻找数组的中心下标、除自身以外数组的乘积、和为K的子数组、和可被K整除的子数组、连续数组、矩阵区域和。 #include <iostream>#include <vector>using namespace std;int main() {//1. 读取数据int n = 0, q = 0;ci
阅读更多...
Linux常用工具与命令日常记录（长期更新）

Linux常用工具与命令日常记录（长期更新）

Linux常用工具与命令日常记录（长期更新） 目录 1.本地复制到远程2.Linux压缩拆包与解压3.生成随机密码4.ubuntu默认Python版本设置5.计算当前文件夹中文件数量6.windows中编写shell脚本，在Linux运行出错7.history 历史命令显示时间用户8.Ubuntu18.04设置源、网卡9.Ubuntu18.04设置网卡10.Ubuntu：自定义开
阅读更多...
Excel和Word日常使用记录：

Excel和Word日常使用记录：

Excel使用总结 表格颜色填充： 合并单元格： 选中你要合并的单元格区域。按下快捷键 Alt + H，然后松开这些键。再按下 M，接着按 C。这个组合键执行的操作是：Alt + H：打开“主页”选项卡。M：选择“合并单元格”选项。C：执行“合并并居中”操作。 插入行： 在Excel中，插入一行的快捷键是：Windows：选择整行（可以点击行号）。按下 Ctrl + Sh
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2