Algorithm_DataStructure 面试专题手册
💡 本章节共收录 4239 道面试真题，建议每天复习 10-20 题。
Q1: 不考虑范围查询，红黑树和哈希表有什么区别？
【核心解析】 哈希表平均O(1)查找，红黑树O(log n)；哈希表无序，红黑树有序；哈希表依赖哈希函数，红黑树依赖比较；哈希表处理冲突（链地址法、开放地址法），红黑树通过旋转保持平衡；哈希表适合等值查询，红黑树适合范围查询。
Q2: 什么是哈希冲突？如何解决？
【核心解析】 哈希冲突指不同键映射到同一哈希值；解决方法：链地址法（拉链法）、开放地址法（线性探测、二次探测、双重哈希）、再哈希法、建立公共溢出区。
Q3: 你知道哪些哈希算法？
【核心解析】 MD5、SHA-1、SHA-256、SHA-3、CRC32、MurmurHash、CityHash、一致性哈希算法。
Q4: 哈希计算的结果是什么？是内存地址吗？
【核心解析】 哈希结果是固定长度的数字摘要，不是内存地址；哈希值通过哈希函数计算得到，用于数据索引或校验；内存地址是变量在内存中的位置，与哈希值不同。
Q5: 举个例子，数字1234如何哈希？
【核心解析】 简单哈希：取模运算，如1234 % 10 = 4；或使用哈希函数如MD5：1234的MD5值为81dc9bdb52d04dc20036dbd8313ed055；实际哈希算法更复杂，考虑分布均匀性。
Q6: 不考虑范围查询和Key的有序性，哈希表和红黑树在KV映射场景下的适用场景和局限性是什么？
【核心解析】 哈希表适用于O(1)平均查找时间，但不支持有序遍历；红黑树支持有序遍历和范围查询，但查找时间为O(log n)；哈希表需要处理哈希冲突，红黑树通过旋转保持平衡。
Q7: 哈希冲突是什么？常见的解决方法有哪些？
【核心解析】 哈希冲突指不同键映射到同一哈希值；解决方法包括链地址法（拉链法）、开放地址法（线性探测、二次探测、双重哈希）、再哈希法；Java HashMap使用链地址法，当链表过长时转为红黑树。
Q8: 常见的哈希算法有哪些？哈希计算的结果是内存地址吗？
【核心解析】 常见哈希算法包括MD5、SHA-1、SHA-256、CRC32、MurmurHash等；哈希结果是一个固定长度的二进制值或整数，不是内存地址；哈希值用于快速定位存储位置，但实际地址由哈希表实现决定。
Q9: 以数字1234为例，解释哈希过程。
【核心解析】 哈希函数将输入映射为固定范围的值；例如取模法：1234 % 10 = 4；更复杂的哈希如乘法哈希：乘以黄金比例后取小数部分；实际哈希函数会考虑均匀分布和冲突率。
Q10: 常见的排序算法有哪些？快速排序的时间复杂度是多少？最好、最坏、平均情况分别是什么？
【核心解析】 常见排序：冒泡、选择、插入、希尔、归并、快速、堆排序、计数排序等；快速排序平均O(n log n)，最好O(n log n)，最坏O(n^2)；最坏情况发生在每次选取的基准都是最大或最小元素。
Q11: 红黑树有哪些应用场景？
【核心解析】 红黑树用于实现关联容器如C++ map/set、Java TreeMap/TreeSet；用于内存管理如Linux内核的调度器；用于实现时间轮、定时器等；平衡二叉搜索树的一种，保证最坏情况O(log n)操作。
Q12: unordered_map（哈希表）在rehash时如何重新映射？rehash的复杂度高吗？
【核心解析】 rehash时创建新桶数组，将旧元素重新计算哈希并插入新桶；复杂度为O(n)，n为元素个数；虽然单次rehash耗时，但均摊后为O(1)；rehash触发条件通常为负载因子超过阈值。
Q13: 给定一个只包含'A'和'B'的字符串，求将所有'A'移动到左边、所有'B'移动到右边所需的最小相邻交换次数。
【核心解析】 问题等价于求逆序对数量；遍历字符串，统计每个'A'前面'B'的个数并累加；或使用双指针，从左到右移动'A'，计算交换次数。
Q14: 给定一组城市IP范围，输入一个IP，如何查找其对应的城市？
【核心解析】 将IP转换为整数；对IP范围列表按起始IP排序；使用二分查找找到包含目标IP的区间；若区间不重叠，可构建线段树或区间树优化；注意边界处理。
Q15: 手撕：链表重排（如L0→Ln→L1→Ln-1→...）
【核心解析】 快慢指针找中点；反转后半部分；合并两个链表
Q16: 手撕：合并两个有序数组，要求O(1)空间复杂度
【核心解析】 从后往前遍历；比较两个数组末尾元素，将较大者放入nums1末尾；处理剩余元素
Q17: 手撕：二分查找算法。
【核心解析】 前提：有序数组；定义左右指针left和right；循环条件left<=right；计算mid=(left+right)/2防溢出；比较target与arr[mid]，相等返回mid；target小则right=mid-1；大则left=mid+1；未找到返回-1；时间复杂度O(log n)。
Q18: 请介绍常见的排序算法，并分析快速排序的时间复杂度（最好、最坏、平均）。
【核心解析】 常见排序算法包括冒泡、选择、插入、希尔、归并、快速、堆排序等；快速排序最好时间复杂度O(n log n)，最坏O(n^2)，平均O(n log n)；最坏情况发生在每次选取的基准都是最大或最小元素时；可通过随机化或三数取中法优化避免最坏情况。
Q19: 请比较红黑树和哈希表（如unordered_map）的适用场景和局限性，不考虑区间搜索和Key的有序性，只关心KV映射。
【核心解析】 哈希表插入、查找、删除平均O(1)，但需要解决哈希冲突（如链地址法、开放地址法）；红黑树操作O(log n)，支持有序遍历；哈希表不适合范围查询，红黑树适合；哈希表在哈希函数设计不佳或冲突严重时性能退化；红黑树实现复杂，内存占用略高。
Q20: 请解释哈希表（如unordered_map）的rehash过程，包括如何重新映射以及rehash的复杂度。
【核心解析】 当负载因子超过阈值时触发rehash，通常创建新桶数组（大小约为原两倍）；重新计算每个元素的哈希值并映射到新桶；rehash时间复杂度O(n)，n为元素个数；为避免频繁rehash，可预先分配足够容量或使用渐进式rehash（如Redis的dict）。
Q21: 请介绍哈希冲突的常见解决方法。
【核心解析】 常见方法：链地址法（每个桶维护链表或红黑树）、开放地址法（线性探测、二次探测、双重哈希）、再哈希法、建立公共溢出区；链地址法实现简单，但可能链表过长；开放地址法空间利用率高，但删除复杂；Java HashMap使用链地址法，当链表长度超过8且数组长度>=64时转为红黑树。
Q22: 旋转遍历数组（简单题）
【核心解析】 给定一个旋转后的有序数组，查找目标值或遍历；常用二分查找变种；时间复杂度O(log n)
Q23: 最长连续无重复子串的长度问题如何用滑动窗口解决？请写出算法思路。
【核心解析】 使用双指针维护一个滑动窗口；右指针遍历字符串，左指针根据重复字符调整；用哈希表记录字符最近出现位置；窗口内无重复字符时更新最大长度；时间复杂度O(n)，空间复杂度O(字符集大小)。
Q24: 请实现一个函数，找出字符串中无重复字符的最长子串的长度。
【核心解析】 滑动窗口法；使用哈希集合记录窗口内字符；右指针扩展，遇到重复时左指针收缩；时间复杂度 O(n)，空间复杂度 O(字符集大小)。
Q25: 请实现一个函数，交换链表中的相邻节点（两两交换）。
【核心解析】 递归或迭代；迭代：使用哑节点，每次交换两个节点，更新指针；递归：交换前两个节点，然后递归处理剩余链表。
Q26: 请实现一个函数，每 k 个节点一组反转单链表。
【核心解析】 递归或迭代；先遍历链表判断剩余节点是否足够 k 个；若足够，反转这 k 个节点，然后递归处理剩余部分；注意连接反转后的子链表。
Q27: 请实现一个函数，合并两个有序数组（非递减顺序）。
【核心解析】 双指针从后向前遍历，避免覆盖；将两个数组合并到第一个数组（假设有足够空间）；时间复杂度 O(m+n)，空间复杂度 O(1)。
Q28: 有序链表中删除所有重复节点，要求时间复杂度O(n)，空间复杂度O(1)，设置虚拟头节点的好处是什么？
【核心解析】 虚拟头节点简化边界处理；避免对头节点特殊判断；统一删除逻辑；便于返回新链表头；防止头节点被删除时丢失引用
Q29: 手撕：判断一个链表内部是否有循环，有的话找到循环开始的节点位置。
【核心解析】 使用快慢指针检测环；快指针每次两步，慢指针每次一步；相遇则存在环；从相遇点和头节点同步移动，相遇处即为环入口
Q30: 给定一个缺少一个数的连续数组，找出缺少的是哪个
【核心解析】 使用求和公式计算期望总和减去实际总和；使用异或运算，将数组元素与完整序列异或得到缺失值；时间复杂度O(n)，空间复杂度O(1)；注意数组是否有序及边界情况；也可以使用哈希集合或排序后遍历。
Q31: 实现O(1)时间复杂度的LRU缓存
【核心解析】 哈希表+双向链表；哈希表存储key到节点的映射；双向链表维护访问顺序；get时移动节点到头部；put时若存在则更新并移动，若不存在则插入头部并检查容量；容量满时删除尾部节点；O(1)操作
Q32: 合并K个升序链表
【核心解析】 优先队列（最小堆）；分治合并；顺序合并；时间复杂度O(NlogK)；空间复杂度O(K)；注意链表为空的情况；堆中存储节点值和链表索引
Q33: 反转链表
【核心解析】 迭代法：使用三个指针prev、curr、next遍历链表，逐个反转；递归法：递归到链表末尾，然后逐层反转；注意处理空链表和单节点链表；时间复杂度O(n)，空间复杂度O(1)（迭代）或O(n)（递归）。
Q34: 合并两个有序链表
【核心解析】 迭代法：使用虚拟头节点，比较两个链表当前节点值，将较小者接入结果链表；递归法：比较头节点值，递归合并剩余部分；注意处理其中一个链表为空的情况；时间复杂度O(n+m)，空间复杂度O(1)（迭代）或O(n+m)（递归）。
Q35: 快速排序
【核心解析】 选择基准元素（如第一个、最后一个或随机）；分区操作：将小于基准的元素放左边，大于的放右边；递归对左右子数组排序；时间复杂度平均O(n log n)，最坏O(n^2)；空间复杂度O(log n)（递归栈）。
Q36: 双端队列的定义、特性及应用场景
【核心解析】 双端队列（Deque）支持两端插入和删除；相比队列（FIFO）和栈（LIFO）更灵活；常用实现：ArrayDeque、LinkedList；应用：滑动窗口、任务调度、撤销操作；在滑动窗口中求最大最小值可用单调双端队列，保持队列递减/递增。
Q37: 双端队列在滑动窗口中求最大最小值的工作原理
【核心解析】 维护一个单调双端队列，存储元素索引；窗口右移时，移除超出窗口的索引；新元素入队前，从队尾移除所有小于（求最大）或大于（求最小）的元素；队首即为当前窗口极值；时间复杂度O(n)。
Q38: 实现一个LRU缓存，要求手撕代码。
【核心解析】 LRU缓存淘汰策略；使用哈希表+双向链表实现；get和put操作的时间复杂度为O(1)；维护最近访问顺序；考虑并发安全。
Q39: 求链表中倒数第k个元素，要求只遍历一次。
【核心解析】 双指针法（快慢指针）；快指针先走k步；边界条件处理（k大于链表长度）；空间复杂度O(1)；也可以使用哈希表存储节点位置，但面试官认为取巧。
Q40: 请比较数组和链表的区别，并说明在实际工程中如何选择。
【核心解析】 数组连续存储，支持O(1)随机访问，缓存局部性好，遍历快；链表节点分散，插入删除已知位置节点方便，无需搬移元素；链表访问时频繁跳地址，缓存命中率低，实际执行效率往往不如数组；工程中数组或vector通常比链表更快，除非需要频繁在中间插入删除；选择时需考虑内存连续性、缓存局部性和操作频率。
Q41: 手撕：实现 LRU 缓存，要求 get 和 put 操作都是 O(1) 时间复杂度。
【核心解析】 使用哈希表 + 双向链表；哈希表存储 key 到节点的映射；双向链表维护访问顺序；get 时移动节点到头部；put 时若存在则更新并移动，若不存在则插入头部，超出容量则删除尾部节点。
Q42: 手撕：手写快速排序，并说明平均和最坏时间复杂度。
【核心解析】 快速排序采用分治策略，选取基准元素，分区后递归排序；平均时间复杂度 O(n log n)；最坏时间复杂度 O(n^2)（当每次分区极不平衡时）；可通过随机选择基准优化。
Q43: 如何查看链表是否有环？
【核心解析】 使用快慢指针法；快指针每次走两步，慢指针每次走一步；若相遇则有环；若快指针到达 null 则无环；也可使用哈希表记录访问过的节点。
Q44: 实现一个LRU缓存，应该用什么数据结构？
【核心解析】 使用哈希表+双向链表；哈希表提供O(1)查找，双向链表维护访问顺序；每次访问将节点移到链表头部，淘汰时删除尾部节点。
Q45: 给定一个矩阵，从任意节点出发，求递增序列的最大长度。要求时间复杂度分析。
【核心解析】 使用深度优先搜索+记忆化；每个格子作为起点，递归搜索四个方向，记录已计算的最长路径；时间复杂度O(m*n)。
Q46: 手撕：最长无重复子串。
【核心解析】 滑动窗口法；使用哈希集合记录窗口内字符；右指针扩展，遇到重复则移动左指针；时间复杂度O(n)。
Q47: 数据结构选择题：二叉树遍历、栈与队列、排序稳定性。
【核心解析】 二叉树遍历：前序、中序、后序、层序；栈与队列：先进后出、先进先出；排序稳定性：稳定排序如冒泡、插入，不稳定如选择、快排。
Q48: 编程题：阅读理解，根据公式计算，输出保留两位小数。
【核心解析】 理解公式，注意输入输出格式；使用DecimalFormat或printf保留小数。
Q49: 手撕：魔法字符串（括号匹配变式）。
【核心解析】 使用栈匹配字符；遍历字符串，遇到左字符入栈，右字符检查栈顶是否匹配；不匹配或栈空则无效。
Q50: 判断一个链表内部是否有循环，有的话找到循环开始的节点位置。
【核心解析】 使用快慢指针法判断是否有环；快指针每次两步，慢指针每次一步，相遇则有环；找到环入口：相遇后，一个指针从头开始，另一个从相遇点，每次一步，再次相遇处即为环入口。
Q51: 栈和队列的区别是什么？
【核心解析】 栈是后进先出（LIFO）结构，队列是先进先出（FIFO）结构；栈的插入和删除操作都在栈顶，队列在一端插入（队尾）另一端删除（队头）；栈常用于函数调用、表达式求值，队列常用于任务调度、缓冲。
Q52: 如何在不修改原数组的情况下找到数组中重复的数？
【核心解析】 使用快慢指针法（Floyd判圈算法），将数组视为链表，索引为节点值，值为next指针；由于存在重复数，会形成环；快慢指针在环内相遇后，再从头开始找环入口；时间复杂度O(n)，空间复杂度O(1)；注意数组元素范围需在1到n之间。
Q53: 手撕算法：判断链表是否有环、计算树的高度。
【核心解析】 链表环判断：快慢指针法，快指针每次两步，慢指针一步，相遇则有环；树的高度：递归计算左右子树最大高度加1，或层序遍历统计层数。
Q54: 滑动窗口求最大容器（LeetCode 11. 盛最多水的容器）如何实现？
【核心解析】 双指针法，左右指针分别指向数组两端；计算当前面积（min(height[left], height[right]) * (right-left)）；移动较矮的指针；更新最大面积；时间复杂度O(n)，空间复杂度O(1)。
Q55: 手撕链表逆序求和（类似LeetCode 445）：两个链表表示的数字相加，返回结果链表。
【核心解析】 先反转链表；逐位相加并处理进位；注意链表长度不同；最后反转结果或使用栈
Q56: 请解决股票买卖问题：一次买卖的最大收益，以及必须完成两次买卖（不能当天买卖）的最大收益。
【核心解析】 一次买卖：遍历，维护前i-1天最低价格，计算当前卖出收益，取最大；两次买卖：动态规划，定义dp[i][k][0/1]表示第i天、交易k次、持有或不持有的最大收益；或分段计算，将数组分成左右两部分，分别计算一次买卖的最大收益，然后求和取最大。
Q57: 力扣 209：长度最小的子数组。给定一个含有 n 个正整数的数组和一个正整数 target，找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。
【核心解析】 使用滑动窗口法，维护左右指针和当前窗口和；当和 ≥ target 时，更新最小长度并移动左指针；时间复杂度 O(n)。
Q58: 实现一个线程安全的链表，要求提供 add、remove 等基本方法。
【核心解析】 使用同步锁（如 synchronized 或 ReentrantLock）保护链表操作；或者使用 ConcurrentLinkedQueue 等并发容器；注意迭代时的线程安全。
Q59: 找二叉树的最近公共祖先（LCA），讲思路及时间空间复杂度。
【核心解析】 递归：从根节点查找，若左右子树分别包含p和q则返回当前节点；时间复杂度O(n)，空间复杂度O(h)（h为树高）；迭代：使用父指针或路径记录；适用于二叉搜索树时可用值比较优化
Q60: 请解释负载均衡中如何用Round Robin实现带权重的任务分配？
【核心解析】 加权轮询算法：每个服务器分配一个权重，按权重比例分配请求；实现方式：维护一个当前索引和当前权重，每次选择当前权重最大的服务器；平滑加权轮询：避免连续请求同一服务器，使用动态权重调整。
Q61: 给定两个长度为2e5的排列p和q，求它们的最长公共子序列中字典序最大的一个。请解释如何将LCS转化为LIS，并说明如何利用suf数组和贪心构造字典序最大的答案，以及如何用BIT优化。
【核心解析】 将p中每个元素替换为它在q中的下标，LCS转化为LIS；suf[i]表示以i开头的最长上升子序列长度，从右向左DP，用BIT维护后缀最大值；贪心构造：按suf值分组，每组内按原值降序，依次选择满足位置和下标均递增的元素；时间复杂度O(nlogn)
Q62: 布隆过滤器（Bloom Filter）大概讲讲它是什么样的数据结构
【核心解析】 基于位数组和多个哈希函数；用于快速判断一个元素是否在集合中；存在误判率（假阳性），但不会漏判；支持插入和查询，不支持删除；空间效率高，适合大数据场景。
Q63: 排序算法的时间复杂度下界（下限）是什么？你了解过比O(N log N)更快的排序算法吗？
【核心解析】 基于比较的排序算法时间复杂度下界为O(N log N)；非比较排序如计数排序、基数排序、桶排序可以达到O(N)；计数排序适用于整数范围小的情况；基数排序按位排序；桶排序利用函数映射。
Q64: 手撕：螺旋打印二维数组
【核心解析】 定义上下左右四个边界；按顺时针方向遍历：从左到右、从上到下、从右到左、从下到上；每遍历完一行或一列后更新边界；注意边界条件避免重复打印。
Q65: LeetCode 31：下一个排列
【核心解析】 从右向左找到第一个降序对(i,i+1)使得 nums[i] < nums[i+1]；在i右侧找到大于nums[i]的最小值并交换；反转i+1到末尾的序列；若找不到降序对，直接反转整个数组
Q66: LeetCode 43：字符串相乘
【核心解析】 模拟竖式乘法，用数组存储每位乘积；两层循环遍历两个字符串的每一位；结果数组长度最多为len1+len2；处理进位；最后将数组转为字符串，去除前导零
Q67: 手撕代码：实现快速排序。
【核心解析】 选择基准（pivot），通常取中间或随机；分区：将小于基准的放左边，大于的放右边；递归排序左右子数组；时间复杂度平均O(n log n)，最坏O(n^2)；空间复杂度O(log n)（递归栈）；优化：三数取中、插入排序混合。
Q68: 手撕代码：二叉树前序和中序输出后序。
【核心解析】 前序第一个为根节点；在中序中找到根节点，左边为左子树，右边为右子树；递归构建左右子树；后序顺序：左-右-根；输出后序序列。
Q69: 实现路由匹配应该用什么数据结构？
【核心解析】 常用前缀树（Trie）或基数树（Radix Tree）；支持动态添加路由和通配符匹配；HTTP 框架如 Gin 使用 Radix Tree 实现高效路由；也可使用哈希表或正则表达式，但性能较低。
Q70: 手撕 LRU 缓存。
【核心解析】 使用哈希表 + 双向链表实现；哈希表 O(1) 查找，链表维护访问顺序；get 和 put 操作时间复杂度 O(1)；淘汰最近最少使用的节点。
Q71: 手撕：判断链表是否有环（需自己写输入输出构建链表）
【核心解析】 使用快慢指针法，快指针每次走两步，慢指针每次走一步；若快慢指针相遇则有环；注意边界条件（空链表、单节点无环）；空间复杂度O(1)，时间复杂度O(n)
Q72: 手撕快速排序；有一个很大的整数数组，找出里面最大的10个数字；长整形的数字计算它二进制表示中1的个数。
【核心解析】 快速排序：选基准、分区、递归；找最大10个数：使用大小为10的最小堆或快速选择算法；计算二进制1的个数：位运算（n & (n-1)）或查表法
Q73: 手撕代码：判断环形链表（LeetCode 141）
【核心解析】 使用快慢指针，快指针每次走两步，慢指针每次走一步；若相遇则有环；注意边界条件（空链表或单节点）；也可使用哈希表记录访问过的节点。
Q74: 实现一个LRU缓存变种，增加阈值k，只有访问次数达到k的键才进入淘汰范围，如何实现？
【核心解析】 使用哈希表+双向链表存储键值对及访问次数；维护一个计数器和两个链表：一个用于未达到k次的键，一个用于达到k次的键；访问时更新计数，当计数达到k时移动到淘汰链表；淘汰时从淘汰链表中移除最近最少使用的项；注意并发安全。
Q75: 手撕代码：寻找数组中第K大的元素，要求写出高效算法并分析时间复杂度。
【核心解析】 使用快速选择（QuickSelect）算法，平均时间复杂度O(n)；或使用大小为K的最小堆，时间复杂度O(n log K)；注意处理重复元素和边界条件。
Q76: K个一组翻转链表（最后剩余的节点需要反转）如何实现？
【核心解析】 使用递归或迭代；先计算链表长度；分组翻转，每组内部反转；剩余节点不足K个时也反转；注意边界条件；时间复杂度O(n)，空间复杂度O(1)
Q77: 无重复字符的最长子串如何求解？
【核心解析】 滑动窗口法；使用哈希集合或数组记录字符出现位置；双指针维护窗口；右指针扩展，左指针收缩；时间复杂度O(n)；空间复杂度O(字符集大小)
Q78: 最长递增子序列的解法有哪些？
【核心解析】 动态规划O(n^2)；贪心+二分查找O(n log n)；维护tails数组；二分查找插入位置；注意非严格递增与严格递增的区别
Q79: 手撕 LRU 缓存机制。
【核心解析】 LRU（最近最少使用）缓存淘汰算法；使用哈希表+双向链表实现；get和put操作时间复杂度O(1)；双向链表维护访问顺序，哈希表提供快速查找；节点包含key, value, prev, next；当缓存满时，删除链表尾部节点。
Q80: 实现一个非递归的二叉树前序遍历。
【核心解析】 使用栈模拟递归；先将根节点入栈；循环弹出栈顶节点并访问；先将右子节点入栈，再将左子节点入栈（保证左子树先访问）；注意栈的LIFO特性。
Q81: Bitmap的具体功能和实现原理是什么？
【核心解析】 Bitmap用位数组表示数据存在性，每个位对应一个元素；功能包括快速判断元素是否存在、去重、统计等；实现原理：将元素映射到位索引，通过位运算（如与、或、非）操作；优点：节省内存，适合海量数据；缺点：无法存储重复元素，需处理哈希冲突。
Q82: 实现一个跳表。
【核心解析】 跳表的数据结构定义；插入、删除、查找操作；随机层数的生成；时间复杂度分析；空间复杂度；与平衡树的比较；应用场景。
Q83: 给定一个长度为1e5的数组，每次删除最小的元素（相同则删除最靠前的），进行m轮，求删除m轮后的数组。
【核心解析】 使用pair存储值和下标；按值排序，值相同按下标排序；取第m个之后的元素；再按下标排序输出；时间复杂度O(n log n)。
Q84: 给定2e3个坐标，连接成所有线段，以每个端点为圆心、线段长度为半径画圆，求每个圆内包含的其他端点个数。
【核心解析】 计算所有点对距离；对每个点，将其到其他点的距离排序；对于每个j，二分查找距离≤dis(i,j)的个数；时间复杂度O(n^2 log n)；注意精度问题。
Q85: 给定两个长度为2e5的数组，求它们最长公共子序列中字典序最大的一个。
【核心解析】 最长公共子序列（LCS）问题；动态规划O(n^2)会超时；若数组是排列或值域有限，可优化到O(n log n)；字典序最大需在DP中记录转移；或使用贪心+二分。
Q86: 手撕：二叉树简单题。
【核心解析】 常见二叉树题目：遍历（前中后序、层序）、深度、路径、最近公共祖先、序列化等；递归与迭代实现；时间复杂度O(n)；空间复杂度。
Q87: 如何判断一个链表是否为回文？要求常数空间复杂度。
【核心解析】 使用快慢指针找到中点；反转后半部分链表；比较前后两部分值；恢复链表（可选）；时间复杂度O(n)，空间O(1)。
Q88: 给定一个数n，如23121，求小于n的最大数。
【核心解析】 从高位到低位遍历；找到第一个下降位；将该位减1，后面全置为9；处理前导零；返回结果。
Q89: 如何判断单向链表是否有环？
【核心解析】 使用快慢指针（Floyd判环算法）；快指针每次两步，慢指针每次一步；若相遇则有环；注意空链表和单节点情况。
Q90: 如何判断一棵二叉树是二叉搜索树？
【核心解析】 中序遍历结果递增；递归检查每个节点值在区间内；注意处理重复值；使用辅助函数传递上下界。
Q91: 手撕：两个有序数组，O(logN)求合并后第k大的数
【核心解析】 使用二分查找，每次排除一半元素；比较两个数组的第k/2个元素；递归缩小范围；注意边界条件和数组长度；时间复杂度O(log(m+n))；空间复杂度O(1)；类似寻找中位数问题
Q92: 手撕：给出一串数字，输出九键可能对应的所有字符串集合（回溯法）
【核心解析】 建立数字到字母的映射；使用回溯递归生成所有组合；path传递当前字符串；遍历当前数字对应的每个字母；递归下一层；回溯撤销选择；注意空输入处理
Q93: 两个有序列表的合并（ACM模式）
【核心解析】 双指针遍历两个链表；比较当前节点值，取较小者接入结果；处理剩余节点；注意输入输出格式；时间复杂度O(n+m)；空间复杂度O(1)（迭代）或O(n)（递归）；边界情况：空链表
Q94: 括号匹配
【核心解析】 使用栈；遍历字符串，遇到左括号入栈；遇到右括号检查栈顶是否匹配；匹配则出栈，否则返回false；最后栈为空则匹配；注意多种括号类型；时间复杂度O(n)；空间复杂度O(n)
Q95: 滑动窗口
【核心解析】 维护窗口左右边界；根据条件移动右边界；当窗口不满足条件时移动左边界；记录窗口最大值/最小值/长度等；常用双端队列优化；适用于子数组/子串问题；时间复杂度O(n)
Q96: 二维dp
【核心解析】 定义状态dp[i][j]；确定状态转移方程；初始化边界条件；遍历顺序；空间优化（滚动数组）；常见问题：路径、子序列、背包；注意索引越界
Q97: 链表综合（合并+反转）
【核心解析】 合并两个有序链表；反转链表（迭代或递归）；可能先合并再反转；注意指针操作；处理空链表；时间复杂度O(n)；空间复杂度O(1)
Q98: K个一组翻转链表
【核心解析】 使用哑节点；分组遍历，每组K个；反转组内链表；连接前后组；注意剩余不足K个时不反转；cur和pre指针正确维护；时间复杂度O(n)
Q99: 两个人轮流拿石头，一次最多拿3个最少拿1个，问石头数量为多少时先手必胜
【核心解析】 巴什博奕；如果石头总数是4的倍数，后手必胜；否则先手必胜；先手策略：取走总数模4的余数；使剩余石头为4的倍数；后手每次取4减先手取的数；保证每轮共取4个；数学归纳法证明
Q100: 螺旋数组：按螺旋顺序遍历或填充一个N×N的二维数组，N可以是奇数或偶数。请实现。
【核心解析】 定义上下左右边界；循环遍历直到边界交错；按右、下、左、上顺序遍历；更新边界；注意边界条件处理。