算法面试到底是什么鬼？ 1-1 算法面试不仅仅是正确的回答问题 算法面试的目的 展现思考问题的方式 算法面试过程 看做是和面试官一起探讨一个问题的解决方案。对于问题的细节和应用环境，可以和面试官沟通。 这种沟通本身很重要，它暗示着你思考问题的方式。 我们需要对一组数据进行排序。 快速排序算法 O(nlogn) 正确+更优 这组数据有什么样的特征？ 有没有可能包含有大量的重复元素？ 如果有这种可能的话，三路快排是更好的选择。 Java 默认是三路快排。 这组数据有什么样的特征？ 是否大部分数据距离它的正确位置很近？是否近乎有序？ 如果是这样的话插入排序更优 是否数据的取值范围非常有限？比如学生成绩排序。 计数排序更优 对排序有什么额外的要求 是否需要稳定排序 归并排序更优 数据的存储状况是怎样的 如果使用链表存储，归并排序更优 数据的大小是否可以装在内存里， 外部排序 什么是正确的回答一个算法问题 正确还包含对问题的独到见解，容错性， 1-2 算法面试只是面试的一部分 算法面试优秀不意味着技术面试优秀 算法面试只是技术面试的一部分 项目经历和项目中遇到的实际问题 你遇到印象最深的bug是什么？ 面向对象 设计模式 网络相关：安全相关，内存相关，并发相关 系统设计： scalability 面试不仅仅是考察技术水平，以及对过去项目的思考 项目经历 通过过去了解你的思考行为方式 遇到的最大的挑战 犯过的错误 遇到的失败 最享受的工作内容 遇到冲突的处理方式 做的最与众不同的事儿 准备好合适的问题问面试官 1-3 如何准备算法面试 避免完美学习 使用时间片学习 远远不需要达到竞赛的水平 不要轻视基础算法和数据结构，而只关注有意思的题目 各种排序算法 技术数据结构和算法的实现： 如堆，二叉树，图 基础数据结构的使用： 如链表、栈、队列、哈希表、图、Tire、并查集 基础算法： 深度优先、广度优先、二分查找、递归 基本算法思想：递归、分治、回溯搜索、贪心、动态规划 选择合适的OJ online judge leetcode： online portal for interview

二叉树和递归 二叉树天然的递归结构 满二叉树 二叉树的前序遍历 递归实现 1void preOrder(TreeNode node){ 2 if(node==null){ 3 return; // 递归终止条件 4 } 5 System.out.print(node.val); 6 preOrder(node.left); // 递归过程 7 preOrder(node.right); 8} 二叉树的定义：空是一棵二叉树 二叉树总是否包含某个key 1boolean contain(TreeNode node, Key key){ 2 if(node == null){ 3 return false; 4 } 5 if(key == node.key){ 6 return true; 7 } 8 if(contain(node.left,key)|| contain(node.right, key)){ 9 return true; 10 } 11 return false; 12} 1// c++ 释放二叉树的内存 2void destory(TreeNode node){ 3 if(node == null){ 4 return; 5 } 6 destory(node.

动态规划基础 什么是动态规划 斐波那契数列 Fibonacci Sequence 1//时间复杂度 应该是指数级 2int fib(){ 3 if(n==0){ 4 return 0; 5 } 6 if(n==1){ 7 return 1; 8 } 9 return fib(n-1)+fib(n-2); 10} 递归会有很多的重复计算，重复的计算量会非常大。 所以想办法对重复的计算 只计算一次 记忆化搜索-自上而下的解决问题 改进的Fibonacci 1// 记忆化搜索 时间复杂度O(n) 2int memo[]; 3int fib(){ 4 if(n==0){ 5 return 0; 6 } 7 if(n==1){ 8 return 1; 9 } 10 if(memo[n]==-1){ 11 memo[n]=fib(n-1)+fib(n-2); 12 } 13 return memo[n]; 14} 动态规划-自下而上的解决问题 1// 动态规划 2int fib(int n){ 3 vector<int> memo(n+1, -1); 4 memo[0] = 0; 5 memo[1] = 1; 6 for(int i=2; i<n;i++){ 7 memo[i] = memo[i-1]+memo[i-2]; 8 } 9 return memo[n]; 10} 动态规划：

图 图的表示 邻接矩阵（Adjacent Matrix） 邻接表（Adjacent Matrix） 邻接表适合表示稀疏图（Sparse Graph） 邻接矩阵适合表示稠密图（Dense Graph） 稀疏图 稠密图和完全图 寻路 获得两点之间的一条路径 图的深度优先遍历-时间复杂度 稀疏图（邻接表）：O(V+E) 稠密图（邻接矩阵）：O(v^2^) 深度优先遍历算法-有向图 dfs 查看是否有环- 有向图 广度优先遍历和最短路径 借助队列实现 广度优先遍历求出了无权图的最短路径 图的广度优先遍历-时间复杂度 稀疏图（邻接表）：O(V+E) 稠密图（邻接矩阵）：O(v^2^) 无权图的应用- 迷宫生成，PS抠图 flood fill 魔棒抠图 连通分量 扫雷 走迷宫、 迷宫生成 迷宫的本质是一棵树 本质是一个生成树的过程 不能只用一种方式遍历， 随机队列遍历 欧拉路径 哈密尔顿路径 二分图 同学选课 地图着色

最小生成树 Minimum Span Tree 有权图 Weight Graph 邻接矩阵 Adjacent Matrix 邻接表 使用Edge 表示每一条连接边 最小生成树问题和切分定理 带权无向图、连通图 找V-1条边 切分定理 Cut Property 把图中的节点分成两部分，成为一个切分(Cut) 如果一个边的两个端点，属于切分不同的两边，这个边成为横切边(Crossing Edge); 切分定理： 给定任意切分，横切边中权值最小的边必然属于最小生成树 Prim算法 Lazy Prim Lazy Prim 最小堆中依然有不会是横切边的边。 Lazy Prim 的时间复杂度为O(ElogE) Prim 算法优化 时间复杂度O(ElogV) IndexMinHeap Kruskal算法 使用并查集 使用Union Find 快速判断环 最小生成树问题 最小生成树问题思考 Lazy Prim O(ElogE) Prim O(ElogV) Kruskal O(ElogE) 如果横切边有相等的边 根据具体的算法实现，每次选择一个边 此时，图存在多个最小生成树 Vyssotsky’s Algorithm 将边逐渐添加到生成树中 一旦形成环，删除环中权值最大的边

最短路径 路径最短问题和松弛操作（Relaxation） 最短路径问题 Shortest Path 路径规划 城市，路由 工作任务规划 广度优先遍历 -> 最短路径树 Shortest Path Tree 单源最短路径 Single Source Shortest Path 无权图的最短路径 松弛操作是求最短路径的核心 Dijkstra 算法的思想 dijkstra 单源最短路径算法 前提： 图中不能有负权边 复杂度 O(ElogV) 负权边和Bellman-Ford算法 拥有负权环的图，没有最短路径 Bellman-Ford 单源最短路径算法 前提：图中不能有负权环 Bellman-Ford 判断图中是否有负权环 复杂度O(EV) 如果一个图没有负权环，从一个点到另一个点的最短路径，最多经过所有的V个顶线，有V-1条边。否则存在定点经过了两次，即存在负权环。 对一个点的一次松弛操作，就是找到经过这个点的另外一条路径，多一条边，权值更小。 如果一个图没有负权环，从一个点到另外一个点的最短路径，最多经过所有的V个顶线，有V-1条边。 对所有的点进行V-1次松弛操作。 对所有的点进程V-1次松弛操作，理论上就找到了从源点到其他所有点的最短路径。 如果还可以继续松弛，就说明原图中有负权环 ##更多和最短路径相关的思考

imooc_算法与数据结构综合提升篇

二叉树的序列化和反序列化 二叉树->

CAS 和 ABA 问题 在多并发程序设计中，我们不得不面对并发、互斥、竞争、死锁、资源抢占等问题，归根结底就是读写的问题，有了读写才有增删改查，才有一切。同样也有了谁读谁写、这样的顺序和主次问题，于是就有了上锁，乐观锁和悲观锁、同步和异步、睡眠和换入换出等问题，归根结底就是模拟了社会的分工协作与资源共享的抢占，要理解好这些现象的本质，我们需要更加深刻的进行类比和辨析。要知道这些内容的本质就是内存和CPU之间的故事，有时候还会有一些外存和其他缓存。 https://www.cnblogs.com/zyrblog/p/9864932.html

RandomAccessFile 不同于FileInputStream和FileOutputStream,不是他们的子类 当我们想对一个文件进行读写操作的时候，创建一个指向该文件的RandomAccessFile流就可以了 ； 但是对于OutputStream和DataOutputStream，我们在使用的时候都是通过他们的构造方法来附加或更新文件，即在构造方法中new FileOutputStream；