简明现代魔法 -> 计算机算法

最大公共子串问题JavaScript版

常见的做法是使用矩阵

求最大公共子串,常见的做法是使用矩阵。假设有字符串:abcdefg和字符串abcd,则可构成如下矩阵。对两个字符串的每一项都进行比较,若匹配则该项为1,不匹配则为0。然后求出对角线最长为1的那一段序列,即为最大公共子串。看上面的分开,似乎得使用二维数组了,在两个字符串都较大的情况下不是很划算,是否可以进一步优化?

发布于 2011-06-21 分类:algorithm

一次腾讯招聘的笔试和面试题

给希望进腾讯的朋友一点提示

考的内容非常广泛,包括但不限定于以下内容:计算机体系结构(32位系统和64位系统的区别)、操作系统(内存和cache)、数据结构(由二叉树的中序和后序遍历推出前序遍历结果)、算法(快排第一遍的结果;哪些排序是稳定性排序)、编译原理(操作系统,静态数据区,程序区,堆栈区在内存中的顺序)、计算机网络(服务器收到FIN后处于什么状态)。

发布于 2011-05-25 分类:algorithm

一道关于男女比例的面试题

阿里巴巴的一道面试题

阿里巴巴的一道面试题:说澳大利亚的父母喜欢女孩,如果生出来的第一个女孩,就不再生了,如果是男孩就继续生,直到生到第一个女孩为止,问若干年后,男女的比例是多少?刚看到问题是的思维逻辑:用递推法,假设一对夫妻,生了个女儿,就不再要了;另外一对夫妻,生了个儿子,再要一个,是女儿,然后也就不要了。第一感觉,应该是女的比男的多。

发布于 2011-05-19 分类:algorithm

一棵简单的树的实现

数据源用数组混json结构,实现了基本的功能

数据源用数组混json结构,实现了基本的功能。效率一般,跟 dhtree 梅花雪树对比了下,都差不多。这个实现树的原理是根据json,不断的生成ul li, 下面是一个简单的例子(只有涉及到生成树,也就是说只是展示,tree类代码只有64行) 没有用innerHTML生成,全是是创建节点来创建ul li,所以创建节点碎片添加。

发布于 2011-05-03 分类:algorithm

大范围内素数的求法的效率问题

学习一下这种求素数的算法

筛选法求素数有一个很通用的算法,就是在遍例该集合时,比方检验一个数N是否素数,用N除以2-N的开方,只要有一个能整除,就说明N不是素数。另外这道题要求用数组来计算。谓"筛选法"指的是"埃拉托色尼(Eratosthenes)筛法"。他是古希腊的著名数学家。

发布于 2011-04-18 分类:algorithm

数字1亿里面有多少个1呢

遍历每个数再toString() 看看里面有多少个1

乍看这题真够唬人的,群里看到这个题目后争先恐后的说看法。最简单的办法不外乎就是遍历每个数,然后toString() 看看里面有多少个1,最后全部加起来,这是我们得到标准答案的办法。群里3个人写了3个笨方法都跑出来了,3个笨方法,呵呵 有意思,笨方法也不一样。 程序的实现真是变幻莫测。

发布于 2011-04-17 分类:algorithm

高频笔试题strcpy()的写法

一个问题的多个误区

题目:已知strcpy函数的原型是char * strcpy(char * strDest, const char * strSrc);不调用库函数,实现strcpy函数。解释为什么要返回char *。不检查指针的有效性,说明答题者不注重代码的健壮性。检查指针的有效性时使用((!strDest)||(!strSrc))或(!(strDest&&strSrc))。

发布于 2011-04-14 分类:algorithm

各大软件公司经典算法面试题

从面试题中去学习

有一个整数数组,请求出两两之差绝对值最小的值,记住,只要得出最小值即可,不需要求出是哪两个数。写一个函数,检查字符是否是整数,如果是,返回其整数值。(或者:怎样只用4行代码编写出一个从字符串到长整形的函数?)给出一个函数来输出一个字符串的所有排列。 请编写实现malloc()内存分配函数功能一样的代码。给出一个函数来复制两个字符串A和B。

发布于 2011-04-03 分类:algorithm

快速排序的递归实现

快速排序的两种不同实现

快速排序是对冒泡排序的一种改进。它的基本思想是:通过一次排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归或者非递归进行,以此达到整个数据变成有序序列。

发布于 2011-03-30 分类:algorithm

非常强悍的堆排序

每次按降序提取元素,这样建立从右到左的有序序列

如何生成m个随机数?看了编程珠玑的文章,知道了一些,后来又在csdn上发现了其他人设计的。如果没有头绪,那就按平常来说就是随机生成一个数,然后比较集合中是否存在,不存在放里面,否则再继续生成。每次按降序提取元素,这样建立从右到左的有序序列。n-1 次siftup 和siftdown ,每个操作最多O(logn),故时间是 O(nlogn),很好很强大啊。

发布于 2011-03-28 分类:algorithm

KMP快速字符串查找算法

亲身体验下KMP算法

KMP字符串查找(匹配)算法最大的好处,并不是它比strstr快,而是它不回溯。这是很奇妙的一个特征。这意味着目标文本只需要提供一个取得下一个字符的函数(在WINX中,这个函数叫get),就可以实现搜索。这对KMP算法的客户而言,无疑是非常有利的一件事情。

发布于 2011-03-22 分类:algorithm

计算从1到N中1的出现次数

算法的时间复杂度是如何减少的

给定一个十进制整数N,求出从1到N的所有整数中出现"1"的个数。例如:N=2,1,2出现了1个"1"。N=12,1,2,3,4,5,6,7,8,9,10,11,12。出现了5个"1"。最直接的方法就是从1开始遍历到N,将其中每一个数中含有"1"的个数加起来,就得到了问题的解。

发布于 2011-03-13 分类:algorithm

字符串逆序的算法汇总

字符串逆序有很多种实现方式

很早就准备写一个字符串系列的面试题,本来已经写好了,大概有十几道题,但是写完才发现,文章好长,连我自己都没有耐心读下去了,索性就将其拆分成几个系列,一来分开后篇幅变小,看起来比较方便。二来也更有针对性,便于精雕细作。比如这篇,在原来的文章中只占很小的篇幅,但是独立出来才发现,东西也不少。既然是第一篇,就来个最最简单的字符串逆序吧。

发布于 2011-03-10 分类:algorithm

将矩阵逆时针旋转90度

矩阵逆时针旋转的算法

旋转矩阵(Rotation matrix)是在乘以一个向量的时候有改变向量的方向但不改变大小的效果的矩阵。旋转矩阵不包括反演,它可以把右手坐标系改变成左手坐标系或反之。所有旋转加上反演形成了正交矩阵的集合。旋转可分为主动旋转与被动旋转。主动旋转是指将向量逆时针围绕旋转轴所做出的旋转。被动旋转是对坐标轴本身进行的逆时针旋转,它相当于主动旋转的逆操作。

发布于 2011-03-06 分类:algorithm

寻找和为给定数的连续正整数数列

寻找更高效的解决方法

对于这种算法的设计,我们最容易想到的就是从 1 到 sn 循环遍历所有的数,对于每个数再循环计算是否以这个数为起点总和正好是sn。这种算法的时间复杂度大概是O(n*log2n), 也就是说如果这样计算,当 sn = 100万时,大概需要循环 2000万次左右。 这样做效率自然是比较低的。那么我们有没有比上述方法更高效的方法呢?答案是肯定的。

发布于 2011-03-05 分类:algorithm
 

copyright © 2009 简明现代魔法    学习、分享、进步

power by Gonn 感谢所有关心和支持本站的朋友们