数据结构与算法——二分查找
二分查找 使用二分查找的条件: 单调递增或递减 存在上下界 能够通过索引访问(数组更适合二分查找,链表不适合) 程序模板: left, right = 0, len(array) while left <= right: mid = left + (right - left) // 2 if array[mid] == target: ret…
数据结构与算法———广度与深度优先搜索
广度优先搜索 广度优先搜索(BFS,Breadth First Search) 的一个常见应用是找出从根结点到目标结点的最短路径,其实现用到了队列。下面用一个例子来说明BFS的原理,在下图中,我们BFS 来找出根结点 A 和目标结点 G 之间的最短路径。 首先初始化一个队列Q,将根节点入队:A A出队,将与A相邻的节点入队,此时队列为BCD B出队…
数据结构与算法———哈希
哈希表 哈希表的原理 哈希表是一种使用哈希函数组织数据,以支持快速插入和搜索的数据结构。哈希表由直接寻址表和哈希函数构成。哈希函数$h(K)$将元素关键字$K$作为自变量,返回元素的存储下标。直接寻址表如下所示: $U$为键值的全域,包含了所有可能的键值,$K$为实际使用的键值,$T$为直接寻址表,每个关键字对应表中的一个位置,比如2、3、5、8这…
数据结构与算法——平衡二叉树
平衡二叉树 什么是平衡二叉树: 每个节点的两个子树的高度不会相差超过1。普通树和平衡二叉树的对比: 为什么要用到平衡二叉树: 在二叉搜索树里面,搜索操作的时间复杂度从$O(logN)$到$O(N)$不等,这是一个巨大的性能差异。而平衡的二叉搜索树的搜索复杂度为$O(logN)$。 常见的平衡二叉树的实现: 红黑树、AVL树、伸展树、树堆 判断是否为…
数据结构与算法——十大排序算法
冒泡排序 排序过程: 列表每两个相邻的数,如果前者大于后者,则交换这两个数;遍历列表,完成一趟排序 继续从头遍历,重复上述过程,直到没有发生交换为止 def BubbleSort(a): if len(a) == 0: return None for i in range(len(a) - 1): exchange = False # 标志位,第i…
数据结构与算法———位运算
位运算 位运算: 直接对整数在内存中的二进制位进行操作。比如6的二进制是110,11的二进制是1011,那么6 and 11的结果就是2,它是二进制对应位进行逻辑运算的结果。由于位运算直接在内存数据进行操作,不需要转为十进制,因此速度非常快。 符号 描述 运算规则 & 与 两个都为1时,结果才为1 | 或 两个都为 0时,结果才为1 ^ 异…
数据结构与算法——优先队列
优先队列 优先队列按照队列的方式正常入队,但按照优先级出队。有两种实现方式:堆(二插堆、多项式堆等等)和二叉搜索树。这里重点讲解二叉堆,关于二叉搜索树的内容见这篇文章。 堆是一种特殊的完全二叉树。大根堆: 完全二叉树的任一节点都比其孩子节点大。小根堆: 完全二叉树的任一节点都比其孩子节点小。堆的向下调整: 假设根节点的左右子树都是堆,但根节点不满足…
数据结构与算法——字典树
字典树 字典树(Trie) 又称单词查找树或键树,是一种哈希树的变种。典型的应用是用于统计和排序大量的字符串(但不限于字符串),优点是可以可以最大限度地减少无畏的字符串比较,查询效率比哈希表高。Trie的核心思想是空间换时间,利用字符串的公共前缀来降低查询的时间。 比如有一个包含多个单词的列表:['word', 'work', 'code', 'c…
数据结构与算法——算法复杂度
渐进记号 五种渐进记号 大$O$记号: 对于给定函数$g(n)$,$f(n)=O(g(n))$:存在正常量 $c$ 和 $n_{0}$,使得对所有 $n \geq n_{0}$,有 $0 \leq f(n) \leq cg(n)$成立。$f(n)$ 只有一个渐进上界,$f(n)$ 的阶不高于 $g(n)$ 的阶。 $\Omega$记号: 对于给定函…
数据机构与算法——二叉搜索树
二叉搜索树 二叉搜索树(BST)满足的性质: 每个节点中的值必须大于(或等于)存储在其左侧子树中的任何值。 每个节点中的值必须小于(或等于)存储在其右子树中的任何值。 一个二叉搜索树的例子如下所示: 因为二叉树的中序遍历会得到一个递增的序列,因此在二叉搜索树里中序遍历比较常用。 给定一个二叉树,我们要判断它是否是二叉搜索树。二叉搜索树的特征比较明显…