Algorithm_DataStructure 面试专题手册
💡 本章节共收录 2431 道面试真题，建议每天复习 10-20 题。
Q1: 请实现二分查找算法，并分析其时间复杂度和适用条件。
【核心解析】 有序数组；左右指针；中间值比较；递归或迭代实现；时间复杂度O(log n)；边界条件处理（空数组、重复元素）
Q2: 你知道哪些排序算法？快速排序的时间复杂度和空间复杂度是多少？
【核心解析】 冒泡、选择、插入、归并、快速、堆排序；快速排序平均O(n log n)，最坏O(n^2)；空间复杂度O(log n)递归栈
Q3: 在虚拟列表中，前缀高度表结合二分查找解决了什么问题？请解释其原理。
【核心解析】 虚拟列表需要快速定位滚动位置对应的数据索引；前缀高度表存储每个元素累计高度；二分查找根据滚动偏移量找到目标元素；时间复杂度O(log n)；减少DOM节点数量提升性能
Q4: 请列举你了解的排序算法，并说明归并排序的时间复杂度和空间复杂度。
【核心解析】 冒泡、选择、插入、快速、归并、堆排序等；归并排序时间复杂度O(n log n)；空间复杂度O(n)；稳定排序；分治思想
Q5: 实现一个myPromiseMap函数，输入一个数组、一个回调函数、一个最大并发数，返回一个数组。
【核心解析】 并发控制；Promise.all与race；任务队列；结果顺序保持；错误处理
Q6: 请手写实现括号匹配算法，并说明其原理。
【核心解析】 使用栈数据结构；遍历字符串，左括号入栈，右括号匹配栈顶；最终栈为空则匹配成功；考虑多种括号类型
Q7: 手写LRU缓存机制。
【核心解析】 数据结构选择（Map或双向链表+哈希表）；get与put操作；容量限制；时间复杂度O(1)；淘汰策略
Q8: 输入一个URL，获取所有的参数，设计测试样例，考虑边界，写一个健壮的代码。
【核心解析】 URL解析（searchParams）；处理重复参数；编码解码；边界情况（无参数、特殊字符、hash）；输出格式
Q9: 请手写实现Promise.all和Promise.race，并说明其使用场景。
【核心解析】 Promise.all：所有成功才成功，一个失败则失败；Promise.race：第一个完成的结果；实现要点：处理空数组、错误处理、返回数组顺序
Q10: 请手写实现数组扁平化（flatten）函数，支持指定深度。
【核心解析】 递归实现；利用reduce和concat；使用栈实现迭代版本；处理空数组和非数组元素
Q11: 请手写实现一个带并发限制的Promise调度器。
【核心解析】 控制并发数量；任务队列管理；动态添加任务；错误处理与重试机制
Q12: LeetCode 162：寻找峰值。请用二分查找实现，并说明边界条件和mid计算细节。
【核心解析】 二分查找思路；峰值定义：nums[i] > nums[i-1]且nums[i] > nums[i+1]；边界条件处理；mid计算防止溢出；时间复杂度O(log n)
Q13: 请实现二叉树的前序、中序、后序遍历（递归和迭代方式）。
【核心解析】 前序：根左右；中序：左根右；后序：左右根；递归实现简单；迭代使用栈；前序迭代：根入栈，弹出并处理，先右后左入栈；中序迭代：左链入栈，弹出处理，转向右子树；后序迭代：双栈或标记法
Q14: 请实现买卖股票的最佳时机（一次交易）并求最大利润。
【核心解析】 一次遍历，记录历史最低价；当前价格减去最低价得到利润；更新最大利润；时间复杂度O(n)，空间O(1)；扩展：多次交易、含手续费、冷冻期
Q15: 请实现无重复字符的最长子串。
【核心解析】 滑动窗口；使用哈希集合或哈希表记录字符索引；右指针扩展窗口，遇到重复则移动左指针；更新最大长度；时间复杂度O(n)
Q16: 请实现二分查找算法。
【核心解析】 有序数组；定义左右边界；循环或递归；取中间值比较；根据比较结果缩小范围；时间复杂度O(log n)；注意边界条件（左闭右闭、左闭右开）
Q17: 请手写一个节流函数（throttle），并说明其应用场景？
【核心解析】 节流函数：在指定时间间隔内只执行一次；实现：使用时间戳或定时器；应用场景：滚动事件、resize事件、按钮点击防重复
Q18: 买卖股票的最佳时机（LeetCode 121）的解题思路和实现。
【核心解析】 一次遍历，记录历史最低价；计算当前利润并更新最大利润；时间复杂度O(n)，空间复杂度O(1)；动态规划思想；变体：含手续费、冷冻期
Q19: 怎么判断链表是否有环？快慢指针的原理是什么？
【核心解析】 快慢指针；快指针每次两步，慢指针一步；相遇则有环；时间复杂度O(n)；空间复杂度O(1)
Q20: 什么是hash碰撞？怎么解决？
【核心解析】 不同输入得到相同哈希值；解决方法：链地址法、开放地址法、再哈希法
Q21: 手写拼手气红包算法：m金额分给n个人，扩展：每个人分到的金额尽可能平均。
【核心解析】 二倍均值法；随机分配；保证最小单位；扩展：使用最大最小公平算法
Q22: 手写classnames函数。
【核心解析】 接受字符串、对象、数组；过滤假值；拼接类名；支持嵌套
Q23: 请实现爬楼梯问题（每次可以爬1或2阶，到达n阶有多少种方法），并分析时间复杂度。
【核心解析】 动态规划：dp[i]=dp[i-1]+dp[i-2]；初始条件：dp[0]=1, dp[1]=1；优化：滚动数组降低空间复杂度O(1)；时间复杂度O(n)；也可用递归+记忆化
Q24: 手写节流函数（throttle）的实现？
【核心解析】 定义时间戳或定时器；每次触发判断时间间隔；间隔内不执行；可配置leading/trailing；常见场景：滚动、resize
Q25: 实现O(log n)时间复杂度的乘法运算（不使用乘号）？
【核心解析】 使用位运算和加法；将乘数分解为二进制；左移累加；处理负数；递归或迭代实现
Q26: 请实现一个二叉树查找最大值的函数（前序遍历+打擂台）。
【核心解析】 递归遍历；前序/中序/后序均可；维护全局最大值；比较节点值；空节点处理；时间复杂度O(n)
Q27: 如何实现接口并行请求？例如同时发送a、b、c、d四个接口请求。
【核心解析】 使用Promise.all或Promise.allSettled；Promise.all一个失败则整体失败；Promise.allSettled等待所有完成，返回每个结果状态
Q28: 实现一个限制数量的事件调度器（Scheduler）。
【核心解析】 控制并发数，维护任务队列；每次执行时检查当前并发数，未达到则执行，否则入队；任务完成后出队下一个
Q29: 实现括号生成（LeetCode 22），并分析时间复杂度。
【核心解析】 回溯法，递归生成所有有效括号组合；时间复杂度O(4^n/sqrt(n))，空间复杂度O(n)
Q30: 实现两个版本序列号排序问题。
【核心解析】 将版本号按点分割，逐段比较数字大小；注意长度不同时补0
Q31: 请手写一个反转链表（k个一组反转）。
【核心解析】 链表节点定义；反转链表：迭代或递归；k个一组反转：先分组，每组反转，连接各组；注意边界条件
Q32: 请实现爬楼梯问题（斐波那契数列），并说明状态转移和边界条件。
【核心解析】 状态转移方程：dp[i] = dp[i-1] + dp[i-2]；边界条件：dp[0]=1, dp[1]=1；优化：滚动数组降低空间复杂度
Q33: 请手写实现二分查找算法。
【核心解析】 有序数组；递归或迭代；中间值比较；边界条件处理；时间复杂度O(log n)
Q34: 请手写实现两个有序数组合并成一个有序数组。
【核心解析】 双指针法；比较当前元素；处理剩余元素；时间复杂度O(m+n)；空间复杂度O(m+n)
Q35: 给定一个二叉树，找出最深层级的子节点（可能有多个），并返回。
【核心解析】 层序遍历（BFS）；记录每层节点；深度优先搜索（DFS）记录最大深度；返回最深节点列表
Q36: 请实现两数之和（Two Sum）算法，并分析时间复杂度。
【核心解析】 暴力法（双重循环，O(n^2)）；哈希表法（一次遍历，O(n)）；处理重复元素；返回索引或值；扩展（三数之和、四数之和）
Q37: 算法题：实现一个函数，计算数组中所有偶数的和。
【核心解析】 遍历数组；判断偶数（%2===0）；累加；时间复杂度O(n)；边界处理
Q38: 请手写二叉树的层序遍历，并解释思路。
【核心解析】 使用队列实现；根节点入队；循环取出节点并访问，左右子节点入队；BFS思想；时间复杂度O(n)
Q39: 请手写爬楼梯问题（动态规划），并解释思路。
【核心解析】 状态定义：dp[i]表示到第i阶的方法数；转移方程：dp[i]=dp[i-1]+dp[i-2]；初始条件：dp[0]=1, dp[1]=1；优化：滚动变量降低空间复杂度；时间复杂度O(n)
Q40: 请解释虚拟DOM树最小更新（Diff算法）的核心思路，包括节点匹配、插入/删除/更新三大操作、同层对比逻辑。
【核心解析】 同层对比，不跨层级；key属性优化节点复用；三种操作：插入、删除、更新；节点类型不同则直接替换；列表diff使用双端比较算法；时间复杂度O(n)
Q41: 算法题：买卖股票的最佳时机 II。请实现并说明解题思路。
【核心解析】 贪心算法；累计所有正利润；一次遍历；时间复杂度O(n)；空间复杂度O(1)
Q42: 手写一个可以控制层级的数组扁平化（flat）方法。
【核心解析】 递归实现；利用reduce和concat；控制深度参数；使用栈或迭代；处理空数组和非法输入
Q43: 手撕代码：一个属性降序，如果相等按另外一个属性升序。除了sort函数还有什么实现方法？
【核心解析】 使用Array.prototype.sort自定义比较函数；其他方法：冒泡排序、快速排序、归并排序等手动实现
Q44: 手写实现防抖函数，并解释其原理和应用场景。
【核心解析】 防抖定义（延迟执行，连续触发重置计时器）；实现（使用setTimeout和clearTimeout）；应用（输入搜索、窗口resize）；与节流的区别
Q45: 给定一个整数数组nums和一个整数k，统计并返回数组中和为k的连续子数组的个数。
【核心解析】 前缀和+哈希表；时间复杂度O(n)；空间复杂度O(n)；注意处理负数
Q46: 二叉树层序遍历，如何实现每层从右往左输出？
【核心解析】 层序遍历使用队列；从右往左：入队时先右子节点后左子节点；或正常遍历后反转每层结果；递归方法
Q47: 手写实现有效的括号匹配算法（LeetCode 20）。
【核心解析】 使用栈数据结构；匹配规则（括号对）；遍历字符串；时间复杂度O(n)；边界条件处理
Q48: 请手写实现一个符合Promise/A+规范的Promise。
【核心解析】 状态机（pending/fulfilled/rejected）；then方法链式调用；resolve/reject的异步执行；处理值穿透和错误捕获；静态方法（all、race等）
Q49: 请手写防抖和节流函数，并说明它们的区别和应用场景。
【核心解析】 防抖（debounce）在连续触发后只执行最后一次；节流（throttle）在固定时间间隔内只执行一次；防抖适用于输入搜索，节流适用于滚动事件；实现时注意this和参数
Q50: 请手写一个深拷贝函数，考虑循环引用和特殊类型（如Date、RegExp）。
【核心解析】 基础类型直接返回；对象递归拷贝；使用WeakMap解决循环引用；处理数组、Date、RegExp等特殊对象；考虑Symbol和不可枚举属性
Q51: 请手写实现call、apply、bind方法。
【核心解析】 call/apply改变this指向并立即执行；bind返回新函数且可绑定参数；使用Symbol避免属性冲突；考虑new操作符对bind的影响
Q52: 请手写数组去重和数组扁平化（flat）的实现。
【核心解析】 去重：Set、filter+indexOf、reduce；扁平化：递归、reduce+concat、迭代器；考虑深度参数；处理空数组和边界情况
Q53: 求二叉树的最大深度。
【核心解析】 递归：左右子树最大深度+1；迭代：层序遍历；时间复杂度O(n)；空间复杂度O(height)
Q54: 请手写一个深拷贝函数，并考虑处理除了对象和数组类型之外的数据（如Date、RegExp、Map、Set等）。
【核心解析】 基础类型直接返回；对象和数组递归拷贝；处理循环引用（使用WeakMap）；特殊对象如Date、RegExp、Map、Set需创建新实例；函数通常共享引用
Q55: 请实现二叉树的层序遍历（广度优先遍历）？
【核心解析】 使用队列；逐层遍历；记录每层节点数；递归或迭代；时间复杂度O(n)；空间复杂度O(n)
Q56: 如何用3升和5升容器量出4升水？
【核心解析】 装满5升，倒入3升至满，5升剩2升；倒空3升，将5升中2升倒入3升；再装满5升，倒入3升至满（3升已有2升，需1升），5升剩4升
Q57: 在电商SKU选择组件中，如何高效计算当用户选中某个属性时，哪些其他属性组合不可选？
【核心解析】 构建SKU组合的哈希表或邻接矩阵；使用笛卡尔积与库存数据匹配；通过位运算或集合运算快速判断；动态更新可选状态；减少重复计算
Q58: 手写防抖和节流函数。
【核心解析】 防抖：延迟执行，频繁触发重置定时器；节流：固定时间间隔执行；使用闭包保存定时器；注意this和参数传递；应用场景：输入搜索、滚动事件
Q59: 请实现一个数组扁平化函数，将嵌套数组转换为一维数组。
【核心解析】 递归实现；reduce+concat；Array.isArray判断；深度控制；使用flat方法
Q60: 给定一个包含id和parentId字段的节点列表，请将其转换为树形结构（森林）。
【核心解析】 建立id到节点的映射；遍历节点，根据parentId构建父子关系；收集根节点（无parentId）；处理循环引用；使用Map或对象
Q61: LeetCode 198: 打家劫舍问题，如何用动态规划求解？
【核心解析】 状态定义dp[i]表示前i个房屋能偷到的最大金额；状态转移方程dp[i]=max(dp[i-1], dp[i-2]+nums[i])；边界条件；空间优化（滚动数组）
Q62: 二叉树的右视图如何实现？可以用DFS（后序遍历）吗？
【核心解析】 层序遍历（BFS）取每层最后一个节点；DFS（根右左顺序）记录深度；后序遍历的变种；递归与迭代实现
Q63: 三个有序数组的交集如何求？请说明思路。
【核心解析】 哈希表统计元素出现次数；三指针法（归并思想）；时间复杂度O(n)；空间复杂度O(1)或O(n)
Q64: 请描述机考中遇到的数组与字符串经典题型、队列应用以及贪心算法题目的解题思路。
【核心解析】 数组与字符串：双指针、滑动窗口；队列：BFS、优先队列；贪心：局部最优推导全局最优；场景化理解题意；边界条件处理
Q65: 什么是排序算法的稳定性？请举例说明。
【核心解析】 稳定性定义（相等元素相对顺序不变）；稳定排序（冒泡、插入、归并）；不稳定排序（选择、快速、堆）；实际应用场景
Q66: 请描述快速排序的思路。
【核心解析】 分治策略；选择基准（pivot）；分区操作（小于基准放左边，大于放右边）；递归排序；时间复杂度（平均O(n log n)）
Q67: 请描述堆排序的思路。
【核心解析】 堆数据结构（大顶堆/小顶堆）；建堆过程；堆调整（heapify）；排序过程（交换堆顶与末尾）；时间复杂度O(n log n)
Q68: 请描述 LeetCode 第70题“爬楼梯”的解题思路，并写出核心代码（可以用递归、动态规划等方式）。
【核心解析】 问题转化为斐波那契数列；递归解法与重复计算问题；动态规划状态转移方程；空间优化（滚动数组）；时间复杂度与空间复杂度分析
Q69: 如何判断一个链表是否有环？请说明思路并给出代码实现。
【核心解析】 快慢指针法（Floyd判圈算法）；哈希表法；环的入口点查找；时间复杂度O(n)与空间复杂度O(1)；边界条件处理
Q70: 爬楼梯问题：每次可以爬1或2个台阶，求爬到第n阶的方法数。
【核心解析】 动态规划；状态转移方程dp[n]=dp[n-1]+dp[n-2]；边界条件dp[1]=1,dp[2]=2；空间优化（滚动数组）
Q71: 手写冒泡排序算法。
【核心解析】 双重循环；相邻元素比较交换；优化：设置标志位提前退出；时间复杂度O(n^2)
Q72: 手写二叉树遍历（前序、中序、后序、层序）。
【核心解析】 递归实现；迭代实现（栈/队列）；前序：根左右；中序：左根右；后序：左右根；层序：BFS
Q73: 请实现自定义排序：将输入的数字转换成二进制后，按照二进制中0的个数进行排序。
【核心解析】 二进制转换方法；自定义比较器；排序算法（如快速排序）；处理负数和零的情况；时间复杂度分析
Q74: 请用BFS和DFS两种方法解决岛屿数量问题。
【核心解析】 DFS递归实现；BFS队列实现；visited标记避免重复；网格遍历；时间复杂度O(m*n)
Q75: 算法题：给定一棵二叉树，求从根节点到叶子节点的路径和等于目标值的所有路径？
【核心解析】 深度优先搜索（DFS）；递归遍历；回溯；路径记录；时间复杂度O(n)
Q76: 手写实现：统计字符串中每个字符出现的次数？
【核心解析】 使用对象或Map存储；遍历字符串；时间复杂度O(n)；考虑Unicode字符
Q77: 请手写快速排序算法，并分析其时间复杂度和空间复杂度。
【核心解析】 分治思想；选择基准；分区操作；递归实现；平均O(nlogn)；最坏O(n^2)；原地排序
Q78: 请实现二叉树的中序遍历（递归和非递归两种方式）。
【核心解析】 左根右顺序；递归实现；栈模拟；Morris遍历；时间复杂度O(n)；空间复杂度O(h)
Q79: 数组去重有哪些方法？Set和Map有什么区别？
【核心解析】 Set去重（[...new Set(arr)]）；filter+indexOf；reduce+includes；Map键值对存储；Set存储唯一值；Map可迭代，键可以是任意类型
Q80: 请实现一个版本号排序函数，输入一个版本号列表（如['1.0.0', '2.1.0', '1.9.9']），按版本号从小到大排序。
【核心解析】 分割字符串为数字数组；比较每个部分；处理不等长版本号；使用Array.sort自定义比较函数
Q81: 给定一个数组A，每个元素包含id和parentId，请将其转换为树形结构（如：A = [{id:2, parentId:1}, {id:1}, {id:3, parentId:2}, {id:5, parentId:4}, {id:4}]）。
【核心解析】 使用Map建立id到节点的映射；遍历数组，将子节点添加到父节点的children中；根节点为parentId不存在的节点
Q82: 快速排序的时间复杂度是多少？请简述其思路。
【核心解析】 平均O(n log n)，最坏O(n^2)；分治思想：选基准，分区，递归排序；优化：随机基准、三数取中；原地排序版本
Q83: 请实现一个函数，将给定的树形结构（包含id和children）转换为扁平数组。
【核心解析】 递归遍历或迭代；深度优先或广度优先；收集所有节点；处理parentId关系；返回扁平数组
Q84: 请实现二叉树的左视图。
【核心解析】 层序遍历（BFS）取每层第一个节点；递归DFS记录深度；时间复杂度O(n)；空间复杂度O(n)
Q85: 数组和链表有什么区别？
【核心解析】 数组内存连续，支持随机访问；链表内存不连续，不支持随机访问；数组插入删除需移动元素，链表只需修改指针；数组大小固定，链表动态；链表有额外指针开销
Q86: 请介绍三种你最熟悉的排序算法。
【核心解析】 快速排序：分治，平均O(nlogn)；归并排序：分治，稳定O(nlogn)；堆排序：利用堆，O(nlogn)；冒泡排序：简单但慢O(n^2)
Q87: 什么是平衡二叉树？为什么要设计这种数据结构？
【核心解析】 平衡二叉树左右子树高度差不超过1；保证查找、插入、删除操作的时间复杂度为O(logn)；防止退化为链表；常见实现有AVL树、红黑树
Q88: 请讲解归并排序算法的原理、时间复杂度和实现？
【核心解析】 分治思想；递归拆分；合并有序数组；时间复杂度O(n log n)；空间复杂度O(n)；稳定排序
Q89: 手写题：实现一个函数柯里化（currying）。
【核心解析】 柯里化是将多参数函数转换为一系列单参数函数；实现：返回新函数，收集参数，参数足够时执行原函数；支持占位符（可选）；应用：参数复用、延迟执行
Q90: 手写题：实现一个debounce（防抖）和throttle（节流）函数。
【核心解析】 防抖：延迟执行，连续触发重置定时器；节流：固定时间间隔执行一次；防抖应用：输入搜索；节流应用：滚动事件；实现：利用setTimeout和clearTimeout；可配置leading/trailing
Q91: 手写实现深拷贝，如何处理循环引用？
【核心解析】 递归遍历；判断引用类型；使用WeakMap记录已拷贝对象；处理循环引用；支持数组和对象
Q92: 手写实现深拷贝，如何处理循环引用？
【核心解析】 递归遍历；判断引用类型；使用WeakMap记录已拷贝对象；处理循环引用；支持数组和对象
Q93: 请实现一个超时重试函数。
【核心解析】 设计思路（Promise.race实现超时，递归或循环实现重试）；需要考虑（重试次数、延迟策略、指数退避）；边界情况（网络错误、超时、取消）；AbortController的使用
Q94: 请实现找出最小的k个数（Top K问题）。
【核心解析】 排序法（O(nlogn)）；堆（最大堆，O(nlogk)）；快速选择（Quick Select，平均O(n)）；适用于海量数据（堆）
Q95: 请实现一个图片加载方法，要求最多同时加载n个图片，传入images的src数组，使图片完成加载最快。
【核心解析】 使用并发控制；维护一个正在加载的计数；每次从队列中取出图片开始加载；加载完成后递归调用；利用Promise.all或async/await
Q96: 随机生成的字符串中混有JSON字符串，写一个方法提取JSON字符串。
【核心解析】 遍历字符串，找到第一个'{'或'['；使用栈匹配括号；提取子串并尝试JSON.parse；若成功则返回，否则继续寻找下一个
Q97: 请手写一个深拷贝函数，并说明需要考虑哪些边界情况。
【核心解析】 递归实现；处理循环引用（WeakMap缓存）；处理特殊对象（Date、RegExp、Map、Set）；忽略原型属性；处理Symbol属性
Q98: 一个7升的水杯和一个3升的水杯，如何量出2升的水？
【核心解析】 装满7升杯；倒入3升杯两次，剩余1升；清空3升杯，将1升倒入；再装满7升杯，倒入3升杯至满，剩余5升；倒掉3升杯，再倒入3升杯至满，剩余2升
Q99: 请实现有效的括号匹配（LeetCode 20）和爬楼梯（LeetCode 70）算法。
【核心解析】 有效括号：使用栈，遇到左括号入栈，右括号匹配出栈；时间复杂度O(n)；爬楼梯：动态规划，dp[i]=dp[i-1]+dp[i-2]；空间优化：滚动数组
Q100: 请列举常见的排序算法，并说明哪些是稳定的排序算法？
【核心解析】 稳定排序：冒泡、插入、归并、基数；不稳定排序：选择、快速、堆、希尔；稳定性定义：相等元素相对顺序不变