哈夫曼树（一） C语言详解

2017年02月05日 38 阅读

哈夫曼树（一） C语言详解2014-12-22哈夫曼树的介绍Huffman Tree，中文名是哈夫曼树或霍夫曼树，它是最优二叉树。定义：给定n个权值作为n个叶子结点，构造一棵二叉树，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树。这个定义里面涉及到了几个陌生的概念，下面就是一颗哈夫曼树，我们来看图解答。（01） 路径和路径长度定义：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为...

哈夫曼树（二） C++详解

2017年02月05日 36 阅读

哈夫曼树（二） C++详解2014-12-22哈夫曼树的介绍Huffman Tree，中文名是哈夫曼树或霍夫曼树，它是最优二叉树。定义：给定n个权值作为n个叶子结点，构造一棵二叉树，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树。这个定义里面涉及到了几个陌生的概念，下面就是一颗哈夫曼树，我们来看图解答。（01） 路径和路径长度定义：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为...

哈夫曼树（三） Java详解

2017年02月05日 37 阅读

哈夫曼树（三） Java详解2014-12-22哈夫曼树的介绍Huffman Tree，中文名是哈夫曼树或霍夫曼树，它是最优二叉树。定义：给定n个权值作为n个叶子结点，构造一棵二叉树，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树。这个定义里面涉及到了几个陌生的概念，下面就是一颗哈夫曼树，我们来看图解答。（01） 路径和路径长度定义：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数...

算法练习：Eratosthenes 筛选法

2017年02月05日 43 阅读

算法练习：Eratosthenes 筛选法2014-12-22题目：Eratosthenes筛选法内容：求质数是一个很普遍的问题，通常不外乎用数去除，除到不尽时，给定的数就是质数。但是早在2000年前人们就知道了一个不必用除法而找出2~N的所有质数的方法。假设一个很神奇的筛子，可以给出一个数，例如i，这个筛子有办法把i所有的倍数去掉。请用这个方法求出2~N之间的所有质数。即Eratosthenes筛选法。我的解法：上来没多想，打开vs2013就敲了起来，问...

算法练习：求质数

2017年02月05日 34 阅读

算法练习：求质数2014-12-22题目：求质数内容：试编写一个程序，找出前N个质数。如果没有进一步要求，这不是难题。但在此希望从所知的、使用除法的方法中，用最快的办法来编写程序。我的解法：上来没多想，打开vs2013就敲了起来，问题果然很简单，分分钟就超神。。奥，不对就解决了！这个题目确实很简单，先看看常规解法吧！#include <iostream>#include <math.h>#define endNum 200using...

并行化频繁模式挖掘算法FP Growth及其在Mahout下的命令使用

2017年02月05日 39 阅读

并行化频繁模式挖掘算法FP Growth及其在Mahout下的命令使用2014-12-24今天调研了并行化频繁模式挖掘算法PFP Growth及其在Mahout下的命令使用，简单记录下试验结果，供以后查阅：环境：Jdk1.7 + Hadoop2.2.0单机伪集群 + Mahout0.6（0.8和0.9版本都不包含该算法。Mahout0.6可以和Hadoop2.2.0和平共处有点意外orz）部分输入数据，输入数据一行代表一个购物篮：4750,19394,25...

谷歌面试题解析：寻找丑数

2017年02月05日 39 阅读

谷歌面试题解析：寻找丑数2014-12-24题目：我们把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第1500个丑数。分析：这是一道在网络上广为流传的面试题，据说google曾经采用过这道题。这段题刚开始的想法是从1开始递增遍历，找出1500个是丑数的数，并打印出来。实现如下：#include<stdio.h>#include&...

微软面试题解析：调整数组顺序使奇数位于偶数前面（数组）

2017年02月05日 37 阅读

微软面试题解析：调整数组顺序使奇数位于偶数前面（数组）2014-12-24题目：输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O（n）。分析：只需要设置头尾两个指针遍历就可以了，前面遇到偶数记下来，后面遇到奇数记下来，交换，知道后面的指针小于前面的指针。实现如下：#include<iostream>#include<stdio.h>#include<stdl...

百度面试题解析：字符串的排列（字符串）

2017年02月05日 39 阅读

百度面试题解析：字符串的排列（字符串）2014-12-24题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则输出由字符a, b, c 所能排列出来的所有字符串abc, acb, bac, bac, cab和cab。分析：这题主要考递归思想。依次取出每个字符，剩下的字符的字符串所有排列都打印出来，再加上开始的字符。实现：#include<iostream>#include<stdio.h>#include&...

网易面试题解析：和为n连续正数序列（数组）

2017年02月05日 36 阅读

网易面试题解析：和为n连续正数序列（数组）2014-12-24网易面试题：和为n连续正数序列（数组）题目：输入一个正数n，输出所有和为n连续正数序列。例如：输入15，由于 1+ 2 + 3 + 4 +5 = 4 + 5 + 6 = 7 + 8 = 15， 所以输入3个连续序列1,2,3,4,5 和 4,5,6 和7,8。分析：找连续序列可以从2个开始找，再找3个，4个等等，那到什么时候结束呢？当发现找到的k个数的起始数小于1，终止。还可以分析出，当k为偶数...

腾讯面试题解析：重复短信问题

2017年02月05日 35 阅读

腾讯面试题解析：重复短信问题2014-12-24有一千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。有一千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。请用5分钟时间，找出重复出现最多的前10条。分析：常规方法是先排序，在遍历一次，找出重复最多的前10条。但是排序的算法复杂度最低为nlgn。可以设计一个hash_table, hash_map<string, int>，依次读取一千万条短信，加载到hash_table表中...

微软面试题解析：请修改append函数， 利用函数实现（链表）

2017年02月05日 39 阅读

微软面试题解析：请修改append函数， 利用函数实现（链表）2014-12-24题目：请修改append函数，利用这个函数实现：两个非降序链表的并集，1->2->3 和 2->3->5 并为 1->2->3->5另外只能输出结果，不能修改两个链表的数据。分析：这题很简单，两个指向链表的指针，比较对应的值，并遍历实现如下：#include<iostream>using namespace std;str...

百度研发笔试题解析：设计一个系统处理词语搭配问题

2017年02月05日 36 阅读

百度研发笔试题解析：设计一个系统处理词语搭配问题2014-12-24题目：设计一个系统处理词语搭配问题，比如说 中国 和人民可以搭配，则中国人民 人民中国都有效。要求：*系统每秒的查询数量可能上千次；*词语的数量级为10W；*每个词至多可以与1W个词搭配当用户输入中国人民的时候，要求返回与这个搭配词组相关的信息。分析：性能要求：每秒查询量达到上千次，意思就是QPS要达到1000以上。搜索端使用多线程处理，现在服务器都是多核的，可以充分利用服务的资源。数据结...

百度研发笔试题解析： 一串首尾相连的珠子（m个），有N种颜色（N&lt;=10）

2017年02月05日 33 阅读

百度研发笔试题解析： 一串首尾相连的珠子（m个），有N种颜色（N<=10）2014-12-24题目：一串首尾相连的珠子（m个），有N种颜色（N<=10），设计一个算法，取出其中一段，要求包含所有N中颜色，并使长度最短。并分析时间复杂度与空间复杂度。分析：使用一个额外的数组存储颜色计数: colors[N]，并且定义一个颜色个数遍历int cn=0;使用数组a[m]表示首尾相连的珠子。遍历数组a，统计对应的颜色，如果等于颜色的个数等于N，记录下开...

Google面试题解析：从1到n的整数中1出现的次数

2017年02月05日 35 阅读

Google面试题解析：从1到n的整数中1出现的次数2014-12-24题目：输入一个正整数n，求从1到n这n个整数的十进制表示1出现的次数。例如：例如输入12， 那么从1到12的整数中出现1的整数为：1，10， 11和12，1一共出现5次。分析：这题可以简单计算每个数中包含的1的个数，再遍历1-n个整数。实现如下：#include<iostream>using namespace std;int count_num（int v）{int i ...

谷歌面试题解析：n支队伍比赛，分别编号为0，1，2。。。。n-1

2017年02月05日 36 阅读

谷歌面试题解析：n支队伍比赛，分别编号为0，1，2。。。。n-12014-12-24题目：n支队伍比赛，分别编号为0，1，2。。。。n-1，已知它们之间的实力对比关系，存储在一个二维数组w[n][n]中，w[i][j] 的值代表编号为i，j的队伍中更强的一支。所以w[i][j]=i 或者j，现在给出它们的出场顺序，并存储在数组order[n]中，比如order[n] = {4,3,5,8,1......}，那么第一轮比赛就是 4对3， 5对8。.........

百度面试题解析：有n个长为m+1的字符串

2017年02月05日 36 阅读

百度面试题解析：有n个长为m+1的字符串2014-12-24题目：有n个长为m+1的字符串， 如果某个字符串的最后m个字符与某个字符串的前m个字符匹配，则两个字符串可以联接，问这n个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误分析：题外话：这段时间以来，做了30多面试题，现在越来越有感觉，对题的思路越来越清晰，并且很多基本的数据结果和算法都比较熟。继续做下去，为了心中的梦想。。。这题可以联想到有向图的概念，字符串A的后m个字符与字符串B的前...

微软面试题解析：求一个矩阵中最大的二维矩阵（元素和最大）

2017年02月05日 38 阅读

微软面试题解析：求一个矩阵中最大的二维矩阵（元素和最大）2014-12-25题目：求一个矩阵中最大的二维矩阵（元素和最大）.如:1 2 0 3 42 3 4 5 11 1 5 3 0中最大的是:4 55 3要求:（1）写出算法;（2）分析时间复杂度;（3）用C写出关键代码分析：直接遍历二维数组，求出最大的二维数组就OK了实现如下：#include<iostream>using namespace std;int max_matrix（int （...

微软面试题解析：使用多线程实现一个队列

2017年02月05日 37 阅读

微软面试题解析：使用多线程实现一个队列2014-12-25题目：实现一个队列队列的应用场景为：一个生产者线程将int类型的数入列，一个消费者线程将int类型的数出列。分析：首先得设计一个队列，并且最好是循环队列，否则队列里面的空间很容易一下就使用完了。题目要求使用生产者线程和消费者线程，所以得设计成线程保护，否则取数据和推送数据很容易搞错。可以使用线程的互斥变量：pthread_mutex_t加pthread_mutex_lock 锁，解锁：pthread...

微软面试题解析：实现一个挺高级的字符匹配算法

2017年02月05日 38 阅读

微软面试题解析：实现一个挺高级的字符匹配算法2014-12-25题目：给一串很长字符串，要求找到符合要求的字符串，例如目的串：1231******3***2 ,12*****3这些都要找出来其实就是类似一些和谐系统。分析：自然匹配就是对待匹配的每个字符挨个匹配设你的待匹配字串长度位n,模式字符串长度位m.对于待匹配字符串中的任意一个字符最坏情况下要匹配m次，也就是说这个字符不在模式字符串中。所以最坏情况下总共是m*n此匹配，时间复杂度就是O（m*n）可以简...