美团 - 如何实现一个有序链表能够进行“二分“查找？ 对于一个有序数组，如果要查找其中的一个数，我们可以使用二分查找(Binary Search)算法，将它的时间复杂度降低为O(logn)。那查找一个有序链表，有没有办法将其时间复杂度也降低为O(logn)呢？ 跳表(skip list) 全称为跳跃链表， 实质上就是一种可以进行二分查找的有序链表，它允许快速

图 - 最短路径（Dijkstra 和 Frolyd） "最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。" 从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小，例：公交查询系统。 问题解法： 1. 求从某个源点到其余各点的最短路径

数据结构基础 - 知识体系 数据结构的作用 数据结构实际上可以理解为数据在计算机中的存储和使用结构。如果借助C++容器的概念，数据结构可以认为是以某种特定的布局方式存储数据的容器。 这种“布局方式”决定了数据结构对于某些操作是高效的，而对于其他操作则是低效的。首先我们需要理解各种数据结构，才能在处理实际问题时选取最合适的数据结构。不同的数据结构适用于不同的应

图 - 最小生成树（Kruskal和Prim） "在给定一张无向图，如果在它的子图中，任意两个顶点都是互相连通，并且是一个树结构，那么这棵树叫做生成树。当连接顶点之间的图有权重时，权重之和最小的树结构为最小生成树！" 在实际中，这种算法的应用非常广泛，比如我们需要在n个城市铺设电缆，则需要n-1条通信线路，那么我们如何铺设可以使得电缆最短呢？最小生成树就是为

图 - 拓扑排序（Topological sort） 什么是拓扑排序？ 维基百科对于拓扑排序有如下定义： "a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every direct

排序 - 常见排序算法知识体系详解 排序算法介绍 排序算法是《数据结构与算法》中最基本的算法之一。 排序是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素某个相知有序的序列。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要