Category Archives: 算法

C语言实现 trie 统计单词频率

前面在解决圣经背诵问题使用 C 语言解决圣经背诵问题中,涉及到一个问题,就是统计文件中各个单词数量的问题,在网上找到了一个解决办法就是 Trie。
Trie,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用[……]阅读全文

使用 C 语言解决圣经背诵问题

PHP 解决圣经背诵问题 这一篇中我们使用 PHP 解决了圣经背诵问题,但是程序运行速度不尽人意,一般要3秒或更多的时间才能得出结果。
我们可以使用 time 命令来看一下运行时间 (关于 time 命令的说明见这一篇 Linux 下使用 time 命令查看程序的执行时间)。
结果如下:[……]阅读全文

PHP 解决圣经背诵问题

在网上看到这样一个题目,听说是腾讯的面试题目,于是决定先用 PHP 来尝试试解决这个问题。
题目如下:

我们碰到了大麻烦,一个新来的传教士惹恼了上帝,上帝很愤怒,要求我们把圣经背熟,直至他说哪个单词,我们就要飞快的回答出这个单词在第几行第几个单词位置。听说你是个优秀的程序员,那么帮助我们完成这个

[……]阅读全文

C语言如何对包含一千万不重复整数的文件进行排序

《编程珠玑》中有着样一题:
限制使用内存 1M
磁盘大小不限
输入为一个文件,此文件包含最多n个正整数,每个数都小于 n,n=10000000 ,所有的正整数不重复
要求对文件输入的整数进行升序排序

常规解法是分块排序,这种解法易懂,也容易实现,实现步骤为,
将 1-10000000[……]阅读全文

C 语言如何实现向量(字符串)旋转(循环位移)

《编程珠玑》上有这样一题:
将一个 n 元一维向量左旋转 i 个位置。例如,当 n = 8, i = 3 时,
向量 abcdefgh 旋转为 defghabc 。简单的代码使用一个 n元中间向量
在 n 步内完成工作。能否仅使用 10 字节额外的存储空间,在正比于 n 的
时间内完成向量旋[……]阅读全文

散列表(Hashtable) 几个常见的散列(Hash)函数

需要用 C 实现了一个 Hashtable。
散列表也称哈希表(Hash table),可直接根据键(Key)快速查找值的数据结构。
它把键映射到表中一个位置来访问记录,以加快查找的速度。
这个映射函数叫做散列函数,存放记录的表叫做散列表。

常见散列函数构造方法
1、直接寻址法
2、

[……]阅读全文

Base64解密(base64_decode)原理及如何使用 PHP 实现

接上一篇何谓 Base64 加密算法及原理,如何使用 PHP 实现一个 Base64_encode

现在我们来说一说如何解密使用 Base64 加密之后的内容,总的来说
Base64 解密就是加密的逆过程,加密的时候就是将每三个自己转为4个字符,
那么解密的时候就是将4个字符还原为三个字节,但

[……]阅读全文

何谓 Base64 加密算法及原理,如何使用 PHP 实现一个 Base64_encode

Base64 加密算法
Base64 算法将每连续对 3 个字节(共 24 位)的内容,平均非为 4 部分每部分 6 位。
6个字节能表达的正整数范围为 0 - 31,共64个数字。我们使用 US-ASCII子集的 64 个字符
+、/、数字 0-9、小写字母 a-z、大写字母 A-Z 组成一

[……]阅读全文

快速排序 quicksort

快速排序是一种采用分治法的比较排序算法。
一般分为三个步骤完成:
一、分解:将数组 A[p..r] 分解为两个(可能为空)子数组 A[p..q – 1] 和
A[q + 1..r],使得 A[p..q – 1] 中的每个元素都小于等于 A[q],而且,
A[q + 1..r] 中的每个元素都[……]阅读全文

堆排序 Heapsort

堆排序是一种以(二叉)堆为数据结构来管理算法执行的原地排序算法。
二叉堆是一种数组对象,可以被视为一颗完全二叉树。二叉堆分为最大堆和最小堆。
对于数组:

[20, 17, 13, 12, 10, 9, 7, 6, 5,2, 1]




它可以就可视为一个最大堆,一下为一个二叉树的示意图[……]阅读全文