常见算法整理（一）

双十一已经过去了，闲暇时间收集了一些算法试题，分享一下！

1、实现一个函数，对一个正整数n，算得到1需要的最少操作次数。操作规则为：如果n为偶数，将其除以2；如果n为奇数，可以加1或减1；一直处理下去。 

例子：
func(7) = 4，可以证明最少需要4次运算
n = 7
n-1 6
n/2 3
n-1 2
n/2 1
要求：实现函数(实现尽可能高效) int func(unsign int n)；n为输入，返回最小的运算次数。给出思路(文字描述)，完成代码，并分析你算法的时间复杂度。

<?php
function func($n)
{
    if($n == 1)
        return 0;
    if($n % 2 == 0)
        return 1 + func($n/2);
    $x = func($n + 1);
    $y = func($n - 1);
    if($x > $y)
        return $y+1;
    else
        return $x+1;
}
echo func(7);
?>

2、一个大的含有50M个URL的记录，一个小的含有500个URL的记录，找出两个记录里相同的URL。

首先使用包含500个url的文件创建一个hash_set。
然后遍历50M的url记录，如果url在hash_set中，则输出此url并从hash_set中删除这个url。
所有输出的url就是两个记录里相同的url。

3、海量日志数据，提取出某日访问淘宝次数最多的那个IP。

回答：
如果日志文件足够的大，大到不能完全加载到内存中的话。那么可以考虑分而治之的策略。
1）按照IP地址的hash(IP)%1024值，将海量日志存储到1024个小文件中。
2）对于每个小文件，可以构建一个IP作为key，出现次数作为value的hash_map，并记录当前出现次数最多的1个IP地址。HASH['10.231.250.234']=0
3）有了1024个小文件中的出现次数最多的IP，我们就可以轻松得到总体上出现次数最多的IP。

4、有10个文件，每个文件1G，每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。如何按照query的频度排序？

回答：
1）读取10个文件，按照hash(query)%10的结果将query写到对应的文件中。这样我们就有了10个大小约为1G的文件。任意一个query只会出现在某个文件中。
2）对于1）中获得的10个文件，分别进行如下操作
　　- 利用hash_map（query，query_count）来统计每个query出现的次数。
　　- 利用堆排序算法对query按照出现次数进行排序。
　　- 将排序好的query输出的文件中。
　　- 这样我们就获得了10个文件，每个文件中都是按频率排序好的query。
3）对2）中获得的10个文件进行归并排序，并将最终结果输出到文件中。

5、蚂蚁爬杆问题
　有一根27厘米长的细木杆，在第3厘米，7厘米，11厘米，17厘米，23厘米这五个位置上各有一只蚂蚁，木杆很细，不能同时通过两只蚂蚁，开始时，蚂蚁的头朝向左还是右是任意的，他们只会朝前走或掉头，但不会后退，当两只蚂蚁相遇后，蚂蚁会同时掉头朝反方向走，假设蚂蚁们每秒钟可以走1厘米的距离。求所有蚂蚁都离开木杆的最小时间和最大时间。

答案：
　两只蚂蚁相遇后，各自掉头朝相反方向走。如果我们不考虑每个蚂蚁的具体身份，这和两只蚂蚁相遇后，打个招呼继续向前走没有什么区别。
　所有蚂蚁都离开木杆的最小时间为：max(min(3,27-3),min(7,27-7), min(11,27-11), min(17,27-17),min(23,27-23))=11
　所有蚂蚁都离开木杆的最大时间为：max(max(3,27-3),max(7,27-7), max(11,27-11), max(17,27-17),max(23,27-23))=24

6、当在浏览器中输入一个url后回车，后台发生了什么？比如输入url后，你看到了淘宝的首页，那么这一切是如何发生的呢？

回答：
　　简单来说有以下步骤：
　　1、查找域名对应的IP地址。这一步会依次查找浏览器缓存，系统缓存，路由器缓存，ISPDNS缓存，根域名服务器。
　　2、向IP对应的服务器发送请求。
　　3、服务器响应请求，发回网页内容。
　　4、浏览器解析网页内容。
详细内容可以参考：http://www.cnblogs.com/liqiu/archive/2013/05/23/3094728.html

7、判断两棵树是否相等，请实现两棵树是否相等的比较，相等返回1，否则返回其他值，并说明算法复杂度。

数据结构是：

typedef struct TreeNode
{
    char c;
    TreeNode *leftchild;
    TreeNode *rightchild;
}TreeNode;

函数接口为：int CompTree(TreeNode* tree1,TreeNode* tree2);

注：A、B两棵树相等当且仅当RootA->c==RootB-->c,而且A和B的左右子树相等或者左右互换相等。
递归方法：

bool CompTree(TreeNode *tree1, TreeNode *tree2)
{
    if(tree1 == NULL && tree2 == NULL)
        return true;
    if(tree1 == NULL || tree2 == NULL)
        return false;
    if(tree1->c != tree2->c)
        return false;
    if( (CompTree(tree1->leftchild, tree2->leftchild) && CompTree(tree1->rightchild, tree2->rightchild)) || CompTree(tree1->leftchild, tree2->rightchild) && CompTree(tree1->rightchild, tree2->leftchild))
        return true;
}

时间复杂度：
在树的第0层，有1个节点，我们会进行1次函数调用；
在树的第1层，有2个节点，我们可能会进行4次函数调用；
在树的第2层，有4个节点，我们可能会进行16次函数调用；
....
在树的第x层，有2^x个节点，我们可能会进行(2^x)^2次函数调用；
所以假设总节点数为n，则算法的复杂度为O(n^2)。

8、求一个论坛的在线人数，假设有一个论坛，其注册ID有两亿个，每个ID从登陆到退出会向一个日志文件中记下登陆时间和退出时间，要求写一个算法统计一天中论坛的用户在线分布，取样粒度为秒。

回答：
一天总共有3600*24=86400秒。
每秒中的人数变化情况：
      定义一个长度为86400的整数数组intdelta[86400]，每个整数对应这一秒的人数变化值，可能为正也可能为负。
　　然后依次读入每个用户的登录时间和退出时间，将与登录时间对应的整数值加1，将与退出时间对应的整数值减1。
　　这样处理一遍后数组中存储了每秒中的人数变化情况。

每秒中论坛的在线人数:
　　定义另外一个长度为86400的整数数组intonline_num[86400]，每个整数对应这一秒的论坛在线人数。与上面的方法类似，区别是在其登陆的时间内每一秒都加一，第二秒也加一类似
    if (第一秒登录了一个人)
    第一秒：   intdelta[1] = 1; 
    第二秒：   intdelta[2] = intdelta[1];
    if (第三秒登录了三个人)
    第三秒：   intdelta[3] = 3 + intdelta[2];
    if (第十秒退出了两个人)
    第十秒：   intdelta[10] = intdelta[9] - 2;
   这样就获得了论坛的在线人数

  

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/liqiu/p/3421391.html