算法笔试练习

记录笔试中常用的题目类型、数据结构、算法以及一些编程小技巧。示例代码为C++。

链表

栈

队列

字符串处理

位运算

图

深度优先遍历

广度优先遍历

广度优先遍历能够用于解决两个节点之间的最短路径问题（走过的路数量最少，并不是指走过的路程最少，后者问题存在于带权图中）。

  1. 初始化访问队列（存储需要访问的元素），访问标记（bool 数组，使用下标区分元素）。
  2. 将开始节点入队，并标记为已访问。（加入队列时便将其标记，而不是出队时。）
  3. 遍历访问队列，将出队元素相连的元素加入到队列中（有些情况下需要考虑到入队顺序），并将其标记为已访问。
  4. 访问队列为空时表示遍历完毕。

以上此种方案只能用于单纯的遍历问题中，对于需要获取遍历层数时需要两个队列共同作用。

回溯

贪心

动态规划

动态规划Dynamic Programming 将需要解决的问题分解为简单的子问题，通过一步步对这些子问题的求解最终完成最终问题的求解。