rein07
- 浏览: 21825 次
- 性别:
- 来自: 南京
-
最新评论
文章列表
KMP快速字符串查找算法
- 博客分类：
- 算法
在C/C++语言编程过程中，一般的字符串搜索操作都是通过标准库的strstr()函数来完成的，这在通常的情况下，因为字符串的搜索操作不多，并不会产生效率问题。实际上，这个函数的时间复杂度不容乐观。如果要从长度为n的字符串中查找长度为m的子字符串，那么这个strstr()函数的最坏时间复杂度为O(n*m)，可见，随着子字符串长度m的增大，strstr()函数的时间复杂度也相应地成倍增加，有没有更加高效的算法呢？
KMP（Knuth-Morris-Pratt）算法通过预先计算模式字符串中相应字符处的回溯索引，避免了模式匹配时不必要的回溯操作，从而提高了效率，将时间复杂度变成了O(m+n)。
KM ...
最大公因数，又称最大公约数。是指 [n(≧2)个自然数 a1, a2, ..., an] 的最大公因数。通常有两种表示方式：
它们的所有公因数中最大的那一个；
如果自然数 m 是这 n 个自然数的公因数，且这 n 个数的任意公因数都是 m 的因数，就称 m 是这 n 个数的最大用因数。通常国内的记述方式为 [(a1, a2, ..., an)] ，国际通用的记号为 [g.c.d.(a1, a2, ..., an)]。
欧几里得算法(Euclidean Algorithm)(Euclid‘s 算法)就是通常所说的求最大公因数的辗转相除法。算法描述如下：
如果 a 除以 b 能整除，则最大公 ...
堆排序(Heap Sort)算法学习
- 博客分类：
- 算法
在程序设计相关领域，堆(Heap)的概念主要涉及到两个方面：
一种数据结构，逻辑上是一颗完全二叉树，存储上是一个数组对象（二叉堆）。
垃圾收集存储区，是软件系统可以编程的内存区域。
本文所说的堆，指的是前者。
...
整数拆分问题的动态规划解法
- 博客分类：
- 算法
输入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[i][j]表示考虑到用数j进行拼接时数字i的拼接方法，可以得到状态转移方程如下：a[i][j]=a[i][j-1]+a[i-j][j-1]+a[i-2j][j-1]+a[i-3j][j-1]…+a[0][j-1]意思很明显，就将j-1状态可以到达a[i][j]的状态的数字相加。由于得到的结果可能相当大， ...
背包问题是在1978年由Merkel和Hellman提出的。它的主要思路是假定某人拥有大量物品，重量各不同。此人通过秘密地选择一部分物品并将它们放 到背包中来加密消息。背包中的物品中重量是公开的，所有可能的物品也是公开的，但背包中的物品是保密的。附加一定的限制条件，给出重量，而要列出可能的物品，在计算上是不可实现的。背包问题是熟知的不可计算问题，背包体制以其加密，解密速度快而其人注目。但是，大多数一次背包体制均被破译了，因此现在很少有人使用它。
P01：01背包问题
题目：有N件物品和一个容量为V的背包。第i件物品的费用是c，价值是w。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量 ...
求平方根sqrt()函数的底层算法效率问题
- 博客分类：
- 算法
我们平时经常会有一些数据运算的操作，需要调用sqrt，exp，abs等函数，那么时候你有没有想过：这个些函数系统是如何实现的？就拿最常用的sqrt函数来说吧，系统怎么来实现这个经常调用的函数呢？
虽然有可能你平时没有想过这个问题，不过正所谓是“临阵磨枪，不快也光”，你“眉头一皱，计上心来”，这个不是太简单了嘛，用二分的方法，在一个区间中，每次拿中间数的平方来试验，如果大了，就再试左区间的中间数；如果小了，就再拿右区间的中间数来试。比如求sqrt(16)的结果，你先试（0+16）/2=8，8*8=64，64比16大，然后就向左移，试（0+8）/2=4，4*4=16刚好，你得到了正确的结果sqrt ...
面试中常见的一些算法问题
- 博客分类：
- 算法
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 ...
各种排序算法的C++实现与性能比较
- 博客分类：
- 算法
排序是计算机算法中非常重要的一项，而排序算法又有不少实现方法，那么哪些排序算法比较有效率，哪些算法在特定场合比较有效，下面将用C++实现各种算法，并且比较他们的效率，让我们对各种排序有个更深入的了解。
minheap.h 用于堆排序：
view sourceprint?001 //使用时注意将关键码加入
002 #ifndef MINHEAP_H
003 #define MINHEAP_H
004 #include <assert.h>
005 #include <iostream>
006 using std::cout;
007 ...
背包问题之硬币找零问题
- 博客分类：
- 算法
设有6 种不同面值的硬币，各硬币的面值分别为5 分，1 角，2 角，5 角，1 元，2元。现要用这些面值的硬币来购物和找钱。购物时可以使用的各种面值的硬币个数存于数组Coins[1:6]中，商店里各面值的硬币有足够多。在1次购物中希 ...
求能被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;
...
买书折扣最优惠问题解法
- 博客分类：
- 算法
题目：在节假日的时候，书店一般都会做促销活动。由于《哈利波特》系列相当畅销，店长决定通过促销活动来回馈读者。在销售的《哈利波特》平装本系列中，一共有五卷，用编号0, 1, 2, 3, 4来表示。假设每一卷单独销售均需要 ...
二叉树中的最近公共祖先问题
- 博客分类：
- 算法
题目：要求寻找二叉树中两个节点的最近的公共祖先，并将其返回。
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-> ...
判断一个整数是否是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，如果等 ...
字符串逆序的算法汇总
- 博客分类：
- 算法
很早就准备写一个字符串系列的面试题，本来已经写好了，大概有十几道题，但是写完才发现，文章好长，连我自己都没有耐心读下去了，索性就将其拆分成几个系列，一来分开后篇幅变小，看起来比较方便。二来也更有针对性，便于精雕细作。比如这篇，在原来的文章中只占很小的篇幅，但是独立出来才发现，东西也不少。既然是第一篇，就来个最最简单的字符串逆序吧。
字符串逆序可以说是最经常考的题目。这是一道入门级的题目，相信80%的程序员经历过这道题。给定一个字符串s，将s中的字符顺序颠倒过来，比如s="abcd"，逆序后变成s="dcba"。
普通逆序
基本上没有这么考的，放在这里主 ...
计算从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" ...