数据结构算法经典汇总

Posted on | Edited on | In

最近在当数据结构和算法的TA，记录一下老师考试的重点

时间复杂度

pass

经典排序

看经典排序哪章，主要是merge排序和quick排序
插入平常用的比较多，插入排序是前面的已经是排好序的了，后面的插入到前面里面。
注意在实现排序的时候，尽量选择交换的方法来实现排序，而不是用创建新的数组的方法

选择排序

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


def SelectionSort(nums):
    for i in range(len(nums)):
        Min = float("inf")
        index = None
        for j in range(i, len(nums)):
            if nums[j] < Min:
                index = j
                Min = nums[j]
        if index != i:
            temp = nums[i]
            nums[i] = nums[index]
            nums[index] = temp
    return nums

插入排序

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


def InsertSort(nums):
    n = len(nums)
    for i in range(1, n):
        temp = nums[i]
        j = i
        while j > 0 and temp < nums[j - 1]:
            nums[j] = nums[j - 1]
            j -= 1
        if j != i:
            nums[j] = temp
    return nums

merge排序（这种实现的空间复杂度是n）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22


def Merge(L, R):
    M = []
    while L and R:
        if L[0] <= R[0]:
            M.append(L.pop(0))
        else:
            M.append(R.pop(0))
    while L:
        M.append(L.pop(0))
    while R:
        M.append(R.pop(0))
    return M


def MergeSort(nums):
    if len(nums) < 2:
        return nums
    mid = int(len(nums) / 2)
    L, R = nums[:mid], nums[mid:]
    Merge(L, R)

快速排序(不占空间版本)

  • 重点：最后才把piv和最前或者最后的交换，先设置一个虚拟的piv的坐标
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21


    def partition(nums, l, r):

        piv = nums[r]
        i = l - 1  # 相当于piv的坐标
        for j in range(l, r):
            # 相当于把比piv小的都换到piv（i）的前面去
            if nums[j] <= piv:
                i += 1
                nums[i], nums[j] = nums[j], nums[i]
        # i的虚拟坐标和i的真实坐标right交换，也就是把piv换到最中间
        nums[i + 1], nums[r] = nums[r], nums[i + 1]
        return i + 1


    def QuickSort(nums, l, r):
        if l < r:
            q = partition(nums, l, r)
            QuickSort(nums, l, q - 1)
            QuickSort(nums, q + 1, r)

Heap

其实也就是堆排序，子节点的数值总是小于（或者大于父节点的数值）。通过list来操作，父节点为i的时候，子节点的坐标是 2i + 1 和 2i + 2，子节点为i的时候，父节点的坐标是 floor（（i - 1）/ 2）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20


def HeapSort(nums):
    for start in range(len((nums) - 2) // 2, -1, -1):
        MinHeap(nums, start, len(nums) - 1)
    for i in range(len(nums) - 1, -1, -1):
        nums[0], nums[i] = nums[i], nums[0]
        MinHeap(nums, 0, i - 1)


def MinHeap(nums, start, end):
    dad = start
    child = dad * 2 + 1
    while child <= end:
        if child + 1 <= end and nums[child] > nums[child + 1]:
            child += 1
        if nums[dad] > nums[child]:
            nums[dad], nums[child] = nums[child], nums[dad]
            dad = child
            child = child * 2 + 1

Hash

DFS BFS

KMP，BM(shift table)

BM：
从最末尾开始匹配，如果最后一个没匹配上，最后一个就是坏字符。

  • 如果单词里没有坏字符，那么直接移动到坏字符后一个
  • 如果单词里有，移动到他们俩对着的（搜索词里面出现的最后一次）
    1
    2
    　　后移位数 = 坏字符的位置(在搜索词的哪一位) - 搜索词中的上一次出现位置
    如果"坏字符"不包含在搜索词之中，则上一次出现位置为 -1。

如果后面几位可以匹配上，最后几位就是好后缀。(good suffix)

1
2
3
　　后移位数 = 好后缀的位置(算到最后一位) - 搜索词中的上一次出现位置
如果只出现了一次，那么这个位置是-1
如果有多个好后缀，除了最长的那个，其他的必须出现在头部

在上面两个移动方法中取最大的一个

因为好后缀比较难实现，所以大也可以光用坏字符法则

生成表

最牛逼的是，坏字符和好后缀都只和单词有关，和被搜索的东西无关，所以可以实现生成一张表来表示，然后再用的时候直接查

路径规划（prim，dij，krus）

把所有的点都设置成未访问的，并且距离是无穷大。只有起始点是访问的，并且距离是0.

  • visited记录已经访问过得点
  • distance记录这个点和起点的距离
    每次找不在visited里面，并且距离起点distance最小的点。放入已访问，并且relax所有和这个点连接的点（更新distance）
    重复这个步骤

python里面直接用字典来记录所有的数据类型就行了

在寻找未得到最优值的点中最小的值时，采用堆优化，其复杂度为O(1)，可以将整个算法的复杂度降为nlog(n) -> 用堆实现的也就是优先队列

  • 上面能够优化的时间复杂度是在“找到不在集合中的离 ss 最近的点”（每个点必须要进入集合才算更新结束，所以大循环的 O(n)O(n) 是无法减小的），我们能否通过一些排序操作，使得能够快速地找到这个点 xx 呢？
    这里就可以用到一个“小顶堆”的数据结构，它能够在 O(logn)O(log⁡n)（其中 nn 为堆中的元素数量）的时间复杂度内完成插入、删除最小值的操作，在 O(1)O(1) 的时间复杂度内完成取堆内最小值的操作。于是我们可以将上面的查找这一步操作放入到堆中，时间复杂度就能下降到 O(nlogn)

树（最大最小，字母树）

C++和python的特点

Python:面向对象，解释，通用。标准库比较多。

  • 语法简单，数据结构不需要定义
  • 解释性语言，跨平台的
  • 高级语言，屏蔽了很多底层实现。比如可以自动管理内存

缺点

  • 运行速度慢解释性语言的通病

编译语言和解释语言

编译型语言

源代码 -> 编译器 -> 最终可执行文件(.exe) -> OS -> CPU

  • 一次编译之后可以无限运行
  • 不能跨平台
    • 可执行程序不能跨平台，同平台可能不兼容
    • 源代码可能也不能跨平台。比如字节长度等问题

解释型语言

源代码 -> 解释器 -> OS -> CPU

  • 执行效率低。一般计算机的底层功能都会用C或者C++实现，应用层面才会使用解释性语言
  • 解释器可以把源代码转换成不同的机器码，所以源代码本身是可以跨平台的。解释器不能跨平台

##C++和python

  • C++更接近于底层，可以直接操作内存。大规模的计算
  • C++不仅面向对象，也面向过程

python： 快速开发应用程序
java： 健壮的大型软件
C++： 需求效率的软件
C： 操作系统及驱动

面向对象编程的特征

面向过程：就是分析出解决问题所需要的步骤，然后用函数把这些步骤一步一步实现，使用的时候一个一个依次调用就可以了。

封装 カプセル化 encapsulation

隐藏了某一方法的具体运行步骤，取而代之的是通过消息传递机制发送消息给它。封装是通过限制只有特定类的对象可以访问这一特定类的成员，而它们通常利用接口实现消息的传入传出。

不用知道是怎么实现的也可以用。私有成员不会被访问。

1
2
3
4
5
6
7
8
9
/* 一个面向过程的程序会这样写： */
定义莱丝
莱丝.设置音调(5)
莱丝.吸气()
莱丝.吐气()

/* 而当狗的吠叫被封装到类中，任何人都可以简单地使用： */
定义莱丝是狗
莱丝.吠叫()

继承 inheritance

在某种情况下，一个类会有“子类”。子类比原本的类（称为父类）要更加具体化
私有成员不会被继承，protected的成员会被继承
python的私有成员前面加两个下划线。保护乘员前面加一个下划线。前后都加下划线的是系统定义的名字

1
2
3
4
类牧羊犬 : 继承狗

定义莱丝是牧羊犬
莱丝.吠叫()    /* 注意这里调用的是狗这个类的吠叫方法。*/

当一个类从多个父类继承时，我们称之为“多重继承”。如一只狗既是吉娃娃犬又是牧羊犬（虽然事实上并不合逻辑）。多重继承并不总是被支持的，因为它很难理解，又很难被好好使用。

多态 polymorphism

指允许不同类的对象对同一消息做出响应。即同一消息可以根据发送对象的不同而采用多种不同的行为方式。很好的解决了应用程序函数同名问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
类狗
开始
    公有成员:
        叫()
        开始
            吠叫()
        结束
结束

类鸡
开始
    公有成员:
        叫()
        开始
            啼叫()
        结束
结束

定义莱丝是狗
定义鲁斯特是鸡
莱丝.叫()
鲁斯特.叫()

overload

首先说重载（overload），是发生在同一类中。与什么父类子类、继承毫无关系。
标识一个函数除了函数名外，还有函数的参数（个数和类型）。也就是说，一个类中可以有两个或更多的函数，叫同一个名字而他们的参数不同。
他们之间毫无关系，是不同的函数，只是可能他们的功能类似，所以才命名一样，增加可读性，仅此而已！

override

覆盖(override),是发生在子类中！也就是说必须有继承的情况下才有覆盖发生。
我们知道继承一个类，也就有了父类了全部方法，如果你感到哪个方法不爽，功能要变，那就把那个函数在子类中重新实现一遍。

机器学习和深度学习

机器学习直接来源于早期的人工智能领域，传统的算法包括决策树、聚类、贝叶斯分类、支持向量机、EM、Adaboost等等。从学习方法上来分，机器学习算法可以分为监督学习（如分类问题）、无监督学习（如聚类问题）、半监督学习、集成学习、深度学习和强化学习。

最初的深度学习是利用深度神经网络来解决特征表达的一种学习过程。深度神经网络本身并不是一个全新的概念，可大致理解为包含多个隐含层的神经网络结构。为了提高深层神经网络的训练效果，人们对神经元的连接方法和激活函数等方面做出相应的调整。其实有不少想法早年间也曾有过，但由于当时训练数据量不足、计算能力落后，因此最终的效果不尽如人意。

深度学习需要大量的样本才能很好的解决问题，如果样本数量不够的时候，使用机器学习的方法可以更好的解决问题

机器学习的主要障碍

由于以下原因，使用低功率/简单模型是优于使用高功率/复杂模型：

  • 在我们拥有强大的处理能力之前，训练高功率模型将需要很长的时间。 在我们拥有大量数据之前，训练高功率模型会导致过度拟合问题（因为高功率模型具有丰富的参数并且可以适应广泛的数据形状，所以我们最终可能训练一个适合于特定到当前的训练数据，而不是推广到足以对未来的数据做好预测）。
  • 然而，选择一个低功率的模型会遇到所谓的“欠拟合”的问题，模型结构太简单，如果它复杂，就无法适应训练数据。（想象一下，基础数据有一个二次方关系：y = 5 x ^ 2;你无法适应线性回归：y = a x + b，不管我们选择什么样的a和b。
  • 为了缓解“不适合的问题”，数据科学家通常会运用他们的“领域知识”来提出“输入特征”，这与输出关系更为直接。（例如，返回二次关系y = 5 square（x），如果创建了一个特征z = x ^ 2，则可以拟合线性回归：y = a z + b，通过选择a = 5和b = 0）。
  • 机器学习的主要障碍是特征工程这个步骤，这需要领域专家在进入训练过程之前就要找到非常重要的特征。特征工程步骤是要靠手动完成的，而且需要大量领域专业知识，因此它成为当今大多数机器学习任务的主要瓶颈。

深度学习的优点

DNN的主要区别在于，你可以将原始信号（例如RGB像素值）直接输入DNN，而不需要创建任何域特定的输入功能。通过多层神经元（这就是为什么它被称为“深度”神经网络），DNN可以“自动”通过每一层产生适当的特征，最后提供一个非常好的预测。这极大地消除了寻找“特征工程”的麻烦，这是数据科学家们最喜欢看到的。