数据结构与算法入门手册

第一部分:算法概述

1. 算法定义:一系列解决问题的清晰易行的步骤和规则。以编程实现,输入为问题实例,输出为问题解。
2. 算法特征:输入、输出、有穷性、确定性、可行性。算法必须有清晰的输入与输出,步骤必须能在有限时间内结束,为任意输入都可以给出解,并且解得出的结果是正确的。
3. 算法类族:递归算法、迭代算法、确定算法、非确定算法、Exact算法、Heuristic算法等。递归算法通过递归解决子问题,迭代通过循环;确定算法对每组输入都给出同样的输出,非确定算法输出随输入变化。Exact算法可以给出最优解,Heuristic算法可以给出可行解。
   第二部分:常用算法类型

1. 递归算法:子问题的解决依赖于递归算法,典型例子阶乘函数、斐波那契数列。需设置终止条件,否则会出现栈溢出。
2. 贪心算法:在当前选项中做最佳选择,典型例子硬币找零、最小生成树。通过局部最优解得到全局最优,但不一定最优,需证明贪心策略的正确性。
3. 分治算法:通过递归将问题划分为相同或相似的子问题,典型例子二分查找、快速排序。需合并子问题解为原问题解,通常更高效。
4. 动态规划:通过拆分为子问题并保存子问题解避免重复计算,典型例子背包问题、最长公共子序列。需定义状态转移方程并初始化 base case。
   第三部分:算法面试常考点

1. 排序算法:时间复杂度与稳定性比较,原地排序与非原地排序。
2. 链表:插入、删除、查找、反转操作实现与时间复杂度分析。
3. 字符串:KMP算法原理与实现、最长公共子串算法实现与优化、回文字符串算法实现。
4. 二叉树:递归与迭代方式实现前序、中序与后序遍历,层次遍历的队列实现。
   5.图的搜索:BFS与DFS实现与应用场景对比,最短路径算法如Dijkstra算法与Floyd算法。
5. 其他:哈希表的冲突解决方法、堆的实现与应用。
   第四部分:算法学习资料与建议
6. 网站:Leetcode、HackerRank、Lintcode、Topcoder 等。
7. 书籍:《算法导论》、《剑指Offer》、《编程之美》等。
8. 建议:不怕难、多练习、总结规律、编写博客、参加交流。
9. 递归算法:通过递归解决子问题,典型例子阶乘函数、斐波那契数列。需设置终止条件,否则栈溢出。
   阶乘函数:int factorial(int n) {if (n == 1) return 1; else return n * factorial(n-1);}
   斐波那契数列:int fib(int n) {if (n == 1 || n == 2) return 1; else return fib(n-1) + fib(n-2);}
10. 贪心算法:在当前做最佳选择,典型例子硬币找零、最小生成树。通过局部最优取得全局最优,不一定最优,需证明贪心策略正确。
    硬币找零:每次取面值最大的硬币,直到零钱数为0。
    Prim算法:每次选取与当前树相连的权值最小的边,直到所有点被选取。
11. 分治算法:通过递归将问题划分为相同或相似子问题,典型例子二分查找、快速排序。需合并子问题解为原问题解,通常更高效。
    二分查找:在有序数组中查找目标值,每次比较中间元素,递归左区间或右区间。
    快速排序:从数组中选取一个pivot,小于pivot放左区间,大于pivot放右区间,递归左区间和右区间。
12. 动态规划:通过拆分为子问题并保存子问题解避免重复计算,典型例子背包问题、最长公共子序列。需定义状态转移方程并初始化base case。
    背包问题:物品有重量和价值,在一定容量下选择最大价值。状态转移方程:dpi=max(dpi-1, dpi-1j-wi]+vi)
    最长公共子序列:两个序列的最长公共子序列。状态转移方程:dpi=dpi-1+1 (if Ai==Bj) dpi=max(dpi-1, dpi)
13. 数组:定长顺序存储,支持快速查找、插入和删除,适用于静态数据。 实现:int arr10; arr0=1; arr1=2;
14. 链表:动态非顺序存储,节点包含值和指针,单向链表/双向链表/循环链表。适用于动态数据,插入和删除快,查找慢。
    单向链表节点:struct Node {int val; Node *next;}
    插入:node->next=head; head=node;
    7.栈和队列:栈遵循后进先出,队列遵循先进先出。应用场景不同,实现类似。
    栈:void push(int); int pop(); 队列:void push(int); int pop();

1. 二叉树:节点最多两个子节点,适用于表示层次关系。递归实现前序、中序和后序遍历。
   1
   /
   2 3
   /
   4 5
   前序遍历:1 2 4 5 3
   中序遍历:4 2 1 5 3
   后序遍历:4 5 2 3 1
2. 哈希表:通过散列函数映射键值对,支持快速添加、删除和查找。解决冲突常用开放定址法与链地址法。
   开放定址法:发生冲突时探测下一空槽位。
   链地址法:发生冲突时将该键值对链入链表。
3. 堆:完全二叉树,支持快速添加、删除和获取最大/小值。可实现优先队列。
   大根堆:父节点值大于子节点,getMaximum()在O(1)时间内返回最大值。
   小根堆:父节点值小于子节点,getMinimum()在O(1)时间内返回最小值。
4. 字符串匹配:通过模式串在文本串中寻找其出现位置。KMP算法优化了暴力匹配算法。
   KMP算法:通过生成前缀函数 skipi表示模式串中i之前的字符串中最长的相同前后缀长度, 降低回溯次数。
5. 排序:给元素序列按一定顺序进行排列。
   冒泡排序:第i趟将第i大的数沉到底 O(n2) 稳定
   快速排序:选定pivot,小于pivot放左边,大于pivot放右边。递归调用 O(nlogn) 不稳定
   归并排序:递归地拆分序列,合并有序子序列 O(nlogn) 稳定
6. 最短路径:寻找图中两个节点之间的最短路径长度。Dijkstra算法与Floyd算法。
   Dijkstra算法:从起点开始向外扩展,每次选取距离起点最近的未选定点,直到扩展到终点。适用于有向图。
   Floyd算法:通过填充dpi表示i到j的最短路径,遍历所有点作为中间点更新最短路径。适用于无向图
   算法入门手册.pdf
   谷歌高畅Leetcode刷题笔记.pdf
   点击个人头像主页进入博客获取