生题本

记录第一次接触的新题型，掌握后移到正式笔记。

[HackerRank] 20. Ways to Fill Slots with Single or Double Coverage

• 题型：动态规划（爬楼梯变体）
• 第一次接触 DP，核心学到的：四步推导法（定义状态 → 最后一步什么选择 → 转移方程 → 边界）
• 转移方程：dp[n] = dp[n-1] + dp[n-2]
• BigInt 处理大数

[HackerRank] 21. Count Connected Components in Network

• 题型：图论 / DFS
• 第一次接触图论，核心学到的：邻接表建图、DFS 遍历连通块、visited 标记
• 模板：建 adj → DFS 函数 → 遍历所有节点数未访问的
• 基础模板题，掌握后图论题都在这个骨架上加东西

[HackerRank] 24. Detect Cycle in Module Dependency Graph

• 题型：图论 / DFS / 环检测
• 第一次接触环检测，核心学到的：三色标记法（白=未访问、灰=访问中、黑=已完成）
• 灰色节点表示在当前递归路径上还没走完，遇到灰色 = 环
• 有向图建邻接表只加一次，和第 21 题无向图加两次不同
• 踩坑：黑色节点要 continue 不是 return；DFS 结束要标黑

[HackerRank] 26. Longest Arithmetic Subsequence with Given Difference

• 题型：动态规划 + 哈希表
• 第一次遇到”没有选择的 DP”，理解到：识别 DP 的真正信号是”有没有重复计算”，不是”有没有选择”
• 转移方程：dp[x] = dp[x-k] + 1（以 x 结尾的等差数列长度）
• 关键细节：必须先排序，保证 x-k 在 x 之前被处理，否则 dp[x-k] 还没算出来
• 哈希表代替数组：arr[i] 范围 ±10
• 暴力解 O(n²) 超时，DP 降到 O(n log n)

[HackerRank] 29. Max Unique Substring Length in a Session

• 题型：滑动窗口
• 第一次接触滑动窗口，核心学到的：两个指针不回头，right 扩展窗口，left 收缩窗口
• 遇到重复字符时 left 追着 right 走，不需要重新扫描
• * 分隔符在遍历中处理，不需要真的分割字符串
• 两种解法：Set 版（while 逐步删）和 Map 版（直接跳到重复字符之后）

[HackerRank] 31. Next Greater Element with Position Offset

• 题型：单调栈
• 第一次接触单调栈，核心学到的：从右往左遍历，栈维护从底到顶递减的候选索引
• 每个元素三步：弹出比当前小的 → 读栈顶（就是答案）→ 入栈
• 为什么 O(n)：每个元素入栈出栈各一次，和滑动窗口一样指针不回头
• 暴力解 O(n²) 也能 AC，单调栈 O(n) 是正解

[HackerRank] 35. Longest Alternating Binary Substring with Limited Flips

• 题型：滑动窗口进阶
• 第 29 题的滑动窗口升级版，窗口合法条件从”无重复”变成”不匹配数 <= k”
• 交替串只有两种模式 0101… 和 1010…，各跑一次滑动窗口取最大值
• 踩坑：第一版用 s[left] 动态判断模式，left 移动后模式跟着变但 notGoods 没更新，固定模式 ‘01’/‘10’ 更稳定
• for…of [‘01’, ‘10’] 合并到一个函数里，start[right % 2] 取目标字符

[HackerRank] 37. Minimum Plans to Reach Target Bandwidth

• 题型：完全背包 / 硬币找零（LeetCode 322 Coin Change）
• DP 方程是求最小值：dp[i] = min(dp[i], dp[i - planSize] + 1)
• Infinity 初始化代表无解，有解时一定是 dp[i - planSize] + 1
• 踩坑：贪心不行，选最大的 planSize 不一定导致全局最优
• 和爬楼梯（计数 DP）的区别：累加 vs 取最小，同一框架换运算就换问题类型

[HackerRank] 38. Longest Increasing Subsequence Length

• 题型：DP + 二分查找优化（贪心 + 二分）
• 朴素 DP：dp[i] = 以 quality[i] 结尾的 LIS 长度，内层遍历所有 j < i 取 max(dp[j]+1)，O(n²)
• tails + 二分：tails[i] 存”长度为 i+1 的递增子序列的最小末尾值”，用二分找替换位置，O(n log n)
• DP 方程里竟然可以包含遍历：dp[i] 不是简单递推，而是要扫描前面所有符合条件的 j 取最大值
• 踩坑：findIndex 是 O(n) 会超时，必须手写二分查找；严格递增用 >= 不是 >
• 核心理解：tails 是”末尾存当前子序列信息 + 前面存后续可能更优的子序列信息”，替换只动一个位置不丢长度记录

[HackerRank] 40. Peak Concurrent Sessions per User Group

• 题型：扫描线（事件排序 + 计数）
• 按时间戳排序，同一时间戳 login 优先，遍历时 login +1、logout -1，记录峰值
• 踩坑1：groupId 必须转 number，字符串做 Map key 输出类型不对
• 踩坑2：groupMap 初始化要先设 0 再 +1/-1，不能直接设 1
• 踩坑3：truthy 判断 0 是 falsy，必须用 has()
• 踩坑4：题目和用例不一致——说”order does not matter”实际必须排序，说”logout 有对应 login”但用例有无 login 的 logout，count 记 -1 但 peak 记 0

[HackerRank] 41. Queue from Two Stacks

• 题型：数据结构设计（双栈实现队列）
• 两个栈：inStack 负责 enqueue（push），outStack 负责 dequeue/peek（空了才从 inStack 倒过来）
• 均摊 O(1)：每个元素最多 push/pop 各两次
• 踩坑：只在 outStack 空了才倒，不空直接用；取巧用数组 + shift 是 O(n) 会超时

[LeetCode] 15. 三数之和

• 题型：排序 + 固定一个数 + 双指针
• 三数之和变两数之和：固定 nums[i]，left=i+1，right=末尾，找 nums[left]+nums[right]=-nums[i]
• 三处去重：i 跳过相邻相同，left 和 right 找到后也跳过相邻相同
• 踩坑：第一版用 Map 去重逻辑复杂且指针方向不对；i 是固定开头不在 left/right 之间

[LeetCode] 279. 完全平方数

• 题型：完全背包 / 硬币找零（同 HackerRank 第 37 题）
• 硬币就是完全平方数 1, 4, 9, 16…，target 就是 n
• dp[i] = min(dp[i], dp[i - jj] + 1)，jj 是完全平方数
• 新鲜点：j 不是从数组取，而是用 jj 动态生成完全平方数，内层循环条件是 jj <= i
• 内层最多 √n 次，整体 O(n × √n)

[LeetCode] 146. LRU 缓存

• 题型：设计题（哈希表 + 双向链表）
• 利用 JS Map 保持插入顺序的特性，不用手写双向链表
• get：delete + set 把 key 移到最新位置
• put：已存在的 key 先 delete 再 set；容量满时删第一个（最久没用的）
• 踩坑：get 不能只读不写，必须更新使用顺序；put 已存在的 key 不能直接 set，位置不会变
• 面试时如果要求不用 Map，要能用哈希表 + 双向链表实现