哈希表

哈希映射

面试题10.02变位词组

最长回文串

哈希映射

不使用任何内建的哈希表库设计一个哈希映射

具体地说，你的设计应该包含以下的功能

put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更新这个值。
get(key)：返回给定的键所对应的值，如果映射中不包含这个键，返回-1。
remove(key)：如果映射中存在这个键，删除这个数值对。

示例：

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);
hashMap.put(2, 2);
hashMap.get(1); // 返回 1
hashMap.get(3); // 返回 -1 (未找到)
hashMap.put(2, 1); // 更新已有的值
hashMap.get(2); // 返回 1
hashMap.remove(2); // 删除键为2的数据
hashMap.get(2); // 返回 -1 (未找到)

实现一个hash类

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
44
45
46
47
48
49
50
51
52
53
54
55
struct Node{
    int nkey;
    int nval;
    Node* next;
    Node(int key, int val): nkey(key), nval(val), next(nullptr){}
};
int len = 1000;
class MyHashMap {
public:
    vector <Node*> arr;
    /** Initialize your data structure here. */
    MyHashMap() {
        arr = vector<Node*> (len, new Node(-1,-1));
    }
    
    /** value will always be non-negative. */
    void put(int key, int value) {
        int temp = key % len;
        Node* h = arr[temp];
        Node* prev;
        while(h){
            if(h -> nkey == key){
                h -> nval = value;
                return;
            }
            prev = h;
            h = h -> next;
        }
        Node* node = new Node(key,value);
        prev -> next = node;
    }
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    int get(int key) {
        int temp = key % len;
        Node* h = arr[temp];
        while(h){
            if(h -> nkey == key)    return h -> nval;
            h = h -> next;
        }
        return -1;
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        int temp = key % len;
        Node* h = arr[temp];
        while(h){
            if(h -> nkey == key){
                h -> nval = -1;
            }
            h = h -> next;
        }
    }
};

C++链地址法

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <vector>

class Node
{
public:
    int key;
    int value;
    Node * next;
public:
    Node(int key_, int value_):key(key_),value(value_),next(nullptr){};
    ~Node();
};

const int len = 100;

class MyHashMap {
    
public:
    vector<Node*> arr;
public:
    /** Initialize your data structure here. */
    MyHashMap():arr(vector<Node*>(len, nullptr)){
        for (int i = 0; i < len; ++i)
            arr[i] = new Node(-1,0);
    }
    /** value will always be non-negative. */
    void put(int key, int value) {
        int index = key % len;
        Node *tmp = arr[index];
        while (tmp)
        {
             if (tmp->key == -1)
            {
                tmp->key = key;
                tmp->value = value;
                return ;
            }
            if (tmp->key == key)
            {
                tmp->value = value;
                return ;
            }
            if (tmp->next == nullptr)
            {
                tmp->next = new Node(key, value);
                return ;
            }
            tmp = tmp->next;
        }
        return ;
    }
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    int get(int key) {
        int index = key % len;
        Node *tmp = arr[index];
        while (tmp)
        {
            if (tmp->key == key)
                return tmp->value;
            tmp = tmp->next;
        }
        return -1;
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        int index = key % len;
        Node *tmp = arr[index];
        while (tmp)
        {
            if (tmp->key == key)
            {
                tmp->value = 0;
                tmp->key = -1;
                return ;
            }
            tmp = tmp->next;
        }
        return ;
    }
};
/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */
作者：lie-wen-hu-ke-de-xian-wei-jing
链接：https://leetcode-cn.com/problems/design-hashmap/solution/c-lian-di-zhi-fa-by-lie-wen-hu-ke-de-xian-wei-jing/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

变位词组

编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。

注意：本题相对原题稍作修改

示例:

输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
输出:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]
说明：

所有输入均为小写字母。
不考虑答案输出的顺序。

解题思路

变位词利用sort后和相同。哈希表添加次下标即可，之后便利哈希表根据下标添加变位词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string,vector<int> > map;
    vector<vector<string> > res;
    for(int i =0; i < strs.size() ; i++)
    {
        string str = strs[i];
        sort(str.begin(),str.end());
        map[str].push_back(i);
    }

    for(auto i : map )
    {
        auto index = i.second; //vector<int> index
        vector<string> tmp;
        for(auto it : index)
        {
            tmp.push_back(strs[it]);
        }
        res.push_back(tmp);
    }
    return res;
}

最长回文串

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。

注意:
假设字符串的长度不会超过 1010。

示例 1:

输入:
“abccccdd”

输出:
7

解释:
我们可以构造的最长的回文串是”dccaccd”, 它的长度是 7。

思路

  • 先用哈希统计出现的每一个字母个数

for(auto it : s) hash[it]++;

  • 统计字母个数为偶数的和，字母个数为奇数时，减一也能满足回文串要求

length += it.second % 2 ? it.second : it.second - 1

  • 此时res % 2 = 0，如果 res < size,则回文串中间还可以加一个

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char,int> hash;
        for(auto it : s)
            hash[it]++;
        int res = 0;
        for(auto it : hash)
            res += it.second % 2 == 0 ? it.second : it.second-1;
        //res % 2 = 0 如果res = size,则原字符串出现的字母均是偶数个
        return res = res < s.size() ? res + 1 : res;
    }
};

独一无二的出现次数

1207. 独一无二的出现次数

给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。

如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。

示例 1：

1
2
3
输入：arr = [1,2,2,1,1,3]
输出：true
解释：在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。

示例 2：
1
2
输入：arr = [1,2]
输出：false

示例 3：
1
2
输入：arr = [-3,0,1,-3,1,1,1,-3,10,0]
输出：true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        unordered_map<int,int> hash;
        for(int i =0; i < arr.size(); ++i)
        {
            hash[arr[i]]++;
        }
        unordered_set<int> times;
        for (const auto& x: hash) {
            times.insert(x.second);
        }
        return times.size() == hash.size();

    }
};

前 K 个高频元素（哈希排序）

347. 前 K 个高频元素

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:

1
2
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:
1
2
输入: nums = [1], k = 1
输出: [1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    static bool cmp(pair<int,int>v1,pair<int,int>v2)
    {
        return v1.second > v2.second;
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int,int> hash;
            for(int i = 0; i < nums.size(); i++)
            {
                hash[nums[i]]++;
            }
            vector<pair<int,int> > arr(hash.begin(),hash.end());
            sort(arr.begin(),arr.end(),cmp);
            vector<int> res;
            for(int i = 0; i < k; i++)
            {
                res.push_back(arr[i].first);
            }
            return res;
    }

};

二倍数对数组

954. 二倍数对数组

给定一个长度为偶数的整数数组 A，只有对 A 进行重组后可以满足 “对于每个 0 <= i < len(A) / 2，都有 A[2 i + 1] = 2 A[2 * i]” 时，返回 true；否则，返回 false。

示例 1：

1
2
输入：[3,1,3,6]
输出：false

示例 2：
1
2
输入：[2,1,2,6]
输出：false

示例 3：
1
2
3
输入：[4,-2,2,-4]
输出：true
解释：我们可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]

示例 4：
1
2
输入：[1,2,4,16,8,4]
输出：false

代码

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
class Solution {
public:
    bool canReorderDoubled(vector<int>& A) {
        map<int,int> hash;
        int match;

        for(int i : A)
            hash[i]++;
        for(auto it = hash.begin(); it != hash.end(); ++it)
        {
            if(it->second > 0)
            {
                if(it->first > 0)
                    match = it->first *2;
                else
                {
                    if(it->first % 2) return false;
                    match = it->first / 2;
                }
                hash[match] -= it->second;
                if(hash[match] < 0) return false;
            }
        }
        return true;
    }
};