首页 知识库

目的：为了备战蓝桥杯（4 月 12 日）和夏令营预推免的机试。

每一题目标：彻底弄懂该题思路。

# 哈希表

简单：

LeetCode—— 罗马数字转整数：https://leetcode.cn/problems/roman-to-integer/?envType=problem-list-v2&envId=hash-table

LeetCode—— 多数元素：https://leetcode.cn/problems/majority-element/?envType=problem-list-v2&envId=hash-table

LeetCode—— 两数之和：1. 两数之和 - 力扣（LeetCode）

LeetCode—— 环形链表：141. 环形链表 - 力扣（LeetCode）

LeetCode—— 相交链表：160. 相交链表 - 力扣（LeetCode）

LeetCode—— 快乐数：202. 快乐数 - 力扣（LeetCode）

LeetCode—— 同构字符串：205. 同构字符串 - 力扣（LeetCode）

LeetCode—— 存在重复元素：217. 存在重复元素 - 力扣（LeetCode）

中等：

LeetCode—— 字母异位词分组：49. 字母异位词分组 - 力扣（LeetCode）🔥

LeetCode—— 最长连续序列：128. 最长连续序列 - 力扣（LeetCode）🔥

# 双指针

简单：

LeetCode—— 移动零（快慢指针）：283. 移动零 - 力扣（LeetCode）

LeetCode—— 删除有序数组中的重复项：26. 删除有序数组中的重复项 - 力扣（LeetCode）

LeetCode—— 移除元素：27. 移除元素 - 力扣（LeetCode）

LeetCode—— 找出字符串中第一个匹配项的下标：28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

LeetCode—— 合并两个有序数组（三指针）：https://leetcode.cn/problems/merge-sorted-array/?envType=problem-list-v2&envId=two-pointers 🔥

LeetCode—— 验证回文串（相向指针）：125. 验证回文串 - 力扣（LeetCode）🔥

LeetCode—— 回文链表（相向指针）：234. 回文链表 - 力扣（LeetCode）

LeetCode—— 反转字符串（优化相向指针）：344. 反转字符串 - 力扣（LeetCode）

LeetCode—— 反转字符串中的元音字母（双向指针）：345. 反转字符串中的元音字母 - 力扣（LeetCode）

中等：

LeetCode—— 盛最多水的容器（暴力必超时，相向指针）：11. 盛最多水的容器 - 力扣（LeetCode）🔥

LeetCode—— 三数之和（枚举与相向指针的结合）：15. 三数之和 - 力扣（LeetCode）🔥

# 滑动窗口

简单：

LeetCode—— 存在重复元素 II （暴力必超时，定长滑窗）：219. 存在重复元素 II - 力扣（LeetCode）

LeetCode—— 最长和谐子序列（变长滑窗）：594. 最长和谐子序列 - 力扣（LeetCode）

LeetCode—— 子数组最大平均数 I （定长滑窗）：643. 子数组最大平均数 I - 力扣（LeetCode）

LeetCode—— 拆炸弹（定长滑窗）：1652. 拆炸弹 - 力扣（LeetCode）🔥

LeetCode—— 找到一个数字的 K 美丽值（定长滑窗）：2269. 找到一个数字的 K 美丽值 - 力扣（LeetCode）🔥

LeetCode—— 每个字符最多出现两次的最长子字符串（变长滑窗）：https://leetcode.cn/problems/maximum-length-substring-with-two-occurrences/description/

中等：

LeetCode—— 定长子串中元音的最大数目（最佳定长滑窗入门题）：1456. 定长子串中元音的最大数目 - 力扣（LeetCode）

Summary

定长滑窗模板：
入 —— 更新 —— 出

  • 入：下标为 i 的元素进入窗口，更新相关统计量。如果 i<k−1 则重复第一步，目的是为了让窗口全部进入。窗口全部进入后，循环下标值 i==k-1，开始做更新的内容。
  • 更新：更新答案。一般是更新最大值 / 最小值。
  • 出：下标为 i−k+1 的尾部元素离开窗口，更新相关统计量。
class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        ans = vowel = 0
        for i, c in enumerate(s):
            # 1. 进入窗口
            if c in "aeiou":
                vowel += 1
            if i < k - 1:  # 窗口大小不足 k
                continue
            # 2. 更新答案
            ans = max(ans, vowel)
            # 3. 离开窗口
            if s[i - k + 1] in "aeiou":
                vowel -= 1
        return ans

LeetCode—— 无重复字符的最长子串（变长滑窗入门题）：3. 无重复字符的最长子串 - 力扣（LeetCode）

Summary

变长滑窗的核心思想是：维护一个有条件的滑动窗口。滑窗右端点右移的目的是为了扩大窗口，破坏条件。滑窗左侧端点左移的目的是为了维护这个条件，直至条件成立。下面是与哈希集合结合的滑窗去重模板（学习自灵茶山艾府）：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        table = set()
        left = maxValue = 0
        for right, c in enumerate(s):
            while c in table:
                table.remove(s[left])
                left += 1
            table.add(c)
            maxValue = max(maxValue, right - left + 1)
        return maxValue

变长滑窗需要额外的一个指针或者一个别的手段记录滑窗尾部位置。

LeetCode—— 重复的 DNA 序列：187. 重复的 DNA 序列 - 力扣（LeetCode）

LeetCode—— 长度最小的数组（变长滑窗）：209. 长度最小的子数组 - 力扣（LeetCode）🔥

LeetCode—— 大小为 K 且平均值大于等于阈值的子数组数目（定长滑窗练手题）：https://leetcode.cn/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold/description/

LeetCode—— 半径为 K 的子数组平均值（定长滑窗检验入门题）：https://leetcode.cn/problems/k-radius-subarray-averages/description/

LeetCode—— 删掉一个元素以后全为 1 的最长子数组（考验变长滑窗维护条件的选择）：https://leetcode.cn/problems/longest-subarray-of-1s-after-deleting-one-element/description/ 🔥

# 二分算法

简单：

LeetCode—— 搜索插入位置（闭区间二分查找）35. 搜索插入位置 - 力扣（LeetCode）

LeetCode—— 二分查找：704. 二分查找 - 力扣（LeetCode）

LeetCode—— 寻找比目标字母大的最小字母（左闭右开区间二分查找）：744. 寻找比目标字母大的最小字母 - 力扣（LeetCode）

LeetCode—— 正整数和负整数的最大计数（重用二分查找）：2529. 正整数和负整数的最大计数 - 力扣（LeetCode）

LeetCode—— 两个数组间的距离值（二分查找）：1385. 两个数组间的距离值 - 力扣（LeetCode） 🔥

中等：

LeetCode—— 在排序数组中查找元素的第一个和最后一个位置（二分查找入门题）：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

Summary

（学习自灵茶山艾府）

  • 闭区间二分查找模板：
class Solution:
    # lower_bound 返回最小的满足 nums [i] >= target 的下标 i
    # 如果数组为空，或者所有数都 < target，则返回 len (nums)
    # 要求 nums 是非递减的，即 nums [i] <= nums [i + 1]
    def lower_bound(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1  # 闭区间 [left, right]
        while left <= right:  # 区间不为空
            # 循环不变量：
            # nums[left-1] < target
            # nums[right+1] >= target
            mid = (left + right) // 2
            if nums[mid] >= target:
                right = mid - 1  # 范围缩小到 [left, mid-1]
            else:
                left = mid + 1  # 范围缩小到 [mid+1, right]
        # 循环结束后 left = right+1
        # 此时 nums [left-1] < target 而 nums [left] = nums [right+1] >= target
        # 所以 left 就是第一个 >= target 的元素下标
        return left
  • 开区间二分查找模板：
class Solution:
    # lower_bound 返回最小的满足 nums [i] >= target 的下标 i
    # 如果数组为空，或者所有数都 < target，则返回 len (nums)
    # 要求 nums 是非递减的，即 nums [i] <= nums [i + 1]
    def lower_bound(self, nums: List[int], target: int) -> int:
        left, right = -1, len(nums)  # 开区间 (left, right)
        while left + 1 < right:  # 区间不为空
            mid = (left + right) // 2
            # 循环不变量：
            # nums[left] < target
            # nums[right] >= target
            if nums[mid] >= target:
                right = mid  # 范围缩小到 (left, mid)
            else:
                left = mid  # 范围缩小到 (mid, right)
        # 循环结束后 left+1 = right
        # 此时 nums [left] < target 而 nums [right] >= target
        # 所以 right 就是第一个 >= target 的元素下标
        return right

LeetCode—— 咒语和药水的成功对数（二分查找）：2300. 咒语和药水的成功对数 - 力扣（LeetCode）

LeetCode—— 使结果不超过阈值的最小除数（二分答案求最小入门题）：https://leetcode.cn/problems/find-the-smallest-divisor-given-a-threshold/ 🔥

Summary

（学习自灵茶山艾府）

  • 当 a 和 b 都是正整数时，向上取整可以转换为向下取整，公式如下：

⌈ab⌉=⌊a+b−1b⌋=⌊a−1b⌋+1\lceil \frac{a}{b} \rceil = \lfloor \frac{a+b-1}{b} \rfloor = \lfloor \frac{a-1}{b} \rfloor + 1

  • 只要某个数满足的表达式是单调的，我们就能对这个数进行二分查找。
  • 因为 python 的 ceil 向上取整函数计算出的是浮点数，会有精度误差，因此尽可能转换为向下取整函数 floor。

LeetCode—— 完成旅途的最少时间（二分答案）：https://leetcode.cn/problems/minimum-time-to-complete-trips/ 🔥

# 栈

简单：

LeetCode—— 比较含退格的字符串（模拟栈）：844. 比较含退格的字符串 - 力扣（LeetCode）

LeetCode—— 棒球比赛（模拟栈）：682. 棒球比赛 - 力扣（LeetCode）

LeetCode—— 有效的括号：20. 有效的括号 - 力扣（LeetCode） 🔥

中等：

LeetCode—— 用栈操作构建数组（无脑题）：1441. 用栈操作构建数组 - 力扣（LeetCode）

LeetCode—— 从字符串中移除星号（秒杀题）：https://leetcode.cn/problems/removing-stars-from-a-string/

LeetCode—— 设计浏览器历史记录（用于检验入门的题）（指针与栈结合）：1472. 设计浏览器历史记录 - 力扣（LeetCode）

LeetCode—— 验证栈序列（双指针与栈结合）：946. 验证栈序列 - 力扣（LeetCode）

LeetCode—— 计算字符串的镜像分数：3412. 计算字符串的镜像分数 - 力扣（LeetCode）🔥

LeetCode—— 简化路径：https://leetcode.cn/problems/simplify-path/ 🔥

# 枚举

简单：

同一道题目也会反复出现，比如下面的两数之和出现于前面的哈希表。

LeetCode—— 两数之和（枚举右，维护左 + 哈希表）：https://leetcode.cn/problems/two-sum/description/

Summary

（学习自灵茶山艾府）
枚举右，维护左
双变量问题如：x+y==targetx+y==target 或者x−y==targetx-y==target。可以枚举右边的 y，找是否有x==target−yx==target-y 满足。通常与哈希表结合。

LeetCode—— 好数对的数目（枚举右，维护左 + 哈希表）：https://leetcode.cn/problems/number-of-good-pairs/description/

中等：
LeetCode—— 可互换矩形的组数（枚举右，维护左 + 哈希表）：https://leetcode.cn/problems/number-of-pairs-of-interchangeable-rectangles/description/

# 前缀和

简单：
LeetCode—— 区域和检索 —— 数组不可变（前缀和入门模板题）：https://leetcode.cn/problems/range-sum-query-immutable/

LeetCode—— 变长子数组求和：https://leetcode.cn/problems/sum-of-variable-length-subarrays/

中等：
LeetCode—— 统计范围内的元音字符串数 https://leetcode.cn/problems/count-vowel-strings-in-ranges/ 🔥

# 差分

简单：

中等；

# 队列

# 堆

# 二叉树

# 回溯

更新于 阅读次数 次

请我喝[茶]~(￣▽￣)~*

Runhua Deng 微信支付

微信支付

Runhua Deng alipay

alipay

Runhua Deng paypal

paypal