Leetcode 中的 hot100 记录

  1. 两数之和 哈希表,记录值和索引之间的关系即可
  2. 字母异位单次分组 哈希表用于分组,这里可以把字符串排序之后的值得作为 key , 字符串本身作为 value
  3. 最长连续子序列 利用 unordered_set 进行去重操作,当序列中不存在这一个数字的前面一个数字的时候就说明不是开头跳过,否则就说明是开头一次往后面找看可以找到那里
  • 总结:
    • unordered_map 用于统计,以及寻找相同的关系进行元素的统一,重点是找到元素的统一特点
    • unordered_set 用于去除重复,或者进行单个元素的搜索
  1. 移动零 双指针,slow指向的都是已经满足条件的位置,fast指针用于搜索元素,当遇到非0元素就可以交换到前面即可
  2. 盛装最大水的容器 一个指针从前面开始一个指针从后面开始,对应的长度小的一个指针进行移动即可,并且在移动的过程中记录最大的容量即可
  3. 三数之和 三指针法,首先第一个指针用于确定起点,之后的两个指针一个前一个后并且进行类似于二分查找的操作即可,特别注意减枝操作和去重操作
  4. 接雨水 经典hard,还是利用单调栈的方法,在遍历的过程中找到右边第一个大于该元素的元素,注意最后考虑三个元素,中间的一个元素就是装水的元素 , result += (min(height[st.top()] , height[st.top()]) - height[mid]) * (i - st.top() - 1)
  • 总结:
    • 双指针的类型:
      • 快慢指针
      • 首尾指针(类似于二分查找)
    • 注意边界的控制

  1. 最长的无重复字符的字符串长度 字符串作为滑动窗口即可,注意最后一个元素需要加入到滑动窗口中,另外注意滑动窗口的加入 元素和删除与删除元素的规则

  2. 字符串中的所有异位词 定长滑动窗口 or 非定长滑动窗口, 注意异位词的最快的方法就是使用哈希表,所以这里也是一样,注意哈希表在使用的过程中加入元素可以抽象为: count[s[right] - 'a'] -- , 取出元素可以抽象为: count[s[right] - 'a'] ++

  3. 和为K的子数组 前缀和经典题目,参考 前缀和

  4. 滑动窗口最大值 单调队列,每一次加入元素需要弹出所有小于这一个元素的所有元素,并且注意弹出元素的时候判断最大元素是否是需要弹出的元素即可,可以参考: 栈与队列

  5. 最小覆盖子串 滑动窗口的经典题目,注意滑动窗口中的元素要求的时候就需要移动滑动窗口的指针使得要求被破坏从而使得滑动窗口的指针移动可以继续执行,之后会总结滑动窗口的所有题目类型 参考: 滑动窗口

  6. 最大子数组和 可以用 dp , dp[i] 表示数组中以 i 结尾的序列的元素最大值, 也可以使用贪心算法

  7. 合并区间 按照左端点排序,压入第一个元素,之后不断比较当前遍历道德元素和数组中最后一个元素的结尾位置,如果小于结尾位置,那么就可以更新结尾位置了,参考 贪心算法

  8. 轮转数组 反转整个数组,反转前K个元素,反转后面的nums.size() - K个元素

  9. 除自身以外数组的乘积 凡是和数组元素相关的问题都需要可以使用前缀表和后缀表来做,这里的前缀表和后缀表的定义和作用如下: $$ prefix[i] = nums[0] * nums[1] * ... * nums[i - 1] $$ $$ suffix[i] = nums[i + 1] * nums[i + 2] * ... * nums[n - 1] $$ 所以最终的答案数组为: $$ answer[i] = prefix[i] * suffix[i] $$

  10. 缺失的第一个正数 非常新颖的一个题目,注意到查找元素需要使用哈希表,但是这里使用哈希表就会让空间复杂度变成O(n) ,所以这里可以把数组本身当成哈希表,如果数组长度为 N , 那么如果之需要判断数组中是否出现 1 - N 即可,如果都出现了答案就是 N + 1 ,否则就是没有出现的元素,这里的策略就是,所有非正数变成 N + 1,另外的正数假设为 i 就可以标记 nums[i + 1]为负数即可,找到第一个正数下标增加一即可 Pasted image 20250115095202.png 18 - 21. 参考 矩阵操作 22 - 35. 参考 链表

  11. 二叉树的中序遍历 参考二叉树的统一迭代法(使用通用的模板即可)