反转字符串有切片法（s[::-1]，时间空间复杂度均为o(n)）、双指针原地交换（转列表、首尾交换、join拼接）和递归法（需处理边界条件）。
反转字符串（含多种实现）
面试常考基础题，重点考察对 Python 内置方法、切片和双指针的理解。
- 切片法最简洁：
s[::-1]，适合单行回答，但需说明其时间空间复杂度（O(n), O(n)） - 双指针原地交换更体现算法思维：用
list(s)转为列表，首尾交换后''.join()拼回 - 递归写法需注意边界（
if len(s) ）和栈深度限制，一般不推荐用于长字符串
两数之和（返回下标）
哈希表应用的典型题，核心是“边遍历边查补数”。
- 用字典存
{数值: 下标}，遍历中计算target - 当前数，查字典是否存在 - 注意题目是否允许重复使用同一元素（通常不允许），所以查补数要在更新字典前做
- 若要求返回所有解，改用双重循环或记录多组下标；若只找一对，一次遍历即可
链表相关（反转/检测环/合并）
虽不强制手写完整链表类，但需能快速写出关键操作逻辑。
- 反转单链表：用三个变量（pre, cur, nxt）迭代，避免断链；递归写法要明确返回新头节点
- 判断环形链表：快慢指针（Floyd 判圈），相遇即有环；进阶问“入口点”，需数学推导后二次相遇
- 合并两个有序链表：虚拟头节点 + 双指针比较，注意处理剩余段，避免空指针访问
斐波那契与动态规划入门
考察递归优化能力，区分暴力、记忆化、迭代三种写法。
立即学习“Python免费学习笔记（深入）”；
- 暴力递归时间复杂度 O(2^n)，明显超时，仅用于引出问题
- 记忆化递归（
@lru_cache或手动 dict 缓存）降为 O(n)，空间 O(n) - 最优是迭代：两个变量滚动更新（
a, b = b, a+b），空间 O(1) - 延伸题如爬楼梯、打家劫舍，思路同源：定义状态、找转移方程、确定初始值
二叉树遍历与递归设计
手写中序/层序遍历最常见，重点在递归终止条件和左右子树处理顺序。
- 中序递归：先左 → 根 → 后右，可用于验证 BST（结果应严格递增）
- 层序遍历（BFS）：用
collections.deque队列，每次取一层长度，避免混淆 while 和 for 层级 - 求最大深度：递归返回
1 + max(left_depth, right_depth)，空节点返回 0 - 避免常见错误：忘记 return、混淆 self 参数（类内方法）、未处理空树边界
字符串处理（有效括号/最长无重复子串）
结合栈和滑动窗口，考察数据结构选择意识。
- 有效括号：用栈存左括号，遇右括号弹出匹配；最终栈空且无非法匹配即有效
- 最长无重复子串：滑动窗口 + 字典记录字符最近位置，
left指针跳到重复字符右侧（取 max 避免回退） - 注意细节：窗口右扩用 for，左缩用 while；字典更新时机在每次右移后，而非仅发现重复时
排序算法手写（快排/归并）
不要求工业级鲁棒，但需逻辑清晰、分区/分治正确。
- 快排：选 pivot（常用首/末/中位数），分区后递归左右子数组；注意
low 终止条件 - 归并：先分到单元素，再合并；合并函数需双指针+临时数组，最后拷回原数组
- 堆排序较少手写，但可提及其基于大顶堆，
heapq是最小堆，需取负模拟
其他高频小题
覆盖语言特性与边界思维。
- 旋转数组找最小值：二分法，比较
mid与right判断哪边有序 - 合并区间：先按 start 排序，遍历中用 last 区间动态合并重叠部分
- 实现 LRU Cache：用
OrderedDict（move_to_end,popitem(last=False)）或手动双向链表+字典 - 判断回文数（不用字符串）：整数反转一半，对比前后半部分（注意奇偶位数）
