Hash数据结构：
hash表可以提供快速的插入操作和查找操作。需要首先申请较大的空间，将元素根据特定规则求key,散列到不同的空间位置。
哈希表散列方法：
- 直接定址法
- 数字分析法
- 平方取中法
- 折叠法
- 除留余数法
- 随机数法
哈希表处理冲突方法：
- 开放定址法：当冲突时， 重新计算地址 H = (H(key) + di) MOD m
- di = 1, 2, 3…时，线性探测再散列, 能保证只要表未满，就能找到空位，但是会造成“二次聚集”： 如下一个地址为 i,i + 1,i+2的元素都会争夺后一个空位。
- di = 1^2, -1^2, 2^2, -2^2…k^2, -k^2.. 二次探测再散列。
- di = 伪随机数序列， 称作伪随机探测再散列
- 链地址法
leetcode 相关题目
1. Intersection of Two Arrays(349)
Given two arrays, write a function to compute their intersection.
Example: Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].
解法： 1 排序用two pointer，注意去重； 2 hash表索引，注意去重
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
vector<int> result;
unordered_set<int> s(nums1.begin(), nums1.end());
for(int i = 0; i < nums2.size(); i++){
if(s.count(nums2[i])){
result.push_back(nums2[i]);
s.erase(nums2[i]);
}
}
return result;
}
2. Two Sum(1)
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example: Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
unordered_map<int, int> map;
for(int i = 0; i < nums.size(); i++){
unordered_map<int, int>::iterator x = map.find(target - nums[i]);
if(x != map.end()){
result.push_back(x->second);
result.push_back(i);
break;
}
map[nums[i]] = i;
}
return result;
}
3. Longest Substring Without Repeating Characters(3)
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given “abcabcbb”, the answer is “abc”, which the length is 3.
Given “bbbbb”, the answer is “b”, with the length of 1.
Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.
int lengthOfLongestSubstring(string s) {
if(s.size()== 0){
return 0;
}
int max = 0;
unordered_map<char, int> map;
int pre = 0;
for(int i = 0; i < s.size(); i++){
unordered_map<char, int>::iterator it;
it = map.find(s[i]);
if(it != map.end()){
//注意substring开始界限的更新 比如abba ， it->second + 1
//能比 pre 小
pre = pre > it->second + 1 ? pre : it->second + 1;
it->second = i;
}else{
pair<char, int> ss (s[i], i);
map.insert(ss);
}
max = max >= (i - pre + 1)? max: (i - pre + 1);
}
return max;
}
4 Max Points on a Line(149)
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:
int maxPoints(vector<Point>& points) {
map<pair<int, int>, int> slopes;
int maxp = 0, n = points.size();
for (int i = 0; i < n; i++) {
slopes.clear();
int duplicate = 1;
int localMax = 0;
for (int j = i + 1; j < n; j++) {
if (points[j].x == points[i].x && points[j].y == points[i].y) {
duplicate++;
continue;
}
int dx = points[j].x - points[i].x;
int dy = points[j].y - points[i].y;
int dvs = gcd(dx, dy);
pair<int, int> ppp(dx / dvs, dy / dvs);
slopes[ppp]++;
localMax = max(localMax, slopes[ppp]);
}
maxp = max(maxp, localMax + duplicate);
}
return maxp;
}
private:
int gcd(int num1, int num2) {
while (num2) {
int temp = num2;
num2 = num1 % num2;
num1 = temp;
}
return num1;
}
};
5 微软笔试题 Queen Attack https://hihocoder.com/contest/mstest2017april/problem/1
描述
There are N queens in an infinite chessboard. We say two queens may attack each other if they are in the same vertical line, horizontal line or diagonal line even if there are other queens sitting between them.
Now given the positions of the queens, find out how many pairs may attack each other?
输入 The first line contains an integer N.
Then N lines follow. Each line contains 2 integers Ri and Ci indicating there is a queen in the Ri-th row and Ci-th column.
No two queens share the same position.
For 80% of the data, 1 <= N <= 1000
For 100% of the data, 1 <= N <= 100000, 0 <= Ri, Ci <= 1000000000
输出 One integer, the number of pairs may attack each other.
思路： 两两遍历，O(n^2), 但是超时。需要更高效的办法。 看题目，没有重复的点，可以计算出，横坐标每个相同的数目， 比如横坐标都是1 的点有n个，那么符合要求的对有（n * (n - 1)）/ 2, 纵坐标也是类似。难点在于对角线相同的怎么求。根据 |x1 - x2| = |y1 - y2|, 可以得到对角线的两种情况， x1 - y1 = x2 - y2 和 x1 + y1 = x2 + y2, 所以我们把坐标变换一下， ni = xi - yi, mi = xi + yi, 再求ni, mi中相同值的个数， 再计算就好了。 当然求相同的个数，可以用hash. 也可以排序之后再遍历一遍，也比O(n^2) 快。 <p>排序的解法
#include <iostream>
#include <algorithm>
#define pairs(n) (n*(n-1))/2
using namespace std;
int calculateNums(int* arr, int n) {
int num = 0;
int e = arr[0];
int eCount = 1;
for(int i = 1; i < n; i++) {
if(arr[i] == e) {
eCount++;
}else {
num += pairs(eCount);
eCount = 1;
e = arr[i];
}
}
if(eCount > 1) {
num += pairs(eCount);
}
return num;
}
int main(void) {
int n;
cin >> n;
int pos[n][2];
int col[n];
int row[n];
int num = 0;
for (int i = 0; i < n; i++) {
cin >> pos[i][0] >> pos[i][1];
row[i] = pos[i][0];
col[i] = pos[i][1];
}
sort(row, row + n, less<int>());
num += calculateNums(row, n);
sort(col, col + n, less<int>());
num += calculateNums(col, n);
for(int i = 0; i < n; i++) {
row[i] = pos[i][0] - pos[i][1];
col[i] = pos[i][0] + pos[i][1];
}
sort(row, row + n, less<int>());
num += calculateNums(row, n);
sort(col, col + n, less<int>());
num += calculateNums(col, n);
cout << num << endl;
return 0;
}
6 Group Anagrams(49)
Given an array of strings, group anagrams together.
For example, given: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”], Return: [ [“ate”, “eat”,”tea”], [“nat”,”tan”], [“bat”] ] Note: All inputs will be in lower-case.
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string> > map;
for(int i = 0; i < strs.size(); i++){
string key = strs[i];
sort(key.begin(), key.end());
unordered_map<string, vector<string> >:: iterator it = map.find(key);
if(it != map.end()){
it->second.push_back(strs[i]);
}else{
vector<string> newV;
newV.push_back(strs[i]);
map[key] = newV;
}
}
vector<vector<string> > result;
for(unordered_map<string, vector<string> >::iterator it = map.begin(); it != map.end(); it++){
vector<string> anagram(it->second.begin(), it->second.end());
result.push_back(anagram);
}
return result;
}
};
