Aull Chen's Blog

链表 本文语法涉及大量C语言中结构体的语法，请在食用前确保已经有所了解，不然可能会一头雾水。 当然，如果实在不懂，可以留言。 一、链表的概念 对于顺序存储的结构，最大的缺点就是 插入 和 删除 的时候需要移动大量的元素。所以基于前人的智慧，他们发明了链表。 1、链表的定义 链表由一个个结点组成，每个结点之间通过链接关系串联起来，每个结点都有一个后继结点，最后一个结点的后继结点为空结点。 由链接关系 A -> B组织起来的两个结点，B 被称为 A 的后继结点，A 被称为 B 的前驱结点。 链表分为单向链表、双向链表、循环链表等等。 本文介绍单向链表。 2、链表结点的定义 1234struct ListNode { DataType data; // (1) ListNode *next; // (2)}; （1）data 是数据域，用来储存数据，可以是任意类型，由编码的人自行指定其DataType。本文数据域全部采用int型进行讲解。 （2）*next是指针域，指向 后继结点 的地址。 3、链表结点创建 123456ListNode *List ...

前缀和 前言 前缀和是应用于顺序表的算法，用来储存顺序表前n项的和。 一、朴素前缀和 1、部分和 所谓 部分和，就是给定一个数组，求它的某一段连续子数组的和。 2、朴素做法 比较传统的做法，就是对于要求部分和的区间 [l, r]，枚举所有的数进行相加，如下： 12345678int partialSum(int *a, int l, int r) { int i; int s = 0; for(i = l; i <= r; ++i) { s += a[i]; } return s;} 此时时间复杂度最坏为O(mn)。有没有办法优化呢？ 3、前缀和 我们可以用一个 sum[] 数组来表示数组的前缀和，即 sum[i] 表示的是前 i 项的和，数学公式如下： sum[i]=∑k=0ia[k]sum[i] = \sum_{k=0}^{i}a[k] sum[i]=k=0∑i​a[k] 将 i-1 代入上述的 i，得到 sum[i−1]=∑k=0i−1a[k]sum[i-1] = \sum_{k=0}^ ...

双指针 前言 《算法导论》上是看不到的双指针的，因为无论是思考过程还是代码实现上都是非常容易理解，所以各大算法书上都不屑将它归为算法，但是它却作为职场面试，省赛水题的绝佳选择，它有一个比较优雅的名字叫 尺取法，英文把它叫 two pointers，也就是 双指针 的意思。需要注意的是，这个算法一般而言跟指针关系不大，不要被名字骗了…… 一、最长不重复子串 给定一个长度为 n (1 ≤ n ≤ 10^7^) 的字符串 s，求一个最长的满足所有字符不重复的子串。 1、初步分析 首先我们分析一下这个问题的关键词，主要有以下几个： 1）n ≤ 10^7^； 2）最长； 3）所有字符不重复； 4）子串； 根据以上的几个关键词，我们可以得出一些结论。首先，根据 n 的范围已经能够大致确认这是一个需要 O(n) 或者 O(nlogn) 的算法才能解决的问题；其次，“最长” 这个词告诉我们，可能是一个动态规划问题或者贪心问题，也有可能是搜索，所以这个关键词给我们的信息用处不大；而判断字符是否重复可以用 哈希表 在 O(1) 的时间内判断；最后，枚举所有 “子串” 的时间复杂度是 O(n^2) ...

贪心 一、概念定义 所谓贪心，总是做出在当前看来是最好的选择。也就是说，不从整体最优上进行考虑，算法得到的是在某种意义上的局部最优解。 比如，对于一个全是正整数的数组，我要找到其中两个数，使得它们的乘积最大，毫无疑问，一定是取 最大 和 次大 的两个数进行相乘，得到的结果最大。这个就是贪心思想。 贪心是一种抽象的算法，需要的不仅仅是积累，往往还有灵光一现。 二、例题分析 1、最大乘积差 1234567int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b;}int maxProductDifference(int* nums, int numsSize){ qsort(nums, numsSize, sizeof(int), cmp); //先对数组进行排序 return nums[numsSize - 1] * nums[numsSize - 2] - nums[0] * nums[1]; //利用贪心，直接取最大的两个数下标作为 w 和 x，最小的两个数 ...

递推 前言 递推最通俗的理解就是数列，递推和数列的关系就好比 算法 和 数据结构 的关系，数列有点像数据结构中的顺序表，而递推就是一个循环或者迭代的枚举过程。 递推本质上是数学问题，所以有同学问算法是不是需要数学非常好，也并不是，你会发现，这些数学只不过是初中高中我们学烂的东西，高考都经历了，这些东西又何足为惧！? 一、斐波那契数列 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1，给定 n(0 ≤ n ≤ 30) ，请计算 F(n) 。 拿到这个题目，我们首先来看题目范围， 最多不超过 30，那是因为斐波那契数的增长速度很快，是指数级别的。所以如果  n 很大，就会超过 c语言 中32位整型的范围。这是一个最基础的递推题，递推公式都已经告诉你了，我们要做的就是利用一个循环来实现这个递推。 我们只需要用一个 F[31] 数组，初始化好 F[0] 和 F[1]，然后按照给定 ...

模拟 前言 模拟算法其实就是根据题目做，题目要求什么，就做什么。 一、数据结构 对于模拟题而言，最关键的其实是数据结构，看到一个问题，选择合适的数据结构，然后根据问题来实现对应的功能。模拟题的常见数据结构主要就是：数组、字符串、矩阵、链表 等等。 1、基于数组 利用数组的数据结构，根据题目要求，去实现算法，如：1920. 基于排列构建数组、1389. 按既定顺序创建目标数组、1603. 设计停车系统、2149. 按符号重排数组、2221. 数组的三角和 2、基于字符串 利用字符串的数据结构，根据题目要求，去实现算法，如：2011. 执行操作后的变量值、2744. 最大字符串配对数目、LCP 17. 速算机器人、537. 复数乘法 3、基于链表 利用链表的数据结构，根据题目要求，去实现算法，如：2181. 合并零之间的节点、1823. 找出游戏的获胜者 4、基于矩阵 利用矩阵的数据结构，根据题目要求，去实现算法，如：2120. 执行所有后缀指令、1252. 奇数值单元格的数目、832. 翻转图像、657. 机器人能否返回原点、289. 生命游戏、59. 螺旋矩阵 II、885. 螺旋 ...

枚举 定义 枚举的概念就是把满足题目条件的所有情况都列举出来，然后一一判定，找到最优解的过程。 一、最值问题 比较经典的枚举问题莫过于最值问题了，也就是求一堆数中的最大值或者最小值。 1、两个数的最值问题 两个数的最小值，利用C语言中的三元运算符就可以实现： 123int Min(int a, int b) { return a < b ? a : b;} 2、n 个数的最值问题 当有 n 个数时 ai 时，我们可以首先取前两个数，计算最小值；然后再拿这个最小值和第三个数去比较，得到的最小值再去和第四个数比较，以此类推，就可以计算出 n 个数中的最小值。 假设前 i 个数的最小值为 mi，则有递推公式如下： mi={aii=0min(mi−1,ai)i>0\begin{equation} m_{i}=\left\{ \begin{aligned} a_{i} && i=0 \\ min(m_{i-1}, a_{i}) && i>0 \\ \end{aligned} \right. \end{equation}mi ...

计数排序 1. 概念定义 计数排序（Counting sort）是一个非基于比较的稳定的线性时间的排序算法， 非基于比较：之前学的排序都是通过比较数据的大小来实现有序的，比如希尔排序等，而计数排序不用比较数据的大小。 计数排序的名字会让我们想到“计数法”，实际上计数排序的实现就是使用的计数法。（类似哈希表的思想） 工作原理：使用一个额外的数组 cnt，其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数，然后根据数组 cnt 来将 A 中的元素排到正确的位置。 具体实现：创建一个足够大的数组 cnt，足够大的意思是 cnt 的下标范围可以包括所有的待排序数据值。然后遍历待排序数据，使用计数法统计每个数据的出现次数。最后遍历 cnt 数组，将每一个值（cnt[i]）不为 0 的下标（i）放入原数组 cnt[i] 次。 1234567891011121314void countingSort(int *s, int size) {    int cnt[101]; //因为最大的数据是100，所以数组下标要开到 101，否则会出现数组越界问题    memset( ...

博客搭建教程 本篇文章缝合了源自网络的多篇教程，主要目的是用来帮自己记住相关操作方法，类似备忘录。 （还有就是水文章，毕竟在博客里发布搭建博客的教程也是一种传统？） 前言 近些年来很多用户都喜欢使用 GitHub Pages 来搭建 Hexo 静态博客网站，其最吸引人的莫过于完全免费使用，并且非常稳定。 虽然搭建时比较麻烦，有点折腾，但是配置完成后，基本不需要操心维护的事，甚至放了几年都忘记了，打开来看文章依然还在。 本文就详细介绍下如何使用 Hexo + GitHub 搭建免费个人博客网站的教程。 简介 GitHub Pages 是什么？ What is GitHub Pages? - GitHub Help GitHub Pages 是由 GitHub 官方提供的一种免费的静态站点托管服务，让我们可以在 GitHub 仓库里托管和发布自己的静态网站页面。 Hexo 是什么? 官网：hexo.io Hexo 是一个快速、简洁且高效的静态博客框架，它基于 Node.js 运行，可以将我们撰写的 Markdown 文档解析渲染成静态的 HTML 网页。 Hexo + GitH ...

冒泡排序 1. 概念定义 冒泡排序（Bubble Sort）又称为泡式排序，是一种简单的排序算法。 核心思想：它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就像水中的气泡会冒起来一样。 运作步骤（升序排列）： 比较相邻的元素。如果第一个比第二个大，就交换它们两个。 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。 针对所有的元素重复以上的步骤，除了最后一个。 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 比如： 原始数据：3 2 7 8 6，将其按升序排列。 第一次循环：（最大的跑到最右边） 3 2 7 8 6 --> 2 3 7 8 6 （3和2比较，3 < 2，所以3和2交换位置） 2 3 7 8 6 --> 2 3 7 8 6 （3和7比较。3 < 7，所以3和7不用交换位置） 2 3 ...