笺札

3829. 共享出行配对系统 🎯 问题描述 描述： 设计一个共享出行平台的配对系统，需要支持乘客和司机的注册、匹配以及乘客取消订单的功能。 核心要求： addRider(riderId)：将乘客添加到等待队列 addDriver(driverId)：将司机添加到等待队列 matchDriverWithRider()：匹配最早等待的司机和乘客，返回配对结果 cancelRider(riderId)：允许乘客取消等待，从队列中移除 说明： 这是一个典型的队列与系统设计问题 核心策略：使用FIFO（先进先出）原则模拟真实的打车平台匹配机制 💻 解题思路 思路1：双队列模拟（基础解法） 核心逻辑 初始化： 使用两个独立的队列分别存储乘客和司机的等待队列 利用deque实现高效的队列操作 匹配机制： 只有当乘客和司机队列都非空时才能进行匹配 采用FIFO原则，匹配最早加入队列的用户 取消机制： 支持乘客从等待队列中取消订单 需要处理元素在队列中的查找和删除 代码实现 123456789101112131415161718192021222324...

2390. 从字符串中移除星号 🎯 问题描述 描述： 给你一个包含若干星号 * 的字符串 s。 s 中的操作如下： 选择 s 中一颗星号 *。 移除星号 * 左侧最近的那个非星号字符，并移除星号本身。 题目数据保证总会存在可执行的移除操作。 请返回执行完所有操作后的字符串。 说明： 这是一个典型的栈应用问题。 核心策略： 我们可以把普通字符看作是“入栈”操作。 把星号 * 看作是“出栈”操作（即删除最近加入的字符）。 遍历字符串，根据字符类型决定是添加还是删除。 示例： 示例 1： 12345678910输入：s = "leet**cod*e"输出："lecoe"解释：- 遇到 'l', 'e', 'e', 't' -> 栈: [l, e, e, t]- 遇到 '*' -> 删除 't' -> 栈: [l, e, e]- 遇到 '*' -> 删除...

3652. 按策略购买股票的最佳时机 🎯 问题描述 给你两个整数数组 prices 和 strategy，其中： prices[i] 表示第 i 天某股票的价格。 strategy[i] 表示第 i 天的交易策略，其中： -1 表示买入一单位股票。 0 表示持有股票。 1 表示卖出一单位股票。 同时给你一个 偶数 整数 k，你可以对 strategy 进行 最多一次 修改。一次修改包括： 选择 strategy 中恰好 k 个 连续 元素。 将前 k / 2 个元素设为 0（持有）。 将后 k / 2 个元素设为 1（卖出）。 利润 定义为所有天数中 strategy[i] * prices[i] 的 总和 。 返回你可以获得的 最大 可能利润。 说明： 这是一个滑动窗口结合前缀和的问题。 核心策略： 首先计算不修改任何操作时的基础总利润 base_profit。 利用滑动窗口枚举所有可能的长度为 k 的修改区间。 对于每个窗口，将其分为前半段（长度 k//2）和后半段。 计算“反转后半段操作”后的新收益，并与原收益对比，取最大值。 利用前缀和数组快...

682. 棒球比赛 🎯 问题描述 描述： 你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。 比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 operations，其中 operations[i] 是你需要记录的第 i 项操作，遵循下述规则： 整数 x：表示本回合新获得分数 x。 “+”：表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。 “D”：表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。 “C”：表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。 请你返回记录中所有得分的总和。 说明： 这是一个典型的栈应用问题。 核心策略： 我们需要维护一个记录所有有效得分的列表（栈）。 对于每种操作，根据栈顶（最近一次得分）或次栈顶（倒数第二次得分）的元素进行计算或修改。 最后对栈中所有元素求和。 示例： 示例 1： 123456789输入：ops = ...

844. 比较含退格的字符串 🎯 问题描述 描述： 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true。# 代表退格字符。 注意：如果对空文本输入退格字符，文本继续为空。 说明： 这是一个典型的栈应用问题。 核心策略： 我们需要模拟字符串的输入过程。 遇到普通字符时，将其“输入”（入栈）。 遇到 # 字符时，执行“退格”（出栈），前提是栈不为空。 最后比较两个字符串处理后的结果。 示例： 示例 1： 123456输入：s = "ab#c", t = "ad#c"输出：true解释：- s 变为 "ac" ('b' 被退格删除)- t 变为 "ac" ('d' 被退格删除)- 两者相等。 示例 2： 123456输入：s = "ab##", t = "c#d#"输出：true解释：- s 变为 "" ('b'...

1441. 用栈操作构建数组 🎯 问题描述 描述： 给你一个数组 target 和一个整数 n。每次迭代，需要从列表 list = {1, 2, 3, ..., n} 中依序读取一个数字。 请使用下述操作来构建目标数组 target： “Push”：从 list 中读取一个新元素，并将其推入数组中。 “Pop”：删除数组中的最后一个元素。 如果目标数组构建完成，就停止读取更多元素。题目数据保证目标数组严格递增。请返回构建目标数组所用的操作序列。 说明： 这是一个模拟类问题。 核心策略： 我们需要按顺序遍历 1 到 n 的数字。 对于每个数字 i，它要么是我们需要的（存在于 target 中），要么是不需要的。 如果是需要的，执行 “Push”。 如果是不需要的，执行 “Push” 紧接着执行 “Pop”（相当于读取后丢弃）。 一旦 target 构建完成，立即停止。 示例： 示例 1： 1234567输入：target = [1,3], n = 3输出：["Push","Push",&q...

图 (Graph) 基本概念 图：由顶点集合 V 和边集合 E 组成的非线性数据结构，记作 G = (V, E)。 无向图 / 有向图：边是否有方向。 度：无向图中与顶点相连的边数；有向图中分入度 (In-degree) 和出度 (Out-degree)。 路径：顶点序列 v1, v2, …, vk，其中相邻顶点间有边。 连通图 / 强连通图：任意两顶点间存在路径。 带权图 (网)：边带有权值 (Weight)。 完全图：每对不同顶点间均有边相连。 数据结构的三要素 逻辑结构 多对多关系：顶点之间通过边建立任意连接。 存储结构 邻接矩阵：二维数组 matrix[i][j] 表示顶点 i 到 j 的边（及权值）。 邻接表：数组索引对应顶点，每个元素为链表/列表，存储相邻顶点。 十字链表 (有向图) / 邻接多重表 (无向图)：优化特定场景的存储。 数据的运算 创建图、添加/删除顶点和边。 遍历：深度优先搜索 (DFS)、广度优先搜索 (BFS)。 路径计算：最短路径、最小生成树、拓扑排序等。 费曼理解 图就像一个城市的地铁路线图。车站是顶点，铁轨...

埃拉托斯特尼筛法 基本概念 核心定义：一种用于找出小于等于给定整数N的所有质数的古老算法。 核心思想：“排除法”。与其逐个判断每个数是不是质数，不如反过来：从 2 开始，把每一个质数的倍数全部标记为“合数（非质数）”。剩下的未被标记的数就是质数。 数据结构：通常使用一个布尔数组（Boolean Array）来维护状态。数组索引代表数字本身，值代表该数字是否为质数（True/False）。 费曼理解 (Feynman Technique) 用最简单的语言解释给“小白”听： 想象操场上有编号 2 到 100 的 100 个学生，他们都默认站着（代表是质数）。 第一步：老师喊 2（最小的质数）。2 说：“凡是能被 2 整除的同学（4, 6, 8…），请坐下（排除）。” 第二步：老师喊下一个还站着的同学 3。3 说：“凡是能被 3 整除的同学（6, 9, 12…），请坐下。” 重复：老师继续找下一个还站着的同学（5, 7…），直到检查完 100100​ （即 10）为止。 最后：操场上还站着的同学，他们的编号就是质数。 3. 内部实现：核心代码逻辑 123456789...

动态规划 1. 基本概念 核心定义：动态规划（Dynamic Programming, DP）是一种通过将复杂问题分解为重叠子问题来求解最优化问题的算法策略。 核心思想：“记住过去，指导未来”。 与其每次都重新计算相同的问题，不如把结果存起来（备忘录），下次直接查表。 利用状态转移方程，从小规模问题的解推导出大规模问题的解。 三大要素： 最优子结构：大问题的最优解包含子问题的最优解（比如：去终点的最短路径，一定经过去中途某点的最短路径）。 重叠子问题：在递归求解时，相同的子问题被反复计算（这是使用DP的前提）。 状态转移方程：描述状态之间如何转化的数学公式（如 dp[i]=dp[i−1]+dp[i−2]dp[i] = dp[i-1] + dp[i-2]dp[i]=dp[i−1]+dp[i−2]）。 2. 费曼理解 用最简单的语言解释给“小白”听： 想象你在爬楼梯，每次只能爬 1 级或 2 级。你想知道爬到第 10 级有多少种方法。 普通递归（傻算）： 你站在第 10 级，想：“我要么从第 9 级上来，要么从第 8 级上来”。于是你跑去算第 9 级，算第...

记忆化搜索 1. 基本概念 核心定义：记忆化搜索是一种自顶向下的算法优化技术。它在递归的基础上，增加了一个“备忘录”（通常是哈希表或数组），用来记录已经计算过的子问题的结果。 核心思想：“拒绝重复劳动”。 当你第一次遇到某个子问题时，正常计算，并把结果记在小本本上。 当你再次遇到相同的子问题时，直接查小本本，不再重复计算。 本质：它是动态规划的一种实现形式（另一种是自底向上的迭代法）。它保留了递归的代码逻辑，但拥有了动态规划的时间效率。 2. 费曼理解 用最简单的语言解释给“小白”听： 想象你在做一本超厚的数学练习册（递归问题），题目之间有依赖关系。 普通递归（傻算）： 你做到第 10 题，发现需要第 5 题的答案，于是翻回去算第 5 题。 做完第 10 题，你做第 12 题，发现又需要第 5 题的答案。于是你又翻回去，重新算了一遍第 5 题！ 这就叫“重复计算”，效率极低。 记忆化搜索（聪明人）： 你在桌子旁放了一个草稿本（Memo）。 当你第一次算出第 5 题的答案是 100 时，你把它记在草稿本上：“第 5 题 = 100”。 当你做第 12 题又...