# 关于本书

作为一个算法小白，在力扣和书本之间来回，看了很多大神耐心的解答和总结，书本里循循善诱的知识整理。总想用一张表格来梳理出算法的知识体系，却也一直没有时间整理。这本笔记里，我选择用比较简单的Python语言来回顾一下数据结构和算法的基本知识。

目的不是覆盖所有的知识点，而是想要把自己读的书越读越薄。用尽量浅显的理解来实现比较常见和实用的数据结构和算法，也当是对自己学习的总结，可能能帮到读者。当中有什么疏漏和错误可以直接评论。

## 语言的选择

### 为什么选择Python？

当然是因为好写啦！

平时在阅读的时候发现，很多经典算法书都是用Java或C++演示代码的，虽然也方便理解，但是用Python来作为范例的不算多数。所以我们主要来做两件事：

1. **用Python简单实现基础的数据结构**。有些数据结构（比如说OrderedDict）都现成调库就行了，但是为了理解它们的读写速度啊，优缺点啊，用相对简单的数据结构（数组和链表）来简单实现能帮助理解。
2. **介绍基本算法，提供一些算法模版。**（1）搜索方法，（2）用动态规划来优化搜索速度，（3）如何求解图的性质或最值，（4）如何用数据流或多个机器来再加速。算法主要是提供一些思维方式，让我们从“能解决“到“能高效解决“地问题。

### 使用Python要注意什么

* 比如说下面这段程序用二分法来寻找长度为`N`排序数组`x`中的`target`。然而因为`x[mid+1:]`或者`x[:mid]`在Python中创建了新的List，所以下面这段程序的时间复杂度退化到了`O(N)`。

```python
def binarySearch(x, target):
    if len(x)==0: return False
    mid = len(x) >> 1
    if target==x[mid]: return True
    if target>x[mid]:
        return binarySearch(x[mid+1:])
    return binarySearch(x[:mid])
```

* Python中函数的值是[passed by assignment](http://docs.python.org/3/faq/programming.html#how-do-i-write-a-function-with-output-parameters-call-by-reference)，所以要注意什么那些数据类型是能改变或会改变的。这个特性和其他语言很不一样。

## 算法总结

很多算法都有“一脉相承“的思路。所以这里我把算法的介绍顺序变成：搜索算法-->动态规划-->图论，因为我觉得有些算法这样引出这样比较好理解。

| 引子                                                                             | 算法                                                                                                                                                                                          |
| ------------------------------------------------------------------------------ | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| [DFS搜索](https://maomaoalgo.gitbook.io/python/suan-fa-ji-chu/shen-du-you-xian)  | <p><a href="hui-su-yu-dong-tai-gui-hua"><strong>动态规划算法</strong></a></p><p>DP可以理解成<strong>Memoization</strong>的迭代写法</p><p>aka带备忘录的DFS</p>                                                    |
| [动态规划](https://maomaoalgo.gitbook.io/python/hui-su-yu-dong-tai-gui-hua)        | <p><a href="tu-de-xing-zhi/you-xiang-tu-de-zui-zhi"><strong>DAG/拓扑排序算法</strong></a></p><p>拓扑排序利用了<strong>最优子结构</strong>的性质</p><p>这不就是DP的核心吗？</p>                                            |
| [BFS搜索](https://maomaoalgo.gitbook.io/python/suan-fa-ji-chu/guang-du-you-xian) | <p><a href="tu-de-xing-zhi/wu-xiang-tu-de-zui-zhi"><strong>Dijkstra算法</strong></a></p><p>BFS用Queue来存储<strong>最浅层</strong>的frontier</p><p>Dijkstra用PQ来存储<strong>最小cost</strong>的frontier</p> |