以图明志

计算机算法

用递归实现的快速排序

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

计算机算法

从1到N这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"的个数加起来,就得到了问题的解。

计算机算法

字符串逆序的各种实现算法

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

计算机算法

矩阵逆时针旋转的算法

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

计算机算法

求和为指定数字的连续正整数数列

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

计算机算法

如何判定一个数是否为2的N次方

最保险的还是位运算
给定一个整数num,判断这个整数是否是2的N次方。比如,2,4,8是2的那次方,6,10不是2的N次方。因此我觉得, 最保险的还是位运算, 看多少个1, 来的最实在。当然这里存在一个负数的问题。第一位是1, 剩下全是0的问题。 不过有一位聪明的回复者提供了一个很强大的方法来避开负数的用例:他给参数定的类型是uint!

计算机算法

面试算法题的快速思考方法

面对一个问题,改如何下手思考将其解决
一般关于算法的文章,都是从经典算法讲起,一种一种算法介绍,见得算法多了,自然就有了感悟,但如此学习花费的时间和精力却是过于巨大,也不适合在博客里面交流。这一篇文,却是专门讲快捷思路的,很多人面对算法题的时候几乎是脑子里一片空白,这一篇文章讲的就是从题目下手,把毫无思路的题目打开一个缺口的几种常见技巧。

计算机算法

如何不使用额外变量来交换两变量

不使用第三个变量互换两个变量的方法
交换两个变量,通常我们的做法是(尤其是在学习阶段):定义一个新的变量,借助它完成交换。这种算法易于理解,特别适合帮助初学者了解计算机程序的特点,是赋值语句的经典应用。在实际软件开发当中,此算法简单明了,不会产生歧义,便于程序员之间的交流,一般情况下碰到交换变量值的问题,都应采用此算法。

计算机算法

上楼梯有几种走法问题

斐波那契数列的多种算法实现
假设一个楼梯有 N 阶台阶,人每次最多可以跨 M 阶。例如楼梯总共有3个台阶,人每次最多跨2个台阶,也就是说人每次可以走1个,也可以走2个,但最多不会超过2个,那么楼梯总共有这么3种走法。现在要求用程序实现计算台阶的所有走法的总数。其实就是个斐波那契数列。

计算机算法

JavaScript各种排序的性能比较

各种排序算法在JavaScript下的表现
排序是经常使用的编程例子,在JavaScript里各种排序的性能又如何呢?每个浏览器测试得出的数据会不一样。比如我用chrome 测试 一般快速排序都会最快,IE 则根据数组长度有可能希尔最快。不要用太大数据去测试冒泡排序(浏览器崩溃了我不管)。

计算机算法

编程之美中的买书最优惠问题

买书问题常数时间空间解法
题目:在节假日的时候,书店一般都会做促销活动。由于《哈利波特》系列相当畅销,店长决定通过促销活动来回馈读者。在销售的《哈利波特》平装本系列中,一共有五卷,用编号0, 1, 2, 3, 4来表示。假设每一卷单独销售均需要8欧元。如果读者一次购买不同的两卷,就可以扣除5%的费用,三卷则更多。

计算机算法

什么是极大极小博弈树?

Minimax Game Tree介绍
极大极小博弈树(Minimax Game Tree)用于编写电脑之间的游戏程序,这类程序由两个游戏者轮流,每次执行一个步骤。当然,所有可能的步骤构成了一个树的结构。例如下面的图就是一个MGT,它表示了Tic-Tac-Toe游戏的前两步所有可能的步骤。

计算机算法

一个优化的堆排序

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

计算机算法

关于背包的硬币找零问题

解题思路:01背包,完全背包
设有6 种不同面值的硬币,各硬币的面值分别为5 分,1 角,2 角,5 角,1 元,2元。现要用这些面值的硬币来购物和找钱。购物时可以使用的各种面值的硬币个数存于数组Coins[1:6]中,商店里各面值的硬币有足够多。在1次购物中希望使用最少硬币个数。例如,1 次购物需要付款0.55 元,没有5 角的硬币,只好用2*20+10+5 共4 枚硬币来付款。

计算机算法

亲身体验一下KMP算法

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

计算机算法

被1至20整除的最小正整数问题

一个思考的小捷径
求能被1到20的数整除的最小正整数。最直觉的方法是求1到20这20个数的最小公倍数。求n个数的最小公倍数,以a,b,c三个数为例,他们的最小公倍数等于:先求a与b的最小公倍数m,然后m和c的最小公倍数即着三个数的最小公倍数。
3 / 6 首页 < Prev 1 2 3 4 5 Next > 尾页 页码: