rambo

Hash解法笔试题

2015年6月25日 笔试面试 0 Comments

1.  题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。（360）

解题思路：由于题目与字符出现的次数相关，我们是不是可以统计每个字符在该字符串中出现的次数？要达到这个目的，我们需要一个数据容器来存放每个字符的出现次数。在这个数据容器中可以根据字符来查找它出现的次数，也就是说这个容器的作用是把一个字符映射成一个数字。在常用的数据容器中，哈希表正是这个用途。

哈希表是一种比较复杂的数据结构。由于比较复杂，STL中没有实现哈希表，因此需要我们自己实现一个。但由于本题的特殊性，我们只需要一个非常简单的哈希表就能满足要求。由于字符（char）是一个长度为8的数据类型，因此总共有可能256 种可能。于是我们创建一个长度为256的数组，每个字母根据其ASCII码值作为数组的下标对应数组的对应项，而数组中存储的是每个字符对应的次数。这样我们就创建了一个大小为256，以字符ASCII码为键值的哈希表。

我们第一遍扫描这个数组时，每碰到一个字符，在哈希表中找到对应的项并把出现的次数增加一次。这样在进行第二次扫描时，就能直接从哈希表中得到每个字符出现的次数了。

代码如下：

 

 

 

2.  Given an array of integers, find two numbers such that they add up to a specific target number,the function twoSum should return indices of the two numbers such that they add up to the target,where index1 must be less than index2. Please note that your returned answers (both index1 and index2 are not zero-based). You may assume that each input would have exactly one solution.

stl相关：map与unordered_map

1
2
3
typedef std::map<std::string, int> string_map;
typedef __gnu_cxx::hash_map<std::string, int, zl::hash_string> string_hash_map;
typedef std::tr1::unordered_map<std::string, int> string_unordered_map;

stl::map是按照operator<比较判断元素是否相同，以及比较元素的大小，然后选择合适的位置插入到树中。所以，如果对map进行遍历（中序遍历）的话，输出的结果是有序的。顺序就是按照operator< 定义的大小排序。

  1. std::tr1::unordered_map 与 std::ext/hash_map ：任何情况下，如果要在这两个容器之间选择的话，我们毫不犹豫应该选择 unordered_map。因为它的性能在上述4中操作中均优于 hash_map，甚至可以说远远优于 hash_map。
  2. std::tr1::unordered_map 与 std::map ：map的性能总体来说是最差的。但是，当我们需要一个有序的关联容器的时候，我们必须选择std::map，因为 unordered_map 内部元素不是有序的。除此之外都应该选择 unordered_map 。
  3. unordered_map 的遍历性能几乎是常数级别的，

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
32
33
#include <vector>
#include <map>
#include <unordered_map>
#include <iostream>
using namespace std;
 
void twoSum(vector<int>&num,int target,vector<int>result){
unordered_map<int,int>mapping;
//用一个哈希表，存储每个数对应的下标
for(int i=0;i<num.size();i++){
mapping[num[i]]=i;
}
for(int i=0;i<num.size();i++){
const int gap=target-num[i];
if(mapping.find(gap)!=mapping.end()){
result.push_back(i+1);
result.push_back(mapping[gap]+1);
break;
}
}
}
 
int _tmain(int argc, _TCHAR* argv[]){
vector<int> num;
vector<int>result;
num.push_back(2);
num.push_back(7);
num.push_back(11);
num.push_back(15);
 
twoSum(num,9,result);
return 0;
}

QQ截图20150831220657
QQ截图20150831220807

算法复杂度：O(N)

扩展题目：求三个数字等于0。用左右夹逼方法。

STL中左闭右开，一对迭代器（泛型指针）所标示的区间，是左闭右开的，即[first,last)，实际范围应该是从[first,last-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
32
33
34
35
36
37
38
39
40
41
42
43
#include <vector>
#include <map>
#include <unordered_map>
#include<math.h>
#include <algorithm>
#include <iostream>
using namespace std;
 
void ThreeSum(vector<int>&num, vector<vector<int>>&result){
if (num.size() < 3)return;
sort(num.begin(), num.end());//O(nlgn)
 
const int target = 0;
auto last = num.end();//左闭右开
//先排序，然后左右夹逼
for (auto a = num.begin(); a < prev(last, 2); ++a){
auto b = next(a);
auto c = prev(last);//最后一个数字所在
while (b < c){
if (*a + *b + *c < target){
++b;
}
else if (*a + *b + *c > target){
--c;
}
else{
result.push_back({ *a, *b, *c });
++b;
--c;
}
}
}
sort(result.begin(), result.end());
 
}
 
int _tmain(int argc, _TCHAR* argv[]){
vector<int> num = { -1, 0, 1, 2, -1, -4 };//VS2013才能这样初始化
vector<vector<int>>result;
ThreeSum(num, result);
return 0;
}

针对上面题目的扩展：在一个给定的数组中，判断是否有i,j,k满足a[i]+a[j]=a[k],有没有比较好的算法？

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

一个题是在海量数据中查找出现频率最高的数据，即top10。 一个城市对应多个IP地址段，给你一个IP，怎么判断它属于哪个城市。