面试复习（算法）

链表有环问题

• 判断单向链表是否有环
  • 定义两个指针，从链表的开始，同时沿着链表指针移动，速度分别为一个单位和两个单位。当某个时刻，两个指针指向同一个节点的时候则此链表有环
  • 理论上，速度可以是任意的两个不同的值，因为只要速度差和环的长度有最小公倍数，则必定存在相交的时间点
• 找出链表的环的交点位置
  • 通过上述步骤（速度取一步两步），当两个指针第一次相遇的时候，将速度为二步的指针移动至开头，并将速度调整为一步，然后两个指针继续前进，直到第一次相遇，此相遇点即为链表的环的交点
  • 原理：把整个链表认为长度就是两步的那个指针所走过的路程，把重复的那部分复制一份，将链表展开为无环。此时可以认为整个链表长度为 $2n$，且一步的那个指针恰好位于整个链表最中间的地方，即 $n$，同时，在展开之前，这两个节点是“相同的节点”，此时如果再有一个指针以一步的速度从开头开始走，那么当这两个指针分别走到链表的正中间和最后的时候，此时这两个指针实际上相同了，而这两个指针速度相同，所以在之前应该也有一段时间已经相同了。反过来，当他们第一次重合的时候，即为环的入口
• 判断两个链表是否最终交在同一个节点
  • 利用上述的规则，将其中一个链表的头尾相连，然后从另一个链表开头进行一步两步的判断

洗牌问题

• 问题样式
  • 在 $$ 个不相同的数中随机取出 $$ 个数，使得这 $$ 个数字不同
  • 一个长度为 $$ 的数组，将其打散
• 解题方法
  • Fisher-Yates Shuffle算法
    • 优点：逻辑简单
    • 缺点：时间复杂度高($$)，空间复杂度也较高($$)，而且需要提前知道数组长度
    • 1. 设定 $$
    • 1. 获得一个在 $$ 之间的随机数 $$
    • 1. 将原数组中第 $$ 个没有被取出的数据拿出
    • 1. 使得 $$
    • 1. 重复 2-4 步直到取出 $$ 个整数
  • Knuth-Durstenfeld Shuffle算法
    • 优点：时间复杂度($$)和空间复杂度($$)都低
    • 缺点：会修改原数组，而且需要提前知道数组长度
    • 1. 设定 $$
    • 1. 获得一个在 $$ 之间的随机数 $$
    • 1. 交换数组中的第 $$ 个和第 $$ 个值
    • 1. 使得 $$
    • 1. 重复 2-4 步直到 $$
  • Inside-Out Algorithm算法
    • 优点：时间复杂度($$)低，不需要提前知道数组长度
    • 缺点：空间复杂度高($$)
    • 1. 将整个数据拷贝至一个新的数组 $$
    • 1. 设定 $$
    • 1. 获取一个在 $$ 之间的随机数 $$
    • 1. 交换 $$ 和 $$
    • 1. 使得 $$
    • 1. 重复 3-5 步直到 $$

快速排序

• 快速排序的实现
• 快速排序的优缺点
  • 优点：平均时间复杂度 $$，空间复杂度 $$
  • 缺点：不稳定，初始序列有序或基本有序时，时间复杂度降为 $$