From Zero to Hero

从应用范围来看,算法可以分为数值算法和非数值算法.从工作方式来看,算法可以分为串行算法和并行算法. 概念 算法就是对特定问题求解过程的描述. 算法有一下几种性质: 通用性: 对符合输入要求的任意数据能够进行问题求解并能得到正确答案. 有效性 每条指令都能够正确有效的执行,执行结果类型可以预期. 确定性 每一步之后都有关于下一步动作的确切指令 有穷性 算法的执行必须在有限步数内执行完毕. 输入输出性 算法必须要有输入输出,没有输入输出的算法是无意义的. 算法设计 1 ....

基本概念 线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。这些元素也可称为结点或表目. 在稍复杂的线性表中，一个数据元素可由多个数据项（item）组成，此种情况下常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）。 逻辑结构 用二元组(K,R)来表示线性表,则有: 123K={k0,k1,k2,...,kn-1}R={r}r={<ki,ki+1> |...

题目描述 拿破仑席卷欧洲大陆之后，代表自由，平等，博爱的竖色三色旗也风靡一时。荷兰国旗就是一面三色旗（只不过是横向的），自上而下为红白蓝三色。 该问题本身是关于三色球排序和分类的，由荷兰科学家Dijkstra提出。由于问题中的三色小球有序排列后正好分为三类，Dijkstra就想象成他母国的国旗，于是问题也就被命名为荷兰旗问题（Dutch National Flag...

题目描述 一个台阶总共有n 级，如果一次可以跳1 级，也可以跳2 级。 求总共有多少总跳法，并分析算法的时间复杂度。 分析与解法 解法一 首先考虑最简单的情况。如果只有1级台阶，那显然只有一种跳法。如果有2级台阶，那就有两种跳的方法了：一种是分两次跳，每次跳1级；另外一种就是一次跳2级。 现在我们再来讨论一般情况。我们把n级台阶时的跳法看成是n的函数，记为f(n)。 当n>2时，第一次跳的时候就有两种不同的选择： 一是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1)； 另外一种选择是第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)。 因此n级台阶时的不同跳法的总数f(n)=f(n-1)+f(n-2)。 我们把上面的分析用一个公式总结如下： 123 / 1 n = 1f(n)= 2 n = 2 \ f(n-1) + f(n-2) ...

设顺序表a中数据元素递增有序,试着设计一个算法将x插入到顺序表的适当位置,以保持该表的有序性. 逐个遍历 以为顺序表递增有序,从头开始找到第一个不小于它的元素,放在该元素前面. 二分查找 步骤1:取顺序表中间元素的值与插入元素比较, 步骤2:相等则放在该元素前面;插入元素小于中间元素,将列表分割为两部分对前面的部分进行步骤1;如果大于,对后面部分进行步骤1 结束条件:比较结果相等,或者分割后顺序表元素个数为1

链表简介 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构在插入的时候可以达到O(1)的复杂度，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间.同时失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。 链表有很多种不同的类型：单向链表，双向链表以及循环链表。 单链表 单链表中每个结点只包含一个数据域和一个指针. 单链表声明 123456789101112131415161718192021222324252627typedef int T;//元素类型typedef struct link{ T data; struct link *next;}SingleLinkList, *PSingleLinkList;PSingleLinkList Init();int...

附近地点搜索 题目详情 找一个点集中与给定点距离最近的点，同时，给定的二维点集都是固定的，查询可能有很多次，时间复杂度O(n)无法接受，请设计数据结构和相应的算法。 分析与解法 此题是去年微软的三面题，类似于一朋友@陈利人出的这题：附近地点搜索，就是搜索用户附近有哪些地点。随着GPS和带有GPS功能的移动设备的普及，附近地点搜索也变得炙手可热。在庞大的地理数据库中搜索地点，索引是很重要的。但是，我们的需求是搜索附近地点，例如，坐标(39.91, 116.37)附近500米内有什么餐馆，那么让你来设计，该怎么做？ 解法一：R树二维搜索 假定只允许你初中数学知识，那么你可能建一个X-Y坐标系，即以坐标(39.91,...

随机取出其中之一元素 题目描述 一个文件中含有n个元素（n未知），要求在只能遍历一遍这n个元素的情况下，等概率随机的取出其中之一个元素。 分析与解法 假设5个人轮流抽签，只有其中某一个人能中签，那么，这5个人每个人中签的概率是相等的。不信的话，咱们可以具体计算下。 首先，第一个人中签的概率是1/5，第二个人中签的情况只能在第一个人未中时才有可能，所以第二个人中签的概率是4/5 X 1/4 = 1/5（4/5表示第一个人未中，1/4表示第二个人在剩下的4个签里中签的概率），所以，第二个人最终的中签概率也是1/5， 同理，第三个人中签的概率为：第一个人未中的概率 * 第二个人未中的概率 * 第三个人中的概率，即为：4/5 * 3/4 * 1/3 = 1/5， 一样的可以求出第四和第五个人的概率都为1/5，也就是说先后抽签顺序不影响每个人中签概率的大小。 回到咱们的问题，在明确了先后抽签顺序不影响不公平的原则之后，下面，给出选取策略： 顺序遍历，当前遍历的元素为第L个元素，变量e表示之前选取了的某一个元素，此时生成一个随机数r，如果r%L ==...

定义 顺序表(array-based list)又称为向量(vector)是在计算机内存中以数组的形式保存的线性表. 线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素,使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。 顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。 顺序表的基本操作 顺序表的声明 array_based_list.h 1234567891011121314151617181920212223242526272829#define ListSize 100 //线性表的最大长度typedef int DataType;// 顺序表内元素类型/**** 顺序表**///定义typedef struct{ DataType data[ListSize]; //用数组存储线性表中的元素 int length; ...

I/O的定义 I/O 是 Input/Output 的首字母缩写，即输入/输出，它描述的是数据流动的过程。输入/输出是相对而言的。下面将从两个角度出发来进一步理解 IO： 计算机结构的视角 根据冯·诺依曼结构，计算机分为五大部分，分别是：控制器、运算器、存储器、输入设备、输出设备。 输入设备（如鼠标键盘）和输出设备（如显示器）都属于外设（外部设备），而像硬盘、网卡这种既属于输入设备又属于输出设备。 从计算机的角度出发的话，操作系统将从输入设备读取到的数据写入到输出设备，这就是一次完整的 I/O 过程。 即 I/O 描述了计算机核心（CPU和内存）与外部设备之间的数据转移的过程。 应用程序的视角 我们都知道，应用程序作为一个文件保存在磁盘中，只有加载到内存中成为一个进程才能够运行。 为了确保操作系统的安全性和稳定性，操作系统会将内存分为 内核空间 和 用户空间，进行内存隔离。 而我们运行的应用程序都是运行在用户空间的，只有内核空间才能进行系统态级别的资源有关的操作，比如文件管理、进程通信、内存管理等。也就是说，我们想要进行 I/O...