昨天第一次C++面试，一家小公司，面试官人挺好的，问的都挺简单，但还是因为没面试经验好多自己知道的东西也没全说出来，面试官也没追问，下次面试要自己多说一点，把知道的都尽量说出来。最后问期望薪资把我整懵了，因为确实还没想过这个问题，也才第一次参加面试，不知道行情怎么样，最后还是说了sz至少15k，也不知道是说高了还是低了。先不管这么多了，现在就是把基础知识点常问的查缺补漏多背背多巩固，然后算法继续刷起来，项目之前做的感觉具体实现细节忘了好多，还得再搞搞。现在先把这些准备好后面继续投！

一晃就半个月过去了，元旦的时候外公去世回了家，后面这些天一直在写毕业论文，总算写完了这依托答辩，整整五万字，现在就还差插参考文献，英文论文也是还差个参考文献和投稿的准备，还得再写个cover letter，弄个图形摘要，这些都不算啥。但真的写累了，这两天又被某月亮的面试打乱了计划，还得准备个PPT，太费劲了，但每次机会都得抓住。事情太多了都不知道从哪个下手，有点小烦躁，现在写写总结日记整理一下思绪。首先，应该就剩一个月就得开始投春招了，已经不剩多少时间了，在这期间我得把Qt学一下，然后主要是要复习整理前面学的东西，准备八股，还有就是算法，再就是项目。所以还是不能花太多时间在那个ppt上，最多弄两天吧，然后再把参考文献投稿这些事情搞完，就这个周日之前。下周一就要全身心投入到八股算法。继续加油吧！现在真的很累，但再坚持一下，会有结果的。然后我发现自己还有个问题就是收到面试就会一直想这个事这其实很浪费时间，不能再这样了，做到认真准备就行，但不要想太多抱太大希望。

Floyd多源最短路：思路：动态规划1、grid[i][j][k] = m，表示 节点i 到 节点j 以[1...k] 集合为中间节点的最短距离为m；2、递推公式：节点i 到 节点j 的最短路径经过节点k：grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]节点i 到 节点j 的最短路径不经过节点k：grid[i][j][k] = grid[i][j][k - 1]所以grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1])3、初始化：for(int i = 0; i < m; i++){    cin >> p1 >> p2 >> val;    grid[p1][p2][0] = val;    grid[p2][p1][0] = val; // 注意这里是双向图} 4、遍历顺序：k一定要放在最外层

Bellman_ford 队列优化算法：Bellman_ford 算法每次松弛 都是对所有边进行松弛。但真正有效的松弛，是基于已经计算过的节点在做的松弛；队列优化算法只对 上一次松弛的时候更新过的节点作为出发节点所连接的边 进行松弛，用队列来记录上次松弛的时候更新过的节点。已经在队列里的元素不用重复添加，而从队列里取出的时候，要取消标记。这是因为每个要加入队列的节点，都是一次松弛后得到了更小距离的节点，以它作为出发节点的边也可以获得更小距离。所以如果此时该节点已经再队列里，没有必要再加一次，因为它还没出队更新，一旦出队就会更新好当前情况下的最小距离，但是从队列取出时要取消标记，因为可能该节点的最小距离还会得到更新（找到其它节点到它的路最短），那么以它为出发节点的边也要进行更新！bellman_ford判断负权回路：在有负权回路的情况下，一直都会有更短的最短路，所以松弛第n次，minDist数组也会发生改变所以判断是否有负权回路，就是在松弛n-1次的基础上再多松弛一次，看minDist数组是否发生变化bellman_ford单源有限最短路：计算在最多经过 k 个城市的条件下，从城市 src 到城市 dst 的最低运输成本，最多经过 k 个城市， 那么是 k + 1条边相连的节点，所以本题就是求：起点最多经过k + 1 条边到达终点的最短距离。根据之前对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离得知：对所有边松弛 k + 1次，就是求 起点到达 与起点k + 1条边相连的节点的 最短距离。在有负权回路的情况下，还需要注意使用上次的minDist数组

dijkstra（堆优化版）:从边的数量出发，采用邻接表存储图：vector<list<pair<int,int>>> grid(n + 1)；构建小顶堆来直接选最近结点（不需要循环），优先级队列中存放pair<结点编号，结点到起点的距离>，使用vector<pair<int, int>>作为底层容器,并通过mycomparison类来比较元素；priority_queue<pair<int,int>, vector<pair<int,int>>, mycomparison> pq；时间复杂度：O(ElogE) E 为边的数量Bellman_ford 算法：求带负权值的单向最短路，dijkstra算法只能求权值为非负数的最短路问题。思路：对所有边松弛 n-1 次，然后得出得到终点的最短路径。对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离，松弛就是一次去获取到该结点的最短路径的尝试，因为给出的边规定了哪个结点到哪个结点有路，这说明某次的松弛操作不一定能真正实行，可能起点到某条边的出发结点还未找到最短路，所以要松弛n-1次，才能最终得到起点到终点的最短路。// 松弛操作 // minDist[from] != INT_MAX 防止从未计算过的节点出发if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) {       minDist[to] = minDist[from] + price;  }时间复杂度： O(N * E) , N为节点数量，E为图中边的数量

dijkstra算法求最短路径：与prim算法很相似，步骤几乎一直，但prim求的是所有结点都连通起来的最小值，而dijkstra求的是有向图的起点到终点的最短路径，不需要连通所有结点，所以求结果的过程稍有不同。prim算法中的minDist数组求的是当前结点（还未加入生成树的结点）到现有生成树的最近距离，这个距离会因为每次生成树新节点的加入进行更新），输出结果也是对minDist数组进行累加；而dijkstra算法中minDist数组求的是当前结点到起点（结点1）的最小距离，输出结果就是终点（结点n）到起点的最小距离minDist[n]。//dijkstra三部曲：//1、选起点到哪个节点近且该节点未被访问过//2、对该最近节点标记为已访问//3、更新还未访问节点到起点的距离（即更新minDist数组）拓扑排序：给出一个有向图（具有复杂的依赖关系），把这个有向图转成线性的排序就叫拓扑排序，如大学排课，文件处理等。同时要检测有向图中是否有环，有环则不能得到线性排序，所以拓扑排序也是图论中判断有向无环图的常用方法。思路：1、找到入度为0（出发结点）的结点，加入结果集2、将该结点从图中移除3、循环上面两步，直到图中所有结点都被移除用vector记录每个文件的入度，入度为0的结点存放在queue里，依赖关系放在unordered_map<int, vector<int>>里当构造依赖关系时就将依赖别人的文件入度+1，最后遍历将入度为0的结点加入队列，然后依次将队列里的结点弹出，此时将该节点从图中移除意味着依赖它的结点的入度要-1，并判断是否入度为0，是的话加入队列。判断有 有向环 的存在：如果找不到入度为0的节点了且此时结果集中的元素个数不等于图中结点个数，就说明有环

寻宝：求最小生成树（所有结点的最小连通子图）//prim 算法是维护节点的集合，而 Kruskal 是维护边的集合。//prim算法求最小生成树（所有结点的最小连通子图）//prim三部曲：//1、选距离生成树最近结点//2、最近节点加入最小生成树//3、更新非生成树结点到生成树的最小距离（minDist数组）//kruscal的思路：//1、边的权值排序，因为要优先选最小的边加入到生成树里//2、遍历排序后的边//如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环//如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合//并查集来判断两个节点在不在同一个集合，不在则加入集合个人认为Kruscal算法更简单！时间复杂度也更低！O(nlogn) < O(n^2)

并查集模板：//把并查集的模板函数写好，后面直接调用即可int n;//结点数量（n取题目给出的最大值+1）vector<int> father = vector<int>(n, 0);//初始化void init(){    for(int i = 0; i < n; i++){        father[i] = i;//根节点都初始化为自己    }}//寻根int find(int u){    return u == father[u] ? u : father[u] = find(father[u]);//路径压缩}//判断是否为同一个根bool isSame(int u, int v){    u = find(u);    v = find(v);//这样寻根的同时，也在进行路径压缩    return u == v;}//将两个元素加入一个集合void join(int u, int v){    u = find(u);    v = find(v);    if(u == v) return;    father[v] = u;}

并查集功能：1、寻找根节点，函数：find(int u)，判断这个节点的祖先节点是哪个2、将两个节点接入到同一个集合，函数：join(int u, int v)，将两个节点连在同一个根节点上3、判断两个节点是否在同一个集合，函数：isSame(int u, int v)，就是判断两个节点是不是同一个根节点代码模板：int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好vector<int> father = vector<int> (n, 0); // C++里的一种数组结构// 并查集初始化void init() {    for (int i = 0; i < n; ++i) {        father[i] = i;    }}// 并查集里寻根的过程int find(int u) {    return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩}// 判断 u 和 v是否找到同一个根bool isSame(int u, int v) {    u = find(u);    v = find(v);    return u == v;}// 将v->u 这条边加入并查集void join(int u, int v) {    u = find(u); // 寻找u的根    v = find(v); // 寻找v的根    // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回    if (u == v) return ;     father[v] = u;}今天得开始写毕业论文了，先把框架整理好！最近学了workflow作为客户端和服务端（http服务器和静态资源管理服务器），开始学wfrest包装的workflow作为HTTP服务器，主要是减少了url提取查询参数，方法，路径这些复杂的字符串切割操作，简化了workflow服务端的使用。

字符串接龙：广搜法，因为广搜只要搜到了终点，那么一定是最短的路径。有向图的完全可达性：邻接表记录每个结点可到达的结点编号，visited数组记录所有可访问的结点，递归处理下一个可达结点的标记和再递归。岛屿周长：不需要深搜广搜，直接遍历出0单元格（扩大地图，增加边界外的0，从而记录到边界上陆地的周长），再遍历上下左右四个方向是否与陆地相连，相连则周长+1。

孤岛题（孤岛的最大面积，沉没孤岛）：从四条边开始遍历，对与四条边上的陆地相连的其他陆地（非孤岛）进行标记，最后剩下的仍未1的格子就是孤岛。水流问题：逆流而上！从边界开始遍历！建造最大的公岛：先将每个岛屿贴好标签（岛屿编号），并计算出其面积（unordered_map存放，key为岛屿编号，value为这块岛屿的面积），然后再遍历每个为0的格子，将其变为1，加上其四周岛屿的面积即可。

图论的经典岛屿题，求岛屿个数/最大面积。ACM模式，将题目的输入的岛屿矩阵放入二维数组grid中，并再创建一个标记陆地是否有遍历到的visited二维数组。两层for循环进行处理，如果未标记且为陆地，则调用递归函数（处理的是将与这块陆地相邻的其他陆地全都进行标记），记录结果。

开始图论刷题！先把图论的理论和DFS、BFS的代码框架学了下，刷了一道可达路径。要练习ACM模式，利用邻接矩阵构造了图，深搜法（和回溯差不多）找出所有路径，并输出（循环，打印）。昨天实验室聚餐去了，几个月没去见导师，被训了一下午，开始催我们写毕业论文了。晚上二十个人坐了一个大圆桌，幸好我机智，坐在进门靠左的位置，一上菜就能吃到，这小子真抠门啊，酒水自带就算了，连花生米和冲泡的玉米汁粉都带来了。。后面让我们去加菜，我一点不客气的加了肥肠、滋补羊肉、蒜香排骨。菜上来之后说他从来不吃内脏不吃下水，从小就不吃羊肉。。爱吃不吃，反正我爱吃哈哈！

42、接雨水（超经典）：接雨水就是求凹槽的面积，每一列凹槽的面积由它左边的第一个比它高的柱子和右边第一个比它高的柱子决定的，两者的最小值减去当前列的柱子高度即为凹槽的高度，所以很适合用单调栈求解。单调递增栈，如果新元素比栈顶元素小或相等则入栈（下标入栈），说明还没找到右边第一根比它高的柱子；如果新元素比栈顶元素大，则说明找到了栈顶元素的右边第一根比它高的柱子，左边比它高的柱子则已经在栈里了。84、柱状图中最大的矩形：关键是要找到每根柱子左右两边第一个更小的柱子。单调递减栈：当比栈顶元素大或相等则入栈，小则取栈顶元素作为矩形的高度，宽度则为左右两边更小的柱子的下标差。在数组首尾分别加上0，方便计算宽度