常见数据结构经典 LeetCode 题目推荐

发表于2019-07-12|计算机基础

|浏览量:

刷数据结构题应围绕“操作成本”展开。数组支持 O(1) 下标访问却不擅长中间插入；链表反之。哈希表用空间换平均常数查找；栈表达后进先出和未完成状态；队列表达层次与到达顺序；堆持续维护极值；树与图表示层级和一般关系。

数组训练可覆盖原地去重、区间合并、前缀和与双指针；链表重点是反转、环、合并和倒数节点；栈适合括号匹配、表达式、单调栈；队列适合 BFS 和滑动窗口；哈希表练计数、去重与映射；树要掌握前中后序、层序、递归信息汇总；图则练连通块、拓扑和最短路；堆用于 Top K 与多路归并。

解题步骤是先列出所需操作：是否频繁查键、取得最值、两端进出、按层扩展或保持有序。再选择让核心操作便宜的数据结构，并核算维护代价。例如优先队列取顶是 O(1)，但插入和删除顶通常是 O(log n)；哈希查找平均 O(1)，并不保证顺序和最坏性能。

训练同一结构时应加入变式：输入是否有序、数据是否流式、能否修改原数组、是否允许额外空间。这样才能理解方案适用范围。实现后至少测试空集合、单元素、重复元素、极值和退化结构。

误区包括按题目名猜结构、只记 API 不懂内部成本、遇到树就递归却忽略栈深，以及为了使用高级结构增加不必要复杂度。小结：数据结构是对操作需求的回答；先明确要快的是哪一种操作，再选容器。

文章作者: Dai Wei

文章链接: https://www.daiwei.biz/knowledge/cs-basics/algorithms/common-data-structures-leetcode-recommendations/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Dai Wei！

数据结构刷题

扫码打赏

微信
支付宝

相关推荐

线性数据结构详解（数组、链表、栈、队列）

线性结构中的元素具有前后次序，但实现方式不同。数组连续存储，可通过地址偏移 O(1) 访问下标，缓存局部性好；中间插删通常要移动元素，为 O(n)。动态数组容量不足时申请更大空间并复制，追加因此是摊还 O(1)。链表把节点分散存放并用指针连接。已知插入位置的前驱时，插删可为 O(1)，但查找第 i 个元素需顺序走 O(n)。双向链表多一个前驱指针，便于从节点本身删除和双向遍历，代价是更多空间与连接维护。栈限制在同一端压入弹出，体现后进先出，适合函数调用、括号匹配、撤销和 DFS。队列从尾部加入、头部移除，体现先进先出，适合任务缓冲与 BFS。循环队列用固定数组和首尾索引复用空间，需要明确“空”和“满”的区分规则；双端队列允许两端操作，可实现滑动窗口。这些结构的端点操作通常 O(1)，但基于数组的队列若每次删除首元素都整体搬移，就会退化；实践中应使用环形索引。链式实现无需整体扩容，却有节点对象和指针开销。误区是说链表插入永远 O(1) 而忽略定位成本、用普通数组首删模拟队列、混淆栈顶和队尾，以及忽略迭代时修改结构的规则。小结：数组优化定位与局部性，链表优化已知位置连接，...

红黑树详解（性质、旋转、应用）

红黑树是带颜色约束的二叉搜索树。节点为红或黑，根和空叶视为黑；红节点不能有红孩子；任一节点到后代空叶的路径包含相同数量黑节点。这些性质使最长路径不超过最短路径约两倍，高度保持 O(log n)。搜索仍按二叉搜索树比较键。插入先作为普通 BST 叶子加入并染红，以免立刻改变黑高；若父节点为红，则出现连续红，需要根据叔节点颜色处理。叔为红时，父与叔染黑、祖父染红并向上继续；叔为黑时，通过左旋或右旋把折线调整为直线，再旋转祖父并交换颜色。旋转只改变局部连接而保持中序次序。左旋让右孩子上升、原节点成为其左孩子；右旋对称。删除更复杂：删除黑节点可能导致某条路径少一个黑色，需要借助兄弟节点颜色、兄弟孩子颜色、旋转和重新着色逐层修复。查找、插入、删除均为 O(log n)，空间为 O(n)。相比 AVL，红黑树平衡条件更宽松，更新时旋转通常较少；AVL 高度更紧，读多写少时可能有优势。它常用于有序映射、集合和内核调度等需要稳定上界的场景。误区是认为红黑树绝对平衡、只背五条性质却不会检查黑高、把旋转当作交换键值，以及忽略父指针和根引用更新。小结：颜色是编码平衡信息，旋转保持排序，重新...

堆详解（最大堆、最小堆、优先队列）

二叉堆是一棵完全二叉树，最大堆要求父节点不小于孩子，最小堆相反。它只保证局部偏序，并不是整体有序。完全树可紧凑地放在数组中：零下标时，节点 i 的孩子为 2i+1 和 2i+2。插入先把新元素放到数组末尾，再与父节点比较并上浮；删除堆顶时，用末尾元素覆盖根，缩短数组，再与更合适的孩子交换并下沉。树高为 O(log n)，因此插入和删除顶都是 O(log n)，读取堆顶为 O(1)。从无序数组建堆不必逐个插入。可从最后一个非叶节点开始向前下沉，虽然单次下沉最高 O(log n)，但大量底层节点移动很短，合计为 O(n)。堆排序建最大堆后反复把根换到末尾并缩小堆区，时间 O(n log n)、额外空间 O(1)，但通常不稳定。优先队列是抽象接口，堆是常用实现。Top K、任务调度、多路归并和 Dijkstra 都可使用它。若需更新任意元素优先级，普通堆还需要位置索引，或采取重复入堆并在弹出时丢弃旧记录。误区是认为遍历堆会得到有序序列、混淆最大 K 与堆方向、把建堆写成 O(n log n)、修改比较器依赖的字段后不重建，以及忘记空堆检查。小结：堆擅长反复取得一个极值，不擅...

哈希表面试题总结：哈希冲突、扩容与 Java HashMap

哈希表先把键经哈希函数转换为整数，再映射到桶。理想情况下只需定位一个桶，因此查询、插入和删除平均接近 O(1)。哈希函数应稳定、计算快且分布均匀，但不同键映射到同一桶的冲突不可完全避免。拉链法让每个桶保存链表或树，冲突元素在桶内继续比较；开放寻址法则按探测规则寻找其他空位。负载因子表示元素数与桶数的比例，过高会增加冲突。超过阈值时通常申请更大数组并重新分布元素，扩容单次为 O(n)，但分摊到多次插入后仍可视作摊还常数。 Java HashMap 的键必须遵守 equals 与 hashCode 契约：相等对象必须有相同哈希值，反之不一定成立。可变对象若作为键后改变参与哈希的字段，可能再也无法按新状态找到原条目。JDK 8 的桶在冲突链较长且容量达到条件时可树化，以改善极端查询，但这不意味着所有操作绝对常数。查询步骤是计算扰动后的哈希、定位桶、再逐个或按树比较哈希和键；因此平均复杂度依赖分布和扩容策略，最坏情况仍需结合实现说明。空间通常为 O(n+桶数)。常见误区是把哈希等同加密、认为无冲突、忽略扩容停顿、依赖遍历顺序，以及在并发写入时直接共享普通 HashMap。小结：...

经典算法思想总结（含 LeetCode 题目推荐）

经典题的价值是覆盖可复用思想，而非提供待背答案。二分利用单调性缩小范围；分治把问题拆成独立子问题再合并；回溯枚举决策树；贪心做可证明安全的局部选择；动态规划缓存重复状态；DFS 与 BFS 负责遍历隐式或显式图。训练时可按“识别—实现—证明—变式”推进。看到有序数组，先问能否二分或双指针；看到连续区间，考虑滑动窗口、前缀和；看到前 K 个，比较堆和快速选择；看到连通关系，考虑 DFS、BFS、并查集；看到最少次数，判断是否是无权最短路或 DP；看到所有组合，则画回溯树。每题先给出暴力解和复杂度，再定位瓶颈。例如重复查询区间和，可用前缀和把单次查询从 O(n) 降为 O(1)，代价是 O(n) 预处理与空间；重复求同一递归状态，可记忆化；每次扫描极值，可用堆或单调结构。优化必须说明利用了何种约束。复盘记录应包含：题目模型、关键不变量、易错边界、时间空间复杂度，以及如果条件变化方案会怎样。隔几天脱离答案重写，比连续刷相似题更能检验迁移能力。误区是以题号替代知识结构、只追求最优代码、忽略数据规模提示，以及把模板当作正确性证明。小结：经典题应成为概念索引。能用自己的话说明为什...

Redis 5 种基本数据类型详解

选对数据结构等于选对时间复杂度。五种基础类型覆盖大部分业务缓存与计数场景。 String二进制安全字符串，可存 JSON、计数、分布式锁（SET NX EX）。INCR 原子计数；GETSET 可用于简单轮换。 List双端链表，LPUSH/RPOP 做队列；注意中间查找 O(n)，长列表慎用。 Hash字段级更新，适合对象缓存（用户 profile）。小 hash 用 ziplist/listpack 省内存。 Set去重集合，SADD/SISMEMBER O(1)；交集可用于共同好友。 Sorted Set带 score 有序集合，排行榜、延迟队列（score=时间戳）。底层跳表+哈希表。 12ZADD rank 980 user:1001ZRANGE rank 0 9 WITHSCORES REV 编码转换阈值ziplist/listpack 与 hashtable 转换阈值由配置项控制；升级版本阈值变化可能导致内存突增。管道 pipeline批量命令减少 RTT；注意非事务场景下部分失败的处理。实践复习清单五类型...

评论

数据加载中