📝 面试准备 - 算法篇 🌀
记录为面试准备的算法相关内容。
数据结构
基础
Data Structure 数据结构
Arrays 数组
最基础的数据结构。
常考点：
- 找数组中第k大的数字
- 找两个有序数组的中位数
Question:
Leetcode 1: Two Sum 两数之和 [简单] Leetcode 243: Shortest Word Distance 最短单词距离 [简单]
Strings 字符串
Linked Lists 链表
常考点：
- 反转链表
- 链表元素排序
- 合并两个有序链表
- 判断链表是否有环（有环的起始点）
Stacks 栈
Queues 队列
Hash Tables 哈希表
Matrix 矩阵
Trees 树
Binary Search Trees 二叉搜索树
递归思想的数据结构。
常考点：
- 判断二叉树是否平衡
- 判断二叉树是否相同
- 判断二叉树是否对称
Heaps 堆
Graphs 图
Trie 字典树
Union Find 并查集
Algorithms 算法
时间复杂度 空间复杂度
Sorting 排序
Bubble Sort 冒泡排序
通过不断比较相邻元素并在必要时交换它们，将较大的元素逐渐“冒泡”到数组的末尾。 多次遍历数组，每次遍历都将一个最大的元素放到正确的位置。
Binary Search 二分查找
Kadane’s Algorithm 卡丹算法
Tree Traversal 树遍历
in-order 中序遍历
pre-order 前序遍历
post-order 后序遍历
level-order 层序遍历
Graph Algorithms 图算法
DFS/BFS 深度优先搜索/广度优先搜索
Topological Sort 拓扑排序
Minimum Spanning Tree 最小生成树
Dijkstra’s Algorithm 迪杰斯特拉算法
Bellman-Ford Algorithm 贝尔曼-福特算法
Problem-Solving Techniques 解题技巧
Two Pointers 双指针
双指针算法是一种通过维护两个索引（或指针）来解决问题的技术，这些指针通常从数组或字符串的两端开始，根据特定条件向中间移动。
这种方法在排序数组中寻找满足条件的元素对时特别有效，例如寻找和为目标值的两个数。
核心思想：
通过维护两个索引（或指针）来高效地遍历数据结构，减少时间复杂度，通常达到 O(n)
分为：
标准双指针
适用于排序数组，指针从两端开始，根据元素和与目标值的比较移动。
例如，在“两数之和II-输入有序数组”（LeetCode #167）中，初始化一个指针在数组开头，另一个在结尾，调整指针直到找到目标和。典型例题：
- leetcode: 167. Two Sum II - Input Array Is Sorted
- leetcode: 15. 3Sum
- leetcode: 18. 4Sum
- leetcode: 11. Container With Most Water
- leetcode: 75. Sort Colors
- leetcode: 283. Move Zeroes
- leetcode: 26. Remove Duplicates from Sorted Array
复杂度：
- 时间：O(n)
- 空间：O(1)
Sliding Window 滑动窗口
滑动窗口
一种高级双指针变体，用于子数组或子串问题，通过两个指针定义一个窗口，扩展或收缩窗口以满足条件。
例如，“最长不含重复字符的子串”（LeetCode #3）使用滑动窗口找到最长无重复字符的子串。典型例题：
- leetcode: 3. Longest Substring Without Repeating Characters
- leetcode: 76. Minimum Window Substring
复杂度：
- 时间：O(n)
- 空间：O(k),k为窗口内可能包含的唯一元素数
Prefix Sum 前缀和
Monotonic Stack 单调栈
Top k Elements 前k个元素
Fast and Slow Pointers 快慢指针
快慢指针
主要用于链表问题，如检测循环（Floyd 循环检测算法）。快指针每次移动两步，慢指针移动一步，若快指针到达空或相遇则无环，否则有环。
例如，“链表是否有环”（LeetCode #141）中，快指针每次移动两步，慢指针移动一步，如果有环它们会相遇。典型例题：
- leetcode: 141. Linked List Cycle
- leetcode: 876. Middle of the Linked List
复杂度：
- 时间：O(n)
- 空间：O(1)