`
rein07
  • 浏览: 21903 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论
文章列表
在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)的概念主要涉及到两个方面: 一种数据结构,逻辑上是一颗完全二叉树,存储上是一个数组对象(二叉堆)。 垃圾收集存储区,是软件系统可以编程的内存区域。 本文所说的堆,指的是前者。 ...
输入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,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++实现各种算法,并且比较他们的效率,让我们对各种排序有个更深入的了解。 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这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-> ...
题目:给定一个整数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"。 普通逆序 基本上没有这么考的,放在这里主 ...
给定一个十进制整数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" ...
Global site tag (gtag.js) - Google Analytics