数据结构和算法

红黑树（map）

一种自平衡二叉搜索树，保证插入、删除、查找操作的时间复杂度为O(log n)。

• 特点：每个节点有红黑两种颜色，根节点为黑色，红色节点的子节点为黑色，任意节点到叶子节点的路径上黑色节点数量相同。
• 适用场景：需要快速查找、插入、删除操作的应用，如关联容器map、set。

Hash表的实现（能手写）

通过数组和链表实现，解决冲突的方法有链地址法、开放地址法。

• 链地址法：每个数组元素是一个链表，冲突时将元素插入链表。
• 开放地址法：冲突时寻找下一个空闲位置，常用方法有线性探测、二次探测、双重散列。

树的遍历(深度优先和宽度优先)

• 深度优先：前序、中序、后序遍历。
  • 前序遍历：根节点 -> 左子树 -> 右子树。
  • 中序遍历：左子树 -> 根节点 -> 右子树。
  • 后序遍历：左子树 -> 右子树 -> 根节点。
• 宽度优先：层次遍历。
  • 层次遍历：按层次从上到下、从左到右遍历节点。

跳跃表的实现

一种随机化的数据结构，支持快速查找、插入、删除操作。

• 特点：在有序链表的基础上增加多级索引，索引层数随机生成。
• 适用场景：需要快速查找、插入、删除操作的应用，如Redis的有序集合。

动态规划题目

通过分解问题、保存子问题的解来解决复杂问题。

• 特点：将问题分解为子问题，保存子问题的解，避免重复计算。
• 适用场景：最优子结构、重叠子问题的应用，如背包问题、最长公共子序列。

字符串最长匹配

常用算法有KMP、Boyer-Moore、Rabin-Karp。

• KMP：通过部分匹配表加速匹配过程。
• Boyer-Moore：从右向左匹配，利用不匹配字符跳跃。
• Rabin-Karp：利用哈希函数比较子串。

链表的操作

单链表、双链表、循环链表的插入、删除、查找操作。

• 单链表：每个节点包含数据和指向下一个节点的指针。
• 双链表：每个节点包含数据、指向下一个节点和上一个节点的指针。
• 循环链表：尾节点指向头节点，形成环形结构。