ITeye博客

rein07的博客

rein07 · 共 20 篇文章

KMP快速字符串查找算法

在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库的strstr()函数来完成的,这在通常的情况下,因为字符串的搜索操作不多,并不会产生效率问题。实际上,这个函数的时间复杂度不容乐观。如果要从长度为n的字符串中查找长度为m的子字符串,那么这个strstr()函数的最坏时间复杂度为O(n*m),可见,随着子字符串长度m的增大,strstr()函数的时间复杂度也相应地成倍增加,有没有更加高效的算法呢? KMP(Knuth-Morris-Pratt)算法通过预先计算模式字符串中相应字符处的回溯索引,避免了模式匹配时不必要的回溯操作,从而提高了效率,将时间复杂度变成了O(m+n)。 KM…

2011-08-25 19:29 · 算法 · 评论(0)

求解最大公约数问题

最大公因数,又称最大公约数。是指 的最大公因数。通常有两种表示方式: 它们的所有公因数中最大的那一个; 如果自然数 m 是这 n 个自然数的公因数,且这 n 个数的任意公因数都是 m 的因数,就称 m 是这 n 个数的最大用因数。通常国内的记述方式为 ,国际通用的记号为 。 欧几里得算法(Euclidean Algorithm)(Euclid‘s 算法)就是通常所说的求最大公因数的辗转相除法。算法描述如下: 如果 a 除以 b 能整除,则最大公约数是 b; 否则,最大公约数等于 b 和 a % b的公约数。 代码实现如下: #include <stdio.h> int Euclidean(i…

2011-08-25 19:27 · 算法 · 评论(0)

堆排序(Heap Sort)算法学习

在程序设计相关领域,堆(Heap)的概念主要涉及到两个方面: 一种数据结构,逻辑上是一颗完全二叉树,存储上是一个数组对象(二叉堆)。 垃圾收集存储区,是软件系统可以编程的内存区域。 本文所说的堆,指的是前者。 堆排序的时间复杂度是O(nlgN),与快速排序达到相同的时间复杂度。但是在实际应用中,我们往往采用快速排序而不是堆排序。这是因为快速排序的一个好的实现,往往比堆排序具有更好的表现。堆排序的主要用途,是在形成和处理优先级队列方面。另外,如果计算要求是类优先级队列(比如,只要返回最大或者最小元素,只有有限的插入要求等),堆同样是很适合的数据结构。 基础知识 堆一般用数组表示,比如数组A数组…

2011-08-25 19:26 · 算法 · 评论(0)

整数拆分问题的动态规划解法

输入n,和k,问将n用1到k这k个数字进行拆分,有多少种拆分方法。例如:n=5,k=3 则有n=3+2, n=3+1+1, n=2+1+1+1, n=2+2+1, n=1+1+1+1+1这5种拆分方法。 这个题目是个比较明显的动态规划,如果想不到是背包问题,也可以写出状态转移方程如下。 用a 表示考虑到用数j进行拼接时数字i的拼接方法,可以得到状态转移方程如下:a =a*+a+a+a…+a意思很明显,就将j-1状态可以到达a*的状态的数字相加。由于得到的结果可能相当大,已经超过了long long,所以应该用大数。但是若跑完所有数据,用大数会超过一秒,我们通过大数的程序可以达到,最大的数字为…

2011-08-25 19:26 · 算法 · 评论(0)

背包问题介绍与分析

背包问题是在1978年由Merkel和Hellman提出的。它的主要思路是假定某人拥有大量物品,重量各不同。此人通过秘密地选择一部分物品并将它们放 到背包中来加密消息。背包中的物品中重量是公开的,所有可能的物品也是公开的,但背包中的物品是保密的。附加一定的限制条件,给出重量,而要列出可能的物品,在计算上是不可实现的。背包问题是熟知的不可计算问题,背包体制以其加密,解密速度快而其人注目。但是,大多数一次背包体制均被破译了,因此现在很少有人使用它。 P01:01背包问题 题目:有N件物品和一个容量为V的背包。第i件物品的费用是c,价值是w。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容…

2011-08-25 19:24 · 算法 · 评论(0)

求平方根sqrt()函数的底层算法效率问题

我们平时经常会有一些数据运算的操作,需要调用sqrt,exp,abs等函数,那么时候你有没有想过:这个些函数系统是如何实现的?就拿最常用的sqrt函数来说吧,系统怎么来实现这个经常调用的函数呢? 虽然有可能你平时没有想过这个问题,不过正所谓是“临阵磨枪,不快也光”,你“眉头一皱,计上心来”,这个不是太简单了嘛,用二分的方法,在一个区间中,每次拿中间数的平方来试验,如果大了,就再试左区间的中间数;如果小了,就再拿右区间的中间数来试。比如求sqrt(16)的结果,你先试(0+16)/2=8,8 8=64,64比16大,然后就向左移,试(0+8)/2=4,4 4=16刚好,你得到了正确的结果sqr…

2011-08-25 19:23 · 算法 · 评论(0)

面试中常见的一些算法问题

Problem 1 : Is it a loop ? (判断链表是否有环?) Assume that wehave a head pointer to a link-list. Also assumethat we know the list is single-linked. Can you come up an algorithm to checkwhether this link list includes a loop by using O(n) time and O(1) space wheren is the length of the list? Furthermore, ca…

2011-08-25 19:22 · 算法 · 评论(0)

各种排序算法的C++实现与性能比较

排序是计算机算法中非常重要的一项,而排序算法又有不少实现方法,那么哪些排序算法比较有效率,哪些算法在特定场合比较有效,下面将用C++实现各种算法,并且比较他们的效率,让我们对各种排序有个更深入的了解。 minheap.h 用于堆排序: view sourceprint?001 //使用时注意将关键码加入 002 #ifndef MINHEAP_H 003 #define MINHEAP_H 004 #include <assert.h> 005 #include 006 using std::cout; 007 using std::cin; 008 using std::endl; 009…

2011-08-25 19:21 · 算法 · 评论(0)

背包问题之硬币找零问题

设有6 种不同面值的硬币,各硬币的面值分别为5 分,1 角,2 角,5 角,1 元,2元。现要用这些面值的硬币来购物和找钱。购物时可以使用的各种面值的硬币个数存于数组Coins中,商店里各面值的硬币有足够多。在1次购物中希望使用最少硬币个数。例如,1 次购物需要付款0.55 元,没有5 角的硬币,只好用2*20+10+5 共4 枚硬币来付款。如果付出1 元,找回4 角5 分,同样需要4 枚硬币。但是如果付出1.05 元(1 枚1元和1 枚5分),找回5 角,只需要3 枚硬币。这个方案用的硬币个数最少。 对于给定的各种面值的硬币个数和付款金额,计算使用硬币个数最少的交易方案。 Input:输入…

2011-08-25 19:19 · 算法 · 评论(0)

求能被1到20的数整除的最小正整数

求能被1到20的数整除的最小正整数。最直觉的方法是求1到20这20个数的最小公倍数。 求n个数的最小公倍数,以a,b,c三个数为例,他们的最小公倍数等于:先求a与b的最小公倍数m,然后m和c的最小公倍数即着三个数的最小公倍数。 求两个数a,b的最小公倍数嘛,先取出其中较大的那个比如a,然后再用k a去试探能否被较小那个数整除,其中,k是从1开始的自然数 k a<a*b。 int get_lcm(int a, int b) { if(a==b) { return a; } int bigger = a<b?b:a; int smaller= a<b?a:b; int max = a*b; in…

2011-08-25 19:18 · 算法 · 评论(0)

买书折扣最优惠问题解法

题目:在节假日的时候,书店一般都会做促销活动。由于《哈利波特》系列相当畅销,店长决定通过促销活动来回馈读者。在销售的《哈利波特》平装本系列中,一共有五卷,用编号0, 1, 2, 3, 4来表示。假设每一卷单独销售均需要8欧元。如果读者一次购买不同的两卷,就可以扣除5%的费用,三卷则更多。假设具体折扣的情况如下: view sourceprint?1 本数 折扣 2 2 5% 3 3 10% 4 4 20% 5 5 25% 在一份订单中,根据购买的卷数以及本书,就会出现可以应用不同折扣规则的情况。但是,一本书只会应用一个折扣规则。比如,读者一共买了两本卷一,一本卷二。那么,可以享受到5%的折扣…

2011-08-25 19:17 · 算法 · 评论(0)

二叉树中的最近公共祖先问题

题目:要求寻找二叉树中两个节点的最近的公共祖先,并将其返回。 view sourceprint?1 class Node 2 { 3 Node * left; 4 Node * right; 5 Node * parent; 6 }; 7 / 查找p,q的最近公共祖先并将其返回。 / 8 Node * NearestCommonAncestor(Node * p,Node * q); 算法思想:这道题的关键在于每个节点中包含指向父节点的指针,这使得程序可以用一个简单的算法实现。首先给出p的父节点p->parent,然后将q的所有父节点依次和p->parent作比较,如果发现两个节点相等,则该…

2011-08-25 19:16 · 算法 · 评论(0)

判断一个整数是否是2的N次方

题目:给定一个整数num,判断这个整数是否是2的N次方。比如,2,4,8是2的那次方,6,10不是2的N次方。 请看下面的程序: public static bool Check1(int num) { int i = 1; while (true) { if (i > num) return false; if (i == num) return true; i = i * 2; } } 不断的循环num%2,如果不等于0,return false,如果等于0,num=num/2,一直做到num=1 public static bool Check2(int num) { if (num …

2011-08-25 19:04 · 算法 · 评论(0)

字符串逆序的算法汇总

很早就准备写一个字符串系列的面试题,本来已经写好了,大概有十几道题,但是写完才发现,文章好长,连我自己都没有耐心读下去了,索性就将其拆分成几个系列,一来分开后篇幅变小,看起来比较方便。二来也更有针对性,便于精雕细作。比如这篇,在原来的文章中只占很小的篇幅,但是独立出来才发现,东西也不少。既然是第一篇,就来个最最简单的字符串逆序吧。 字符串逆序可以说是最经常考的题目。这是一道入门级的题目,相信80%的程序员经历过这道题。给定一个字符串s,将s中的字符顺序颠倒过来,比如s="abcd",逆序后变成s="dcba"。 普通逆序 基本上没有这么考的,放在这里主要是为了和后面的原地逆序做个对比。很简单…

2011-08-25 19:01 · 算法 · 评论(0)

计算从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"的个数加起来,就得到了问题的解。 view sourceprint?01 public long CountOne3(long n) 02 { 03 long i = 0,j = 1; 04 long count = 0; 05 for (i = 0; i <= n; i++) 06 { 07 j = i; 08 while (j != 0) 0…

2011-08-25 18:59 · 算法 · 评论(0)