网站开发架构mvc,中国住房和建设部网站,网页设计的岗位叫什么,域名时间与网站优化数据结构 线性表包括顺序表和链表#xff0c;python的list是顺序表#xff0c;链表一般在动态语言中不会使用。不过链表还是会出现在各种算法题中。 链表 link list 单链表 逆转链表#xff1a; leetcode 206双链表循环单链表字符串 string 有一个重要的点就是字符串的匹配问…数据结构 线性表包括顺序表和链表python的list是顺序表链表一般在动态语言中不会使用。不过链表还是会出现在各种算法题中。 链表 link list 单链表 逆转链表 leetcode 206双链表循环单链表字符串 string 有一个重要的点就是字符串的匹配问题其中比较重要的是无回溯匹配算法(KMP算法)算法比较复杂重要的思想在于匹配过程中不回溯。实际复杂度是O(mn), m和n分别是匹配模式串和目标串一般mn。 通配符 *和? * 匹配任意一个字符串匹配任意一个字符正则表达式内容很多这里就不讲了 原始字符串在字符串前面加r前缀,\不作为转义符栈 stack 队列 queue python3有内置的实现模块 二叉树 基本概念路径长度层数。都比较好理解。 root的层数为0。 二叉树的性质 性质6.1在非空二叉树第i层中最多有2^i个节点性质6.2高度为h的二叉树最多有2^(h1)-1个节点性质6.2对于任何非空二叉树如果其叶节点的个数为n0,度数为2的节点个数为n2,那么n0n21 满二叉树所有分支节点的度数都是2性质6.4: 满二叉树的叶节点比分支节点多一个 扩充二叉树把一个二叉树的所有节点变成度数为2的节点就是这棵树长了一圈叶子旧节点叫内部节点新节点叫外部节点。性质6.5扩充二叉树的外部路径长度叫E, 内部路径长度叫I, n是内部节点数量 EI2*n 完全二叉树0-(h-1)层的节点都满并且最后一层的节点都在左边。性质6.6完全二叉树节点数为n则高度hfloor(log2n)性质6.7完全二叉树节点数为n, 并从0开始编号按层次按左右 root的编号是0i的父节点是floor((i-1)/2)if 2i1n, 则其left child: 2i1 else 无left childif 2i2n, 则其right chiild: 2i 2 else 无right child 完全二叉树到线性结构有自然的双向映射深度优先遍历 depth first traversal, depth first search, DFS 先根序遍历DLR中根序遍历LDR后根序遍历LRD宽度(广度)优先遍历, Breadth First Search, BFS实现BFS一般要用到一个队列先根序DFT def preorder(t, proc):if not t:return Noneproc(t.val)preorder(t.left)preorder(t.right) 广度优先遍历 BFS def levelorder(t, proc_):q Queue()q.put(t)while not q.empty():n q.get()if not n:continueq.put(n.left)q.put(n.right)proc_(n.val) 合并两个二叉树leetcode 617堆一个完全二叉树并且任意一个节点存放的数据先于其子节点的数据 小顶堆 大顶堆 堆和完全二叉树 堆一个元素 -完全二叉树堆 去掉root 生成两个堆上面得到的两个堆新的root - 完全二叉树堆去掉最后一个节点还是堆 堆可以用来构建优先队列(py3已经实现了) 由堆实现的优先队列创建的时间复杂度是O(n)插入和弹出是O(logn) 堆还可以用来排序heap sort python实现 def heap_sort(nums_):def siftdown(nums_i, e, begin, end):i beginj begin*21while j end:if j 1 end and nums_i[j1] nums_i[j]:j 1if e nums_i[j]:breaknums_i[i] nums_i[j]i jj 2*j1nums_i[i] eend len(nums_)for k in range(end//2, -1, -1):siftdown(nums_, nums_[k], k, end)for k in range((end-1), 0, -1):e nums_[k]nums_[k] nums_[0]siftdown(nums_, e, 0, k)return nums_[::-1] heap sort c实现 序列是数组c堆排序 排序算法 sort algorithm 内排序在内存上排序外排序 归并是外排序的基础 原地排序算法空间复杂度为O(1)稳定性 就是原序列里有一些Key一样的元素排序之后能否保持不改变这部分序列的相对顺序。 比如key-value pair按照key 排序 (0, 100), (1, 50), (1, 60), (1, 45), (-2, 80) 希望排序之后(1, 50), (1, 60), (1, 45)这三个元素的相对位置不变。 适应性 如果一个排序算法对接近有序的序列工作的更快就称这种算法具有适应性。 也就是说如果本来已经快排序完了还差一点那么算法是能够利用这种优势迅速完成剩下的工作还是推倒重来按照原本既定的方法重新排序。 9.2 简单排序算法 插入排序已经有一个排序完的序列从剩余序列中顺序拿出一个跟前面的序列挨个比较寻找合适的位置插入。用于链表不错选择排序 简单选择排序每次找到最小的元素放在最前面直接选择排序算法把找到的最小元素和已排序序列后面的元素交换位置。是一个非常烂的算法。别用。堆排序堆排序的问题是不稳定交换排序 冒泡排序交错排序从左向右扫描一遍从右向左再扫描一遍9.3快速排序 转载于:https://www.cnblogs.com/theodoric008/p/7899523.html
