程序员如何准备面试中的算法
备战面试中算法的五个步骤 对于立志进一线互联网公司，同时不满足于一辈子干纯业务应用开发，希望在后端做点事情的同学来说，备战面试中的算法，分为哪几个步骤呢？如下： 1、掌握一门编程语言 首先你得确保你已掌握好一门编程语言： C的话，推荐Dennis M. Ritchie & Brian W. Kernighan合著的《C程序设计语言》，和《C和指针》； C++ 则推荐《C++ Primer》，《深度探索C++对象模型》，《Effective C++》； Java推荐《Thinking in Java》，《Core Java》，《Effictive...
算法分析
算法的复杂性体现在时间复杂性和空间复杂性上.一般使用渐进分析法来表达和计算一个算法的复杂性. 渐进分析法 一般表示输入规模与时间关系的函数比较复杂.渐进分析法计算时间时通常只考虑显著改变函数量级的部分,其余部分忽略. 渐进分析法是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。 渐进分析法包含三种表示方法:大O表示法,Ω(欧米伽)表示法,Θ(西塔)表示法 大O表示法 对于f(n)，存在正数n0、c，使得当 n>n0 时，始终存在 0 <= f(n) < =c*g(n)，则我们可以用 f(n)=o(g(n))表示。 算法的时间复杂度通常用大O符号表述，定义为T[n] = O(f(n))。称函数T(n)以f(n)为界或者称T(n)受限于f(n)。...
算法概述
从应用范围来看,算法可以分为数值算法和非数值算法.从工作方式来看,算法可以分为串行算法和并行算法. 概念 算法就是对特定问题求解过程的描述. 算法有一下几种性质: 通用性: 对符合输入要求的任意数据能够进行问题求解并能得到正确答案. 有效性 每条指令都能够正确有效的执行,执行结果类型可以预期. 确定性 每一步之后都有关于下一步动作的确切指令 有穷性 算法的执行必须在有限步数内执行完毕. 输入输出性 算法必须要有输入输出,没有输入输出的算法是无意义的. 算法设计 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 ==...