文的盲

何为分治？简单来说，就是将大的问题分解成小问题进行求解，然后对每个小问题的解进行处理【一般是合并】为大问题的解，下面是分治较为官方的说明： 分治： 把一个任务，分成形式和原任务相同，但规模更小的 几个部分任务（通常是两个部分），分别完成，或只需要选一部完成。然后再处理完成后的这一个或几个 部分的结果，实现整个任务的完成。 斐波那契数列 我想了很多，最后发现还是从这个例子开始说起更加便于理解。 斐波那契数列的定义很简单，其最早的历史来自于那个生兔子的问题。斐波那契数列的解法众多，详细描述可见维基百科，而如果使用数学公式来描述，那么就是这个样子的： \[ \begin{equation} \left\{ \begin{array}{**lr**} F_0 = 0 & \\ F_1 = 1 & \\ F_n = F_{n-1} + F_{n-2} & \\ \end{array} \right. \end{equation} \] ...

曾经在初读 CSAPP 之时，我初步了解了 C 语言的全部编译过程，即大概可分为以下三大步： 预处理 编译 链接 今天，又看了节公开课，对这部分有了相对较为深入的理解，并且知道了一些有意思的事情。 开始之前，我们应该有这样一个概念：在使用 gcc 编译器进行编译之时，以上三步在某种意义上来说是相互分离的。 预处理阶段 对于此阶段，我之前所理解的全部，便是曾经所做的笔记： 通过预处理器( cpp ) 处理之后，将其变成了 .i 文件，.i 文件实际上对你写的 .c 文件里以井号 # 开头的语句进行了处理，其发现你引入了某个头文件，于是预处理器便将头文件的内容插入到了你的代码之中。 而如今，我想可以进一步扩展（或许不准确），预处理阶段所处理的内容，实质上就是对 C语言中的宏进行处理，而其中需要处理的部分，即通过宏语法限定的，在程序中有效的宏语言1。其中主要有两大类： #define ：对以 #define 打头的宏定义部分进行替换。 #include：对以 #include 格式引入的库文件进行添加。 #define 最为常见的宏定义， ...

此篇博文根据斯坦福公开课 《编程范式》整理，来阐述C语言函数执行时，在内存中的简单过程，也算是一个简单的笔记。 函数的活动记录 所谓活动记录，便是C语言程序在调用过程中的储存分配方案的记录。即：当一个过程被调用时，就把它的活动记录推入运行时存储栈的栈顶，而在控制返回调用程序时，再从栈顶弹出相应的活动记录。如此反复，以执行整个程序。 我们首先将内存抽象为一个索引从 0 开始的庞大数组，然后为了方便说明函数的具体执行过程，我们以一段简单的代码作为说明： 1234void foo(int a, int b) { char c[4]; int d;} 当我们写下这样一个函数的时候，在编译过程中，在内存中会如下图这样分配空间： C函数活动记录1.png 在该函数编译之时，以 Save PC 为分界线，内存上半部分依次为形参空间，下半部分为函数中所申明的变量的空间。 注：save PC 我其实并没有搞得很懂，但是按照老师的说法，应当可以理解为函数本身的地址（此处存疑） 函数的执行 为了较为顺畅地理解，我们依旧以示例代码来说明： 12 ...

分类问题 现实世界中，我们常常需要对事物进行分类，而分类的所依据的标准往往是多样的，这尤其体现在使用电脑解决分类问题之时。 我们如果要使用电脑进行分类，首先需要的便是数据。比如：我们需要将两个不同品种的鱼进行分类，我们首先需要根据找不同的方式找出两种鱼在某些特征上的不一致之处（如：长度，宽度，鱼鳍数目、长度等等）。我们将找出来的这些特征构建为一个行向量，同时对每一类都选许多条鱼进行测量，每一条鱼都能得到这样个行向量，将所有行向量拼接起来，构成一个\(N\times M\) 的矩阵（\(N\) 为鱼的数目，\(M\) 为依据的特征数目），这样就构成了一个简单的有标签的数据集。 有了数据集，接下来所要做的便是分类。什么是分类呢？现实生活中此概念很简单，比如我们买鱼时便有许多选择：鲤鱼，草鱼，带鱼等等等等，而用以区分这些鱼类的，大都是凭经验根据某些特征来区分。其实电脑也一样，分类要做的，就是将两类数据通过一个分类面区分开来，如下粗糙的图所示，分类所做的就是根据已有的数据，找出中间那条红线，将二者分开。 而所谓分类的方法，其归根到底就是利用各种方法，来找到这样一个最佳分类面。而 ...

堆栈是一两种十分常用的数据结构，而在硬件中根据内存相关分区功能的不同，将和此两种数据结构功能相似的分区（不是物理意义上的分区）分别称之为堆区栈区，简称堆栈。 所以要搞清楚不同之处（我刚学C语言的时候一直搞不清楚）：堆栈在数据结构（软件）中来说是两种数据结构的名称；而在计算机内存中又表示两个不同的分区的名称 堆（Heap） 堆区在内存中占了相当大的一部分，这部分主要是为了储存程序中动态分配的数据，就C语言而言， malloc() realloc() calloc() 申请而来的空间就全部是堆中的空间，而动态申请的空间均需要利用 free() 手动释放掉。 当我们书写语句，在堆中申请空间：int* tmp = malloc(40 * sizeof(int)) ，可以计算出，我们申请的空间大小理论上应该为 \(40 \times 4 = 160\) ，但是其在堆中实际申请的空间应该是大于理论值一到两个字节的，而申请完毕后传回的指针实际上也不是申请空间的首地址，而是类似一个如下图所示的结构： 粗谈堆栈1.png 申请的实际空间如最大的红色边界线所示，而理论空间则 ...

链表是什么？学过数据结构的人都很清楚，链表就是一种最最最基本的数据结构，基本到什么程度呢？基本到数据结构课上所学的数据结构都可以用链表来实现。 正因为其基础，我们更要了解链表的基本操作。 链表的构成及基本操作 首先了解链表（单向）的构成：链表由一个个统一的节点构成，节点一般由两个变量构成： 一个值，可以为各种类型 一个指向下一个节点的“指针” 链表的基本操作和多数数据结构相同，即插入，删除，查找等等。均很简单，也不再赘述，主要说说插入操作： 从头插入：新建的节点插入到链表头部 从尾插入：新建的节点插入到链表尾部 从任意位置插入：字面意思。 下面实现链表的构成及其基本操作（LeetCode 对应题目：707. 设计链表） 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687 ...

链表是最为基本的数据结构之一，常与数组作比较。由于链表相较于数组更加优良的的增删性能，常利用于增删比较频繁场合，并且衍生出了许多特殊的链表结构——静态链表，循环链表，双向链表等等。 而链表操作具有较强的技巧性，双指针最为常见，而双指针中，又以快慢指针最为特殊。这篇文章将根据自己的理解，说明快慢指针的原理与常见应用。 链表的中间结点 题目说明 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点。 示例 1： 12345输入：[1,2,3,4,5]输出：此列表中的结点 3 (序列化形式：[3,4,5])返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。注意，我们返回了一个 ListNode 类型的对象 ans，这样：ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL. 示例 2： 123输入：[1,2,3,4,5,6]输出：此列表中的结点 ...

什么是并查集？可以近似地用数学的观点来看，就像数学中的集合一般。但是并不尽相同，并查集在维基百科中的定义如下： 在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。 既然名字叫并查集，那么肯定有其原因，因为此数据结构中的两个操作便是并和查。 Find【查】：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。 Union【并】：将两个子集合并成同一个集合。 初始化并查集 我们可以使用两个数组来简单地实现并查集： 1234#define MAX_N 10000int par[MAX_N]; // 父亲int rank[MAX_N]; // 树高 有了以上定义，便可以实现并查集的初始化： 123456void init(int n) { for (int i = 0; i < n; i++) { par[i] = i; rank[i] = 0; }} 并查集 —— 查 由于 par[] 数组储存的就是父节点下标，所以依次 ...

今天闲得无聊，写了道题，写完后，我发现这道题让我对排序有了更加深刻的认识，如今在看来，排序的核心主要有两点： 比较函数（也就是比较的结果），决定了以何种方式进行排序：从大到小抑或是从小到大，甚至是其他更为特殊的方式 比较次数（也就是比较的方式），决定了排序的时间复杂度，也就是说，要想降低排序的时间复杂度，其重点就在于减少排序的次数。 排序总述 排序，在我看来，就是以给定的规则，对一组数（或者字符）进行重新排列，而规则是可变的，比如我们日常使用的：从大到小的顺序，从小到大的顺序，字典序等等等等。 那么，从底向上看排序，其最核心的部分，就在于两两比较，通过比较，就能确定两两之间的相对顺序——即谁先谁后。 而排序的效率，则取决于比较次数的多少，比如我们可以通过不重复比较，或者一些特殊的比较方式来缩短时间复杂度。 比较函数 总述 什么是比较函数？抽象来说，就是比较两个数，并确定其先后顺序的函数；具体来说，就是C语言 qsort() 函数中的 cmp 参数，是 java 中 Arrays.sort() 方法中的 Comparator 参数。 比较函数的一般写法是， ...

队列是具有一定操作约束的线性表，只能在一端（队尾）进行插入，另一端（队头）进行删除。 简单地理解，按照字面意思，队列这种数据结构，就如同生活中排队的队列一般，后来的人（数据）只能跟在队尾，而队首的人（数据）首先接受服务（进行删除）。 数据插入：入队列 （addQueue） 数据删除：出队列 （deleteQueue） 而队列主要的特性如下： 先来先服务 先进先出：FIFO 类型名称：队列（Queue） 数据对象集：一个有0个或多个元素的有穷线性表 操作集：长度为 MaxSize 的队列 Q 属于 Queue， 队列元素 item 属于 ElementType 123451. Queue CreatQueue() 生成空队列2. int IsFullQ(Queue PtrQ) 判断队列Q是否已满3. void AddQ(Queue PtrQ, ElementType item) 将数据元素item插入队列Q中4. int IsEmptyQ(Queue PtrQ) 判断队列是否为空5. ElementType DeleteQ(Qu ...