算法是解决问题的步骤和方法,是编程和解决问题的核心工具。掌握这些内容,能够帮助开发者高效地解决实际问题,并优化程序的性能。常见的算法包括:
1. 排序算法
比较排序:
冒泡排序(Bubble Sort)选择排序(Selection Sort)插入排序(Insertion Sort)快速排序(Quick Sort)归并排序(Merge Sort)堆排序(Heap Sort)
非比较排序:
计数排序(Counting Sort)桶排序(Bucket Sort)基数排序(Radix Sort)
2. 搜索算法
线性搜索(Linear Search):遍历查找。二分搜索(Binary Search):适用于有序数组。深度优先搜索(DFS):用于树或图的遍历。广度优先搜索(BFS):用于树或图的遍历。
3. 图算法
最短路径算法:
Dijkstra 算法Bellman-Ford 算法Floyd-Warshall 算法
最小生成树算法:
Kruskal 算法Prim 算法
拓扑排序(Topological Sort):用于有向无环图(DAG)。强连通分量(Strongly Connected Components, SCC):Kosaraju 算法或 Tarjan 算法。
4. 动态规划(Dynamic Programming, DP)
经典问题:
斐波那契数列背包问题(0-1 背包、完全背包)最长公共子序列(LCS)最长递增子序列(LIS)矩阵链乘法编辑距离(Edit Distance)
5. 贪心算法(Greedy Algorithm)
经典问题:
活动选择问题霍夫曼编码(Huffman Coding)最小生成树(Kruskal 和 Prim 算法)
6. 分治算法(Divide and Conquer)
经典问题:
归并排序快速排序大整数乘法最近点对问题
7. 回溯算法(Backtracking)
经典问题:
N 皇后问题数独求解全排列问题子集问题
8. 字符串算法
模式匹配:
KMP 算法Boyer-Moore 算法Rabin-Karp 算法
字符串处理:
最长回文子串(Manacher 算法)字符串哈希
9. 数学与数论算法
最大公约数(GCD):欧几里得算法。素数检测:试除法、Miller-Rabin 算法。快速幂算法:用于高效计算幂运算。
10. 其他算法
滑动窗口(Sliding Window):用于解决子数组或子字符串问题。双指针(Two Pointers):用于数组或链表的遍历。位运算(Bit Manipulation):用于高效处理二进制数据。
三、算法分析
时间复杂度:衡量算法运行时间的增长趋势。空间复杂度:衡量算法所需内存的增长趋势。渐进符号:大 O 符号(O)、大 Ω 符号(Ω)、大 Θ 符号(Θ)。
四、经典问题
数组与链表:
两数之和反转链表合并两个有序链表
树与图:
二叉树遍历(前序、中序、后序)二叉树的最近公共祖先(LCA)图的连通性
动态规划:
爬楼梯问题零钱兑换问题最长回文子串
贪心算法:
分配饼干跳跃游戏
回溯算法:
组合总和括号生成