面试复习（算法）

链表有环问题

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

洗牌问题

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

快速排序

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