数据结构面试大全(二) - [算法]

版权声明 ：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://lzhshen.blogbus.com/logs/20356236.html

10, strstr() 的简单实现

strstr(s1,s2) 是一个经常用的函数，他的作用就是在字符串 s1 中寻找字符串 s2 如果找到了就返回指针，否则返回 NULL 。
下面是这个函数的一个简单实现：

static const char* _strstr(const char* s1, const char* s2)

{

     assert(s2 && s1);

     const char* p=s1, *r=s2;

     while(*p!='\0')

     {

          while(*p++==*r++);

          if(*r=='\0')

               return p;

          else

          {

               r=s2;

               p=++s1;

          }

     }

     return NULL;

}

11, 半素数

题 目定义了一种叫半素数的数：只要一个数能被分解成两个素数，那么这个数就是半素数。

Prime Number Definition
An integer greater than one is called a prime number if its only positive divisors (factors) are one and itself. For instance, 2, 11, 67, 89 are prime numbers but 8, 20, 27 are not.

Semi-Prime Number Definition
An integer greater than one is called a semi-prime number if it can be decompounded to TWO prime numbers. For example, 6 is a semi-prime number but 12 is not.

Your task is just to determinate whether a given number is a semi-prime number.

Input

There are several test cases in the input. Each case contains a single integer N (2 <= N <= 1,000,000)

Output

One line with a single integer for each case. If the number is a semi-prime number, then output "Yes", otherwise "No".

Sample Input

3
4
6
12

Sample Output
No
Yes
Yes
No

没什么好说的，解法很简 单，解法如下：

#include <iostream>

#include <cmath>

using namespace std;

bool isprime(long test)

{

     int i;

     for(i=2;i<=sqrt((long double)test);i++)

     {

          if(test%i ==0)

               return false;

     }

     return true;

}

bool isSemiPrime(long test)

{

     int i;

     for(i=2;i<=sqrt((long double)test);i++)

     {

          if(test%i ==0)

          {

               int temp = test/i;

               return isprime(i) && isprime(temp);

          }

     }

     return false;

}

int main()

{

     long n;

     while(cin>>n && n !=0)

     {

          if(isSemiPrime(n))

               cout<<"Yes"<<endl;

          else

               cout<<"No"<<endl;

     }

}

12, 淘汰赛问题

题目：
Our school is planning to hold a new exciting computer programming contest. During each round of the contest, the competitors will be paired, and compete head-to-head. The loser will be eliminated, and the winner will advance to next round. It proceeds until there is only one competitor left, who is the champion. In a certain round, if the number of the remaining competitors is not even, one of them will be chosed randomly to advance to next round automatically, and then the others will be paired and fight as usual. The contest committee want to know how many rounds is needed to produce to champion, then they could prepare enough problems for the contest.

Input
The input consists of several test cases. Each case consists of a single line containing a integer N - the number of the competitors in total. 1 <= N <= 2,147,483,647. An input with 0(zero) signals the end of the input, which should not be processed.

Output
For each test case, output the number of rounds needed in the contest, on a single line.

Sample Input
8
16
15
0

Sample Output
3
4
4

题目比较简单，下面是我给 的解法。其实就是计算一个数是 2 的几次方。

#include <iostream>

using namespace std;

long calculate(long test)

{

     long ret = 0;

     bool is2square = true;

     while(test!=1)

     {

          if(test % 2)

               is2square = false;

          test /= 2;

         ret++;

     }

     if(!is2square)

          ret++;

     return ret;

}

int main()

{

     long n;

     while(cin>>n && n !=0)

     {

          cout<<calculate(n)<<endl;

     }

}

=================================

假定你有一点算法数据结构知识
如果没有的话,所有提到的内容请自行查找,
不推荐提问.

最后偶会说说为什么写这些东西,
为什么选择这些而没有选择另一些.

1 链表找环(探测环形链表) O(n)
A 拓扑排序,删0入度点
B DFS(经过一个点就标记,标记2次的即可判定为环)

2 半素数
(只要一个数能被分解成两个素数，那么这个数就是半素数)
注意时间空间的平衡.
输入N (2<=N<=1000000),输出Y或者N,每行一个,遇0结束

这里只讨论探查找第一个质因数的问题.
A 从 2 到 ceil(sqrt(N)) 取余数探查
B 筛质数,2-1000中的质数进行筛选 (因为对最大的N,ceil(sqrt(N))=1000)
C 小素数筛选,大素数使用 Miller-Rabin 测试

3 LCA(最近公共祖先,Least Common Ancestors) 和 RMQ(Range Minimum/Maximum Query)

先说 RMQ,再说 LCA.
RMQ有n多种方法.
本部分复杂度记法:O(预处理时间)-O(查询时间)

朴素(或许可以称作暴力)DP:
造表,O(n^2)-O(1)

分块,每块大小sqrt(N),总块数sqrt(N),
O(n)-O(sqrt(N))
第一次查询本块,第2次查询所有块的最小值

稀疏表(ST,Sparse Table),存储(i,i+2^j)中的最小值(1<=logn)
O(nlogn)-O(1)
(但是很多人懒的把它写好,所以查询成了O(logn)
存储的是下标,不是数)

类线段树,O(n)-O(logn)

LCA->RMQ: O(n)
深度优先遍历,记录节点深度D[i] 和节点第一次出现的位置(在数组中,R[i])
LCA(i,j)=RMQ(R[i],R[j]) (i<j )
因为每边来回各一次,所以数列中总共 2n-1 项.

相邻两项中相差1(遍历总不能跳着来吧),这样的RMQ也叫+/-1RMQ

RMQ->LCA: O(n)
笛卡尔树(Cartesian Tree),构造时间O(n),具体略

+/-1 RMQ有O(n)-O(1)的算法
将数列分成(2log2n)段,每段长(log2n/2).
用上面提到的稀疏表(ST)方法,
可以在O(N)的时间内完成所有小块的预处理

为什么是O(N)? O(n/(log2n/2) * log2(N/log2n*2) )=O(n)

后面对RMQ的预处理仍然是O(n),具体内容自己查找.

查询是O(1)的,相当的快.

回到正题.
对一般的RMQ进行如下处理
RMQ->LCA->(+/-1)RMQ
都可以达到O(n)-O(1)

另外,LCA还有利用并查集的Tarjan算法,
代码简单,但可惜的是它是离线算法.
====
ps: 没事的同学,看不明白的同学欢迎跳走…

ps2:算法导论第二版偶已经看完了,
如果不考虑证明问题的话,
掌握85%应该是可以达到的

ps3:看了好多关于C函数的面试问题,
这些东西只不过是让你注意一下边界处理问题
(当然偶并不否认它不重要)
很多情况下重做这些东西确实等于重造轮子

ps4:看算法导论不一定就等于会了,欢迎找个Online judge做做题

ps5:写这些东西或许就是来充技术文章的数的?

ps6:这里不是CSDN,写了好文章不会有人推你上首页.

废话了这么多,赶紧结束.

历史上的今天：

Principles of Modeling and Analysis with UML 2008-05-06

随机文章：

数据结构面试大全(一) 2008-05-05

进程调度算法摘要[Page 93 (continued)] 2008-05-05

常见内存分配算法及优缺点 2008-05-04

各种内部排序算法复杂度的比较和排序方法 的选择 2008-04-30

排序算法一览 2008-04-30

收藏到：Del.icio.us

<script src="http://www.blogbus.com/ads/ads.js" type="text/javascript"></script><script src="http://pro.blogbus.com/useruploads/js/1d/1dde2a19e2cfd2a8279fc8e74f18f468.js" type="text/javascript"></script>

Tag：算法 面试

引用地址：

lzhshen 发表于10:10:56 | 编辑 | 继续话题 | 转发 | 分享　0

<!-- /list-->

<script src="http://public.blogbus.com/imgs/jquery.js"></script>

<script src="http://public.blogbus.com/imgs/picobox/picobox.js" type="text/javascript"></script><script src="http://public.blogbus.com/imgs/picobox/picobox_beauty/picobox_beauty.js" type="text/javascript"></script>

发表评论

姓　名 登录后评 论

E-Mail 您将收到博主的回复邮件

地　址

用户名 匿名评论

密　码

<script src="http://blog.home.blogbus.com/front/4470434/comments/20356236/cmt_form" type="text/javascript"></script><script type="text/javascript">var post_ids='20356236';</script><script src="http://app.home.blogbus.com/share/number?id=20356236" type="text/javascript"></script><script>function share_click(id){var num = parseInt(document.getElementById(id).innerHTML); num++;document.getElementById(id).innerHTML= ' '+num;}</script><script src="http://public.blogbus.com/blogbus/skin/common/helper1.js?v1024" type="text/javascript"></script>

个人资料

lzhshen

日历

<script type="text/javascript">var _blogid=4470434;var iCY=2010;var iCM=01;var iCD=21;var iCS=false;var sDCP = &quot;&quot;;var sDCN = &quot;&quot;;var LDWD = new Array();</script><script src="http://lzhshen.blogbus.com/user/js/calendar2.js"></script>

«  2010年 1月 »
日	一	二	三	四	五	六
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

搜索

管理

• 进入后台 写新日志
• 文章管理 评论管理
• 更换模板 访问统计

文章分类

• Linux[16]
• 全景图[1]
• C&C++[6]
• 操作系统[3]
• 算法[5]
• web service[1]
• perl[6]
• english[5]

Tag

• 算 法[6]
• linux[5]
• ubuntu[5]
• 排序[3]
• debug[2]

More..

最新文章

• linux debug tool
• debug python script
• 查看被占用端口
• unix network programming
• C++ — Convert int to string
• ubuntu 下搭建 nfs 服务
• vmware server 添加磁盘
• PostgreSQL数据 的导出导入
• How to umount when the device is busy
• sources.list

全部日 志>>

最新评论

• 失眠怎么办 ：都没人顶下，我帮你顶下！...

链接

存档

• 2009 [10]
• 2008 [38]

• 什么是RSS？
  
  
  
  
  
• 
  
  博客大巴使用指南
  博客大 巴模板中心
  免费注册博客大巴
  一键博客搬 家工具
  中文互动杂志城客