| 2020-01-10 图的两种遍历 邻接矩阵和邻接表 在讲数据结构的那一节里我们提到了图这种数据结构，并且介绍了两种表示方法：邻接矩阵和邻接表。接下来我们来分别看看这两种方法是如何表示一张图的吧。 和树这种数据结构不同，图的节点之间的连接是自由的，即一个节点可以连接其他任意节点（包括自身），并且是具有方向性的。所以我们可以根据这样的特性，用 0 和 1 来表示一个节点 u 是否能够到达另一个节点 v。假设一个图由 n 个节点组成，那么我们就有 n2 种可能的连接。为了方便，我们用一个 n × n 的矩阵来表示： ...
| 2020-01-09 字符串匹配 回顾 前面我们学习了两种低效的排序算法，这次我们来看看一个关于搜索的问题：字符串匹配（string matching）。在算法的问题类型那一节里面我们提到了这个问题，这好比你在浏览网页或者在看电子书的时候按下“Ctrl+F”键，然后你输入一个单词或一段话，它就在原文中自动帮你找到那些匹配的文字。 matching 上图截自《算法导论》的某一页，我在我自己的电脑里试了一下，搜索的是单词“algorithm”，几秒钟就全部搜出来了，可以说速度是相当快的，要知道这本书可是有 1 ...
| 2020-01-07 冒泡排序与选择排序 暴力求解 从这一章开始，我们就要正式地进入具体的算法问题了。别忘了，我们没有按照类别将这些算法问题分类（排序，搜索等），而是按照不同的解决方法来划分的。在我们还没有了解那些高(ling)深(ren)莫(tou)测(teng)的算法之前，我们先来学习一种最简单、最直接的解决方式：暴力求解（brute-force）。 step 所谓的暴力求解就是指：根据问题具体的描述直接写出相应的算法，从而忽略我们观察和分析问题的过程。举两个例子，前面提到的扔鸡蛋的问题，假如你从第一层开始一 ...
| 2020-01-04 复杂度分析（递归） 什么是递归 前面我们对一些算法的复杂度进行了分析，但这些都是基于循环和迭代的，这一节我们会针对递归的算法进行复杂度分析。首先要需要知道什么是递归，递归（recursion）是函数调用自身的一个过程。举个例子，假设你是一个英语水平有限的人，你在读一段英文材料中遇到了某个生词，你需要查字典去了解这个单词的意思，但是字典只提供了英英字典，意味着你找到的单词下方的释义也有可能是你不认识的单词，于是你又继续查找那些单词的意思，而那些单词的释义有可能又出现你不认识的单词，你又继续查找直到 ...
| 2020-01-03 复杂度分析（非递归） 最好，最坏和平均情况 一个算法的好坏并不是一成不变的，它会在不同的情况下有着不同的表现。先来看看一个生活中的场景，假设买彩票中奖的概率是1 / 10,000，那么在最好，最坏和平均的情况下需要买几注彩票才能够中奖呢？显然，如果你的运气够好，第一注你就直接中了，这是最好的情况；相反，如果你的手气够差，你买的彩票永远都中不了奖，这是最坏的情况；平均来讲，你需要买最少10,000注才能够中奖，其实就是这里的数学期望。 彩票 这里的类比并不是想说明算法跟概率学有任何的关系，只是想 ...
| 2020-01-01 三种表示方法：O, Ω, Θ 引入 前面我们讲到了求最大公约数的算法：欧几里得算法。我们先举一个具体的实例：24 和 16 的公约数。根据其公式 gcd(m, n) = gcd(n, m mod n)，我们可以得到：gcd(24, 16) = gcd(16, 8) = gcd(8, 0)，所以最大公约数是 8。除了这种方法以外，我们还可以从 16 开始一个一个地递减，如果存在两数都能够被整除，那么这个数就是最大公约数。写成代码的形式就是： def gcd(m, n): r = min(m, n) ...
| 2019-12-31 算法的问题类型 概述 前面讲到了很多关于数据结构的概念，后面的内容就要用这些数据结构和算法来解决具体的问题了。那么首先我们是不是要对这些问题归一个类呢？废话不多说，直接先列举出来，主要分为五大类： 排序问题 搜索问题 图的问题 几何问题 组合问题 排序问题 排序问题是计算机科学里最基础，也是最重要的问题，很多情况下直接决定了你设计的程序的效率，因为大部分的程序都会用到排序。在实际生活中排序也是用处多多。一个最简单的例子就是国外大学的招生办将申请者的 GPA 全部导入到 Excel 中，然 ...
| 2019-12-30 基本数据结构 概念 如果说程序员是用代码编织这个世界的一群人，那么数据结构（data structure）就是编织所用到的各种工具了，它将计算机中各种各样的数据组织在一起。而我们的算法就是利用这些现有的工具将它们拼接成风格、功能各不相同的程序了。简单来说：算法 + 数据结构 = 程序。这一节就让我们来了解一些基本的数据结构吧。 数组与链表 我们从最简单的一维数据结构开始。数组大家应该都不陌生，它是将一组相同数据类型的数据存储在一起的数据结构。 数组 这里我们分析一下最基本的三大操作：查 ...
| 2019-12-27 算法与复杂度 前言 这个系列的博文会逐个介绍计算机科学里面最基础、也是最重要的一部分内容：算法(algorithm)。提到它，这可能是你最擅长的部分，亦或是你学生生涯的噩梦。不管怎么样，对于学计算机的小伙伴来讲，它始终是不可回避的一个话题。不论是学生时代的你还是已经踏上了工作的岗位，算法都会一直陪伴着你。 为什么要做这个系列呢？因为网上对于这一块的内容实在是太多，甚至是太杂，而很少有把算法的知识体系整合起来形成一个系列的教学博客。于是乎想尽自己的微薄之力，让更多的人能够更好地理解算法，在未 ...
| 2019-12-27 手把手教你用VPS搭建SS+bbr实现科学上网 写在前面 首先先声明一下，本文不带有任何商业性质，单纯地是想方便海内外学生党使用Google、YouTube、Wikipedia等工具来查阅资料，作为一个Google和Wikipedia的重度使用者，有时候离开了这两样东西真的就没办法生活，所以做一个这方面的教程是非常有必要的。 如果你对访问外网的频率和带宽要求不高，用一般的免费vpn或者一些在线代理就足够了，市面上这些vpn哪个好用，哪个免费相信你们比我更清楚。如果要经常看YouTube高清视频或者连外服打游戏的小伙伴呢，这 ...
