实习面试题index

树

• 前中后序遍历二叉树（计算二叉树节点）
• 哈夫曼树生成

  可以给候选集快排，然后选前2个节点，往后面新增一个节点。节点结构点定义好可以少写些映射关系

排序

• 冒泡排序

  把最大浮到最后面，后界不断减小，一种优化策略是记录最后一个交换的位置，令其为后界（因为此位置后面的数都已有序）

• 快速排序

  Partition不需要额外写个函数，用算法导论上面的非常漂亮https://www.cnblogs.com/pugang/archive/2012/06/27/2565093.html

• 堆排序

  关键是heapify，然后用数组存好，父亲序号与左右儿子的序号关系是恒定的，这点很重要

• 归并排序

动态规划

• 最长上升子序列
• 最长公共子序列

  这个凸显了分解成子问题的思想

• 最长公共子串

  这个跟最长上升子序列极类似：以当前点为终点的XXX

图

• 拓扑排序

  删除入度为0的节点，用栈储存

串

• KMP

  next[i]的意思是pattern[i]失配时，下一个要测试的位置。计算next[i]时，pattern[i]是用来计算next[i + 1]的

• 字符串DP

搜索

• 二分搜索

  不断改变上下界，不需要递归

链表

• 反转单链表

---

• 二维数组中的查找（二分搜索、特题特解）

  右上角或左下角开始