计算机知识图谱——数据结构与算法

发表于 | | 阅读次数:

计算机 ==>> 数据结构与算法

数据结构与算法

排序

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
do

  swapped = false

  for i = 1 to indexOfLastUnsortedElement-1

    if leftElement > rightElement

      swap(leftElement, rightElement)

      swapped = true

while swapped

最坏时间复杂度 O(n^2)，最好时间复杂度 O(n)，平均时间复杂度 O(n^2)，空间复杂度 O(1)，稳定排序

选择排序

1
2
3
4
5
6
7
8
9
10
11
repeat (numOfElements - 1) times

  set the first unsorted element as the minimum

  for each of the unsorted elements

    if element < currentMinimum

      set element as new minimum

  swap minimum with first unsorted position

最坏时间复杂度 O(n^2)，最好时间复杂度 O(n)，平均时间复杂度 O(n^2)，空间复杂度 O(1)，不稳定排序

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
mark first elemenzt as sorted

for each unsorted element X

  'extract' the element X

  for j = lastSortedIndex down to 0

    if current element j > X

      move sorted element to the right by 1

    break loop and insert X here

最坏时间复杂度 O(n^2)，最好时间复杂度 O(n)，平均时间复杂度 O(n^2)，空间复杂度 O(1)，稳定排序

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
split each element into partitions of size 1

recursively merge adjacent partitions

  for i = leftPartIdx to rightPartIdx

    if leftPartHeadValue <= rightPartHeadValue

      copy leftPartHeadValue

    else: copy rightPartHeadValue

copy elements back to original array

最坏时间复杂度 O(nlogn)，最好时间复杂度 O(nlogn)，平均时间复杂度 O(nlogn)，空间复杂度 O(n)，稳定排序

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
for each (unsorted) partition

set first element as pivot

  storeIndex = pivotIndex + 1

  for i = pivotIndex + 1 to rightmostIndex

    if element[i] < element[pivot]

      swap(i, storeIndex); storeIndex++

  swap(pivot, storeIndex - 1)

最坏时间复杂度 O(n^2)，最好时间复杂度 O(nlogn)，平均时间复杂度 O(nlogn)，空间复杂度 O(nlogn)，稳定排序

计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
create key (counting) array

for each element in list

  increase the respective counter by 1

for each counter, starting from smallest key

  while counter is non-zero

    restore element to list

    decrease counter by 1

最坏时间复杂度 O(n)，最好时间复杂度 O(n)，平均时间复杂度 O(n)，空间复杂度 O(k)，稳定排序

基数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
create 10 buckets (queues) for each digit (0 to 9)

for each digit placing

  for each element in list

    move element into respective bucket

  for each bucket, starting from smallest digit

    while bucket is non-empty

      restore element to list

>
slowfastgo to beginningprevious framepausenext framego to end

最坏时间复杂度 O(nm)，最好时间复杂度 O(nm)，平均时间复杂度 O(nm)，空间复杂度 O(m)，稳定排序

堆排序

最坏时间复杂度 O(nlogn)，最好时间复杂度 O(nlogn)，平均时间复杂度 O(nlogn)，空间复杂度 O(nlogn)，稳定排序

链表

单向链表

单向链表中每个结点包含两部分，分别是数据域和指针域，上一个结点的指针指向下一结点，依次相连，形成链表。

1. 链表反转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func (head *Node) ReverseNode() *Node {
	if head == nil || head.Next == nil {
		return head
	}

	var preNode, nowNode *Node
	preNode = head
	nowNode = head.Next
	for {
		sufNode := nowNode.Next
		nowNode.Next = preNode
		if sufNode == nil {
			break
		}
		preNode = nowNode
		nowNode = sufNode
	}
	head.Next = nil
	head = nowNode

	return nowNode
}
2. 删除排序链表中的重复元素
1
2


双向链表

单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。而双向链表，顾名思义它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。

循环链表

循环链表跟单链表唯一的区别就在尾结点。单向链表的尾结点指针指向空地址，表示这就是最后的结点了，而循环链表的尾结点指针是指向链表的头结点，它像一个环一样首尾相连，所以叫作“循环”链表。

哈希表

定址的方法

  1. 直接定址法：很容易理解，key=Value+C；这个“C”是常量。Value+C其实就是一个简单的哈希函数。

  2. 除法取余法：key=value%C

  3. 数字分析法：这种蛮有意思，比如有一组value1=112233，value2=112633，value3=119033，针对这样的数我们分析数中间两个数比较波动，其他数不变。那么我们取key的值就可以是key1=22,key2=26,key3=90。

  4. 平方取中法

  5. 折叠法：举个例子，比如value=135790，要求key是2位数的散列值。那么我们将value变为13+57+90=160，然后去掉高位“1”,此时key=60，哈哈，这就是他们的哈希关系，这样做的目的就是key与每一位value都相关，来做到“散列地址”尽可能分散的目地。

解决冲突的方法

  1. 链接地址法：
    将哈希值相同的数据元素存放在一个链表中，在查找哈希表的过程中，当查找到这个链表时，必须采用线性查找方法。

  2. 开放定址法：
    如果两个数据元素的哈希值相同，则在哈希表中为后插入的数据元素另外选择一个表项。当程序查找哈希表时，如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素，程序就会继续往后查找，直到找到一个符合查找要求的数据元素，或者遇到一个空的表项。线性探测带来的最大问题就是冲突的堆积，你把别人预定的坑占了，别人也就要像你一样去找坑。改进的办法有二次方探测法和随机数探测法。开放地址法包括线性探测、二次探测以及双重散列等方法。

  1. 再散列函数法：
    发生冲突时就换一个散列函数计算，总会有一个可以把冲突解决掉，它能够使得关键字不产生聚集，但相应地增加了计算的时间。

  2. 公共溢出区法：
    其实就是为所有的冲突，额外开辟一块存储空间。如果相对基本表而言，冲突的数据很少的时候，使用这种方法比较合适。

一致性哈希

  1. 将机器通过哈希算法均匀的分布到哈希环上

  2. 将请求通过哈希算法映射到哈希环，顺时针找到机器

优化:

  1. 将机器虚拟为多个节点，以节点分布更加均匀

  2. 通过红黑树提高查询速度

树

遍历

  1. 前序遍历（深度优先遍历）

基本思想：先访问当前结点，再前序遍历左子树，最后再前序遍历右子树即根—左—右

  1. 中序遍历

基本思想：先中序遍历左子树，然后再访问当前结点，最后再中序遍历右子树即左—根—右。

  1. 后序遍历

基本思想：先后序遍历左子树，然后再后序遍历右子树，最后再访问当前结点即左—右—根。

  1. 层次遍历（广度优先遍历）

基本思想：从第一层开始，依此遍历每层，直到结束。

二叉搜索树

  1. 构建

左子树的值小于根节点的值，根节点的值小于右子树的值

  1. 排序

中序遍历的结果是从小到大排序好的值

  1. 查找

复杂度小于树的高度

  1. 删除

寻找右子树的最左子树值替换，左子树的右子树由父树接管为左子树

平衡二叉树

AVL树是左右子树的高度差小于等于1的二叉搜索树（比二叉搜索树更快的查找速度）

  1. 构建

  2. 旋转

左旋转 插入的结点为失衡点的右子树的右子树中

右旋转 插入的结点为失衡点的左子树的左子树中

左右旋转 插入的结点为失衡点的左子树的右子树中

右左旋转 插入的结点在失衡点的右子树的左子树中

  1. 查找

  2. 插入

  3. 删除

红黑树

RB树就是一种以二叉树形式实现了2-3-4树的想法

  1. 构建

  2. 旋转

  3. 查找

  4. 插入

  5. 删除

trie树

又称前缀树（prefix tree）、字典树

  1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。

  2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

  3. 每个节点的所有子节点包含的字符都不相同。

B树

B+树

R树

图

动态规划

寻找股票买入卖出的最佳时机

F（n，0） = 0
F（n，1）= max（-price[n-1]，F（n-1，1））
F（n，2）= max（F（n-1，1）+ price[n-1]，F（n-1，2））
F（n，3）= max（F（n-1，2）- price[n-1]，F（n-1，3））
F（n，4）= max（F（n-1，3）+ price[n-1]，F（n-1，4））

每一个阶段最大收益和上一个阶段的关系：

F（n，k） = max（F（n-1，k-1）+ price[n-1]，F（n-1，k））

其它算法

地理围栏算法

射线法

射线法：从该点出发沿着X轴画一条射线，依次判断射线与每条边的交点，并统计交点个数。如果交点数为奇数，则在多边形内部；如果交点数为偶数，则在外部。

射线法对凸和非凸多边形都适用，复杂度为O(N)，其中N是边数。

当地理围栏多边形数目较少时，可以依次遍历每个多边形（暴力遍历法），然后用射线发进行判断。但当多边形数目较多时，执行时间较长。

空间索引R树

  1. 用最小外包矩形表示多边形

  2. 对最小外包矩形建立R树索引

  3. 查询

    1) 通过R树迅速判断位置是否被外包矩形覆盖；

    2) 如果不被任何外包矩形覆盖则不在地理围栏范围；

    3) 如果被外包矩形覆盖则进一步采用射线法判断是否在外包矩形的多边形内部。

    4) 重复以上步骤，直到找到一个节点。

多边形R树索引

多边形的边数较多时，一次射线法执行时间较长。

  1. 对多边形的每条边构建最小外包

  2. 对最小外包矩形建立R树索引

  3. 查询