数据结构与算法面试题

按分类查阅数据结构与算法面试题，包含参考答案与参考资料。共 6 道题。

• 快速排序和归并排序怎样实现？时间复杂度和稳定性有什么区别？

  快速排序选一个基准，把数组分成比它小和比它大的两部分再递归，平均 O(n log n)，最坏 O(n²)，不稳定。归并排序把数组对半拆到只剩一个元素，再两两有序合并，始终 O(n log n)，稳定但要额外空间。JS 的 Array.prototype.sort 从 ES2019 起要求稳定。

• 怎样反转链表、判断链表有环？

  反转链表用三个指针，一边遍历一边把每个节点的 next 指回前一个节点。判断有环用快慢指针，慢指针每次走一步、快指针走两步，有环就一定会相遇。两种做法都是 O(n) 时间、O(1) 额外空间。

• 动态规划怎么入门？爬楼梯和最长递增子序列怎样做？

  动态规划把大问题拆成重叠的小问题，用数组记住小问题的答案，避免重复计算。写的时候先定义状态 dp[i] 表示什么，再找转移方程和初始值。爬楼梯 dp[i] = dp[i-1] + dp[i-2]；最长递增子序列 dp[i] 是以第 i 个数结尾的最长长度，O(n²)，用二分可以优化到 O(n log n)。

• 两数之和怎样从 O(n²) 优化到 O(n)？哈希表在算法题里怎么用？

  暴力解法是两层循环检查每一对数，O(n²)。用 Map 记录已经看过的数和它的下标，每遇到一个数就查 target 减它的差值在不在 Map 里，一次遍历就够，时间 O(n)，空间 O(n)。这是用空间换时间的典型做法。

• 滑动窗口怎样求无重复字符的最长子串？

  用左右两个指针围出一个窗口，右指针不断向右扩，遇到窗口里已有的字符，就把左指针移到这个字符上次出现位置的后一位。用 Map 记录每个字符最后出现的下标，每个字符最多进出窗口一次，整体 O(n)。

• 二叉树怎样层序遍历、求最大深度？

  层序遍历用队列，每轮先记下当前队列长度，把这一层的节点依次取出，同时把它们的子节点放进队尾，一轮就是一层。最大深度可以递归求左右子树深度的较大值加 1，也可以数层序遍历一共走了几层。