数据结构之二叉搜索树
二叉搜索树二叉搜索树（Binary Search Tree）是一种简单经典的数据结构，其特点有三： 一个结点的左子树的值都比该结点的值要小 一个结点的右子树的值都比该节点的值要大 没有两个结点拥有相同的值 得益于二叉树的特性，支持在 $O(\lg n)$ 的时间复杂度内进行查询操作。本文将介绍一个二叉搜索树的建立、查询以及删除节点操作。 结点的表示二叉搜索树也是二叉树，结点的表示和普通的二叉树没有什么区别。最简单的情况下，有一个存放数据的数据域，以及指向左右子树的指针。 12345template<class T>struct TreeNode { T d...
解决双系统启动 Ubuntu 进入 initramfs 问题
在我的电脑上，安装了 Kunbutu 17.04 和 Windows 10 两个系统。启动时通过 grub 来选择进入 Kubuntu 还是 Windows Boot Manager。之前使用一直正常，直到最近重装了一次 Kubuntu 之后发现，在进入 Windows 并重新启动之后，再进入 Kubuntu 的时候一定会进入 initramfs 命令提示符不能正常启动。一种解决办法是通过命令 e2fsck -y -f /dev/nvme0n1p5 （nvme0n1p5 是我的 Kubuntu 系统所在分区）来修复磁盘错误，然后重启即可正常进入 Kubuntu。但是每次都这样输入命令修复...
Visual Studio 2017 新建 C++ 单元测试
在 Visual Studio 2017 中，如果想要为一个 C++ 项目新建单元测试，首先在解决方案上右键，选择“添加”->“新建项目”，出现如图的对话框 选择 Visual C++ 的测试后，选择“本机单元测试”，点击确定生成测试项目。 右键单元测试项目中的“引用”，选择添加引用，弹出对话框： 勾上需要测试的项目后，点击确定。 之后打开 unittest1.cpp 编辑测试代码，在访问需要的类的时候，需要 #include 相关文件，需要注意相对路径。但是在本机上，**包含 .h 头文件的话生成解决方案的时候会出现 LNK2019 错误。一个解决办法是 #include ...
机器学习笔记：对率几率回归
对率几率回归（Logistic Regression）是机器学习中一种基本的分类算法，可以用来完成对输入数据的二分类任务。本文记录了使用 numpy 从基础的公式出发，逐步实现 Logistic Regression 的过程。 对数概率几率函数我们很容易想到二分类方法可以用阶跃函数（Step Function）来分类，但是阶跃函数不连续、不可导，无法训练，因此我们可以用 S 型函数（Sigmoid Function）来进行预测。 $$ \sigma (x) = \frac{1}{1 + e^{-x}} $$ Sigmoid 函数及其图像 该函数实际上是一种概率分布函数，它表示...
01 子串问题
问题：给定一个长度为 n (1 < n < 1000000) 的只含有0和1的字符串，求其中0和1数量相等的子字符串个数（不计空串）？子字符串指的是原串中下标为i到j（0 <= i <= j <= n-1）的字符组成的字符串。 解法一（枚举）我们很容易想到，要使得0和1个数相等，这个字符串的长度一定为偶数。只需要枚举原字符串中长度为偶数的子串，然后检验是否满足条件即可。 123456789101112131415int count_substring_slow(char *str) { unsigned int ...
经典寻路算法：A* 算法
（本文图片引用自 Amit Patel 的博客） 在游戏中，我们常常会遇到寻找两点之间最短路径的任务。而寻路算法中比较经典的就是 A* A* 算法 了。实际上，对于理解了它的人来说这是个很简单的算法，但对于不了解的人来说，可能这是一个比较复杂的算法。 理解一个复杂概念的最好办法便是由浅入深，A* 算法的提出也并非一蹴而就，它也是由一些简单的算法改造而来的。本文尝试带你一步步去学习 A* 算法的基本知识，帮助你理解这个算法。 最简单的寻路——贪心算法一个最简单的寻路算法便是直接计算起点各个方向到终点的距离，选择最小的那个方向走一步就可以了。这个算法理解起来很直观，计算量也不大，某些情况下是...
一些神经网络结构的初步认识
本文粗略地记录一下各个神经网络的特点和发展，仅供抛砖引玉，如需了解详情，可以自行深入搜索。 神经网络 （Neural Network）在出现多层神经网络之前，Frank Rosenblatt 在 1957 年就发明了一种名为 Perceptron 的神经结构，这种神经结构十分简单，可以用一条公式来概括，也就是 $$y = \sigma (\mathbf{W}\mathbf{x}+b)$$它的结构也可以用下图表示： 尽管结构看起来十分简单，但却能完成较为复杂的线性二元分类问题。然而，其严重的缺陷是不能完成非线性的二元分类问题，例如异或问题。在此基础上，人们将其改进为具有多层结构...
十进制转任意进制的算法原理
在中学课本里，我们学到了一个将十进制数转换为任意进制的算法：将十进制数除以新的进制，然后将商作为下一次除法的被除数，直到商为 0，然后将每次除法的余数从右到左写，就得到了新的进制。这篇小文章用数学公式来说明这个神奇算法中的数学道理。 首先，我们不妨假设十进制正数为 $N$，新的进制为 $R (R \geq 2)$ 进制。我们设第 $i$ 次除法的商和余数分别记作 $q_i$ 和 $y_i$。根据算法，我们可以得到下面的递推公式：$$q_{i-1} \div R = q_{i} \cdots \cdots y_i (1 \leq i \leq k)$$其中，我们约定$q_0 &#...
计算机负整数的二进制表示
在中学的信息技术课上，相信大家也听说过电脑中原码、反码、补码这些名词，这篇小文章就是来用数学公式来解释为什么负数的二进制表示是补码。如果你不知道补码是什么，请点击这里查看百科解释。 假设计算机内部用 $k$ 位二进制来表示一个整数。那么，一个正整数 $I$ 就可以写成下面的形式：$$I = \sum_{i=1}^{k} d_i \times 2^{i-1}$$其中$d_i$表示二进制数从右往左数的第$i$位数字。 而根据 Two’s Complement 原则，一个正整数$I$的负数就应该这样表示：$$Neg(I) = 2^k - I$$从这个公式出发，怎样...
Snake.c 用 C 语言写贪吃蛇！
在学习编程语言的过程中，偶尔写一些字符游戏，既能锻炼编程能力，又可以娱乐自己。今天就让我们一起学习怎样用 C 语言写经典游戏御三家之一的贪吃蛇吧！ 当然，为了让程序编写更有条理，我们要采用自顶向下的方法来设计我们的贪吃蛇程序。 这个版本还十分粗糙，更多的打磨就留给大家自己尝试吧！ 第一版：会动的蛇主函数贪吃蛇的游戏逻辑十分简单：如果游戏没有结束，那就读入一个字符，判断方向，然后让蛇走一步,然后把界面输出让玩家知道现在的游戏状态。根据自顶向下的设计思想，我们先简单地编写主程序框架： 123456789101112131415161718192021222324252627#define U...