「算法刷题」哈希表的简单和中等LeetCode题目实现

[TOC]

本文主要记录哈希表的相关LeetCode题目的实现代码，直接给出本文各个题目的答案，供有需求的读者学习或复制。

一、设计哈希结构的LeetCode题目

705. 设计哈希集合（简单难度）

class MyHashSet {
private:
    vector<list<int>> data;// 链表数组
    static const int tableSize = 769;//哈希表的容量,设为static是为了直接初始化
    static int hashFunction(int key) {
        return key % tableSize;
    }
public:
    MyHashSet(): data(tableSize) {}
    void add(int key) {
        int index = hashFunction(key);// 获取key对应的索引
        // 遍历data[h],查看是否已经存在key
        for (auto it = data[index].begin(); it != data[index].end(); it++) {
            if ((*it) == key) {
                return;
            }
        }
        // 如果该key不存在则加入
        data[index].push_back(key);
    }
    void remove(int key){
        int index=hashFunction(key);
        // 遍历data[h],查看是否已经存在key
        for(auto it = data[index].begin(); it != data[index].end(); it++){
            if((*it)==key){
                data[index].erase(it);
                return;
            }
        }
    }

    bool contains(int key) {
        int index = hashFunction(key);
        // 遍历data[h],查看是否已经存在key
        for (auto it = data[index].begin(); it != data[index].end(); it++) {
            if ((*it) == key) {
                return true;
            }
        }
        return false;
    }
};

706. 设计哈希映射（简单难度）

class MyHashMap {
private:
    vector<list<pair<int, int>>> data;// 链表数组,每个链表元素是pair对象
    static const int tableSize = 769;//哈希表的容量,设为static是为了直接初始化
    static int hashFunction(int key) {
        return key % tableSize;
    }
public:
    MyHashMap(): data(tableSize) {}
    
    void put(int key, int value) {
        int h = hashFunction(key);// 获取key对应的索引
        // 遍历data[h],查看是否已经存在key
        for (auto it = data[h].begin(); it != data[h].end(); it++) {
            if ((*it).first == key) {
                (*it).second = value;
                return;
            }
        }
        // 如果该key不存在则加入
        data[h].push_back(make_pair(key, value));
    }
    
    int get(int key) {
        int h = hashFunction(key);
        // 遍历data[h],查看是否已经存在key
        for (auto it = data[h].begin(); it != data[h].end(); it++) {
            if ((*it).first == key) {
                return (*it).second;
            }
        }
        return -1;
    }
    
    void remove(int key) {
        int h = hashFunction(key);
        for (auto it = data[h].begin(); it != data[h].end(); it++) {
            if ((*it).first == key) {
                data[h].erase(it);
                return;
            }
        }
    }
};

剑指 Offer II 031. 最近最少使用缓存（中等难度）

面试题 16.25. LRU 缓存（中等难度）

// 最近最少使用缓存器
class LRUCache {
private:
    int cap;// 容量
    list<pair<int,int>> l;// 链表（队列），存放元素<key,value>的数据
    unordered_map<int, list<pair<int, int>>::iterator> m;//哈希表，用来实现O(1)的查找效率，<key,链表元素指针>
public:
    LRUCache(int capacity):cap(capacity) {}
    // 通过key获取value
    int get(int key) {
        auto it = m.find(key);//在缓存数据中查找
        // 如果没有找到，返回-1
        if (it == m.end()) return -1;
        // 如果成功找到，将其升到链表顶部
        l.splice(l.begin(), l, it->second);
        return it->second->second;
    }
    
    void put(int key, int value) {
        auto it = m.find(key);//在缓存数据中查找
        // 如果成功找到，删除原有数据
        if (it != m.end()) l.erase(it->second);
        // 在链表顶部插入新元素
        l.push_front(make_pair(key, value));
        m[key] = l.begin();// 建立哈希映射
        // 如果插入元素后数量大于容量
        if (m.size() > cap) {
            int k = l.rbegin()->first;//找到倒数第一个元素<key,value>的key
            l.pop_back();// 链表删除最后一个元素
            m.erase(k);// 哈希表删除映射
        }
    }
};

二、哈希表的简单难度的LeetCode题目

1、找出一个序列中某个特殊的数

（1）找出数组中出现次数超过一半的数字

剑指 Offer 39. 数组中出现次数超过一半的数字（简单难度）

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        // 统计nums中每个数组元素出现的频率
        unordered_map<int,int> dict;// nums中每个数，出现频率
        for(int num:nums) dict[num]++;
        //建立哈希数组找其中出现次数大于n/2的数
        int n=nums.size();
        for(auto it=dict.begin();it!=dict.end();++it){
            if(it->second>n/2)
                return it->first;
        }
        return 0;
    }
}

（2）找出数组中只出现一次的数字

剑指 Offer II 004. 只出现一次的数字（中等难度）

剑指 Offer II 070. 排序数组中只出现一次的数字（中等难度）

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int,int> map;// 数字和出现次数
        // 遍历数组一遍统计频率
        for(int num:nums){
            map[num]++;
        }
        // 遍历哈希表
        for(auto it=map.begin();it!=map.end();++it){
            if(it->second==1)
                return it->first;
        }
        return -1;
    }
};

387. 字符串中的第一个唯一字符（简单难度）

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char,int> map;// 字符和出现次数
        // 遍历字符串一遍统计频率
        for(char c:s){
            map[c]++;
        }
        // 再次遍历遍历字符串
        for(int i=0;i<s.size();++i ){
            if(map[s[i]]==1)
                return i;
        }
        return -1;
    }
};

剑指 Offer 50. 第一个只出现一次的字符（简单难度）

class Solution {
public:
    char firstUniqChar(string s) {
        unordered_map<char,int> map;// 字符和出现次数
        // 遍历字符串一遍统计频率
        for(char c:s){
            map[c]++;
        }
        // 再次遍历遍历字符串
        for(char c:s){
            if(map[c]==1)
                return c;
        }
        return ' ';
    }
};

（3）找出数组中重复的数

217. 存在重复元素（简单难度）

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_map<int,int> dict;
        // 遍历数组
        for(int num:nums){
            if(dict.count(num)<=0) dict[num]++;
            else return true;
        }
        return false;
    }
};

剑指 Offer 03. 数组中重复的数字（简单难度）

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int,int> dict;
        for(int num : nums){
            // 如果已经存在就返回
            if(dict.count(num) > 0) return num;
            // 如果不存在就添加
            else dict[num]++;
        }
        return -1;
    }
};

219. 存在重复元素 II（简单难度）

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int,int> map;// 数字和所在索引
        // 遍历一遍数组元素
        for(int i=0;i<nums.size();++i){
            // 如果当前元素是重复元素
            if(map.count(nums[i])>0){
                //如果满足一次直接返回true
                if(abs(map[nums[i]]-i)<=k){
                    return true;
                }
                //否则更新索引（可能存在2个以上的重复元素）
                else{
                    map[nums[i]]=i;
                }
            }
            map[nums[i]]=i;
        }
        return false;
    }
};

2、找出一个序列中某个特殊的数

（1）给定1个数组，找出其中在[0,n]中消失的数、

剑指 Offer 53 - II. 0～n-1中缺失的数字（简单难度）

面试题 17.04. 消失的数字（简单难度）

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> res;
        // 统计nums中每个数组元素出现的频率
        unordered_map<int,int> dict;// nums中每个数，出现频率
        for(int num:nums) dict[num]++;

        // 遍历[1, n]，查看不存在的数
        for(int i=1;i<=nums.size();++i){
            if(dict.count(i)<=0)
                res.push_back(i);
        }
        return res;
    }
};

（2）给定2个字符串，找出不一样的字符

389. 找不同（简单难度）

class Solution {
public:
    char findTheDifference(string s, string t) {
        unordered_map<char,int> dict;
        for(char c:s) dict[c]++;
        for(char c:t){
            // 如果s中存在
            if(dict.count(c)>0){
                // 如果其频率为1，删除其key
                if(dict[c]==1) dict.erase(c);
                // 如果其频率大于1，频率-1
                else dict[c]--;
            }
            // 如果s中不存在，即找到结果
            else{
                return c;
            }
        }
        return ' ';
    }
};

（3）给定2个数组，找出其交集

349. 两个数组的交集（简单难度）

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        unordered_map<int,int> dict;
        // 将nums1的元素加入哈希表
        for(auto & num : nums1){
            dict[num]++;
        }
        // 遍历num2
        for(auto & num : nums2){
            // 如果哈希集中有该值，加入结果并删除
            if(dict.count(num)>0) {
                res.push_back(num);
                dict.erase(num);
            }
        }
        return res;//剩下的元素就是
    }
};

350. 两个数组的交集 II（简单难度）

使用map容器存储每个数的频率，在该容器中查找是否存在另一个数组的元素

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> result_set; // 存放结果
        map<int, int> m;
        //统计每个数的频率
        for (int i : nums1){
            m[i]++;
        }
        //遍历num2中的元素
        for (int num : nums2) {
            // 如果num频率大于0，说明其在nums1中出现过
            if (m[num]>0)
            {
                result_set.push_back(num);//将该num放入结果中
                m[num]--;//频率-1
            }
        }
        return result_set;
    }

（4）给定2个字符串，判断a的字符是否都被b包含

383. 赎金信（简单难度）

bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char,int> map;
        //统计magazine中的每个字母频率
        for(int i=0;i<magazine.size();i++){
            map[magazine[i]]+=1;
        }
    	//统计ransomNote中的每个字母频率
        for(int i=0;i<ransomNote.size();i++){
            map[ransomNote[i]]-=1;
        }
        //遍历哈希表，如果某个字母频率小于0，返回false
        for(unordered_map<char,int>::iterator it=map.begin();it!=map.end();it++){
            if(it->second<0)
                return false;
        }
        return true;
    }

（5）给定2个字符串，判断a和b是否是字母异位词

剑指 Offer II 032. 有效的变位词（简单难度）

bool isAnagram(string s, string t) {
        unordered_map<char,int> map;
        if(s.size()!=t.size())
            return false;
        //统计s和t中的每个字母频率
        for(int i=0;i<s.size();i++){
            map[s[i]]+=1;
            map[t[i]]-=1;
        }
        //遍历映射表
        for(unordered_map<char,int>::iterator it=map.begin();it!=map.end();it++){
            if(it->second!=0)
                return false;
        }
        return true;
    }

三、哈希表的中等难度的LeetCode题目

1、特殊规律

409. 最长回文串（简单难度）

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char,int> dict;//<字符，频率>
        // 统计字符串中每个字母的频率
        for(char c:s){
            dict[c]++;
        }
        // 查找频率
        int res=0;
        int flag = 0;//是否有中心字符，如果存在奇数个相同字符则可以有
        for(auto it=dict.begin();it!=dict.end();++it){
            // 如果字符频率为偶数个，均可以使用
            if(it->second%2==0){
                res+=it->second;
            }
            // 如果字符频率为奇数个，则丢弃1个，其余的均可使用
            else{
                res+=it->second-1;
                flag = 1;//此时，标记回文串可以有中心点
            }
        }
        return res+flag;//最终结果是偶数部分的最大长度+中心字符
    }
};

202. 快乐数（简单难度）

class Solution {
public:
    // 取数值各个位上的单数之和
    int getSum(int n) {
        int sum = 0;
        while (n) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> set;
        while(1){
            int sum=getSum(n);//求和后的新数
            if(sum==1){
                return true;
            }
            //如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false
            if (set.find(sum) != set.end()) {
                return false;
            } else {
                set.insert(sum);
            }
            n = sum;
        }
    }
};

2、双哈希映射

此题是「290. 单词规律」的简化版，需要我们判断 ss 和 tt 每个位置上的字符是否都一一对应，即 ss 的任意一个字符被 tt 中唯一的字符对应，同时 tt 的任意一个字符被 ss 中唯一的字符对应。这也被称为「双射」的关系。因此，我们维护两张哈希表，第一张哈希表 s2t 以 s 中字符为键，映射至 t 的字符为值，第二张哈希表 t2s 以 tt中字符为键，映射至 s的字符为值。从左至右遍历两个字符串的字符，不断更新两张哈希表，如果出现冲突（即当前下标index 对应的字符 s[index] 已经存在映射且不为t[index] 或当前下标 index 对应的字符 t[index] 已经存在映射且不为s[index]时说明两个字符串无法构成同构，返回false。如果遍历结束没有出现冲突，则表明两个字符串是同构的，返回 true 即可。

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char, char> smap;//保存s->t的映射
        unordered_map<char, char> tmap;//保存t->s的映射
        for(int i=0;i<s.size();i++)
        {
            // 如果两个哈希表的映射都不存在，添加数据
            if(smap.count(s[i])<=0&&tmap.count(t[i])<=0)
            {
                smap[s[i]]=t[i];//s->t
                tmap[t[i]]=s[i];//t->s
            }
            // 如果当前字母已经存在并且当前字母和已有映射不同，则返回false
            if(smap.count(s[i])>0&&smap[s[i]]!=t[i]) return false;
            if(tmap.count(t[i])>0&&tmap[t[i]]!=s[i]) return false;
            
        }
        return true;
    }
};

290. 单词规律（简单难度）

class Solution {
public:
    // 分割字符串
    vector<string> splitWord(string str){
        vector<string> words;
        string word;
        // 遍历整个字符串中的字符
        for (char c:str)
            // 如果当前字母为空格并且
            if (c == ' '&&word.size()>0) {
                words.push_back(word);
                word = "";
            } 
            else{
                word += str[i];
            }
        // 如果word有字符，加入结果
        if (word.size()) words.push_back(word);
        return words;
    }
    bool wordPattern(string pattern, string s) {
        vector<string> words=splitWord(s);
        if(pattern.size()!=words.size())return false;
        // 双哈希法(每个字母和每个单词一一唯一对应)
        unordered_map<string,char> str2ch;// 单词到字母的映射
        unordered_map<char,string> ch2str;// 字母到单词的映射
        // 同时遍历两个序列
        for(int i=0;i<pattern.size();++i){
            char ch=pattern[i]; // 获取当前字母
            string str=words[i];// 获取当前单词
            // 如果当前字母已有映射，检查已有映射和当前单词是否一致
            if(ch2str.count(ch)>0&&ch2str[ch]!=str){
                return false;
            }
            // 如果当前单词已有映射，检查已有映射和当前字母是否一致
            if(str2ch.count(str)>0&&str2ch[str]!=ch){
                return false;
            }
            // 当前字母和当前单词没有映射，建立映射
            ch2str[ch]=str;
            str2ch[str]=ch;
        }
        return true;
    }
};

3、字符串数组找交集

1002. 查找共用字符（简单难度）

多个字符串中对应的字母频次最小值就是常用字符：

//获取一个字符串的各个字母频次
    void getfeq(int * feq,const string &s){
        for(int i=0;i<s.size();i++){
            feq[s[i]-'a']++;
        }
    }
    vector<string> commonChars(vector<string>& words) {
        vector<string> res;
        int minfeq[26] = {0};//最小频次
        getfeq(minfeq,words[0]);//默认第一个字符串为最小
        //循环查找最小频次
        for(int i=1;i<words.size();i++){
            int feq[26] = {0};
            getfeq(feq,words[i]);
            for(int j=0;j<26;j++){
                minfeq[j] = min(minfeq[j],feq[j]);
            }
        }
        // 将统计得到最小频次，转成字符
        for(int i=0;i<26;i++){
            if(minfeq[i]!=0){
                for(int j = 0; j < minfeq[i]; j++){
                    string s(1, i + 'a'); // char -> string
                    res.push_back(s);
                }
            }
        }
        return res;
    }

599. 两个列表的最小索引总和（简单难度）

class Solution {
public:
    // 找两个字符串数组中的交集，并且交集字符串所在的索引和最小
    vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
        unordered_map<string, int> dict;//餐厅名字-索引号
        vector<string> res;// 结果数组
        int ans = 2000;//索引和的最大值
        // 遍历数组1,建立哈希映射
        for(int i = 0; i < list1.size(); i++){
            dict[list1[i]]=i;
        }
        // 遍历数组2
        for(int i = 0; i < list2.size(); i++){
            // 如果哈希表中找到了该字符串，说明是和数组1的交集
            auto it =dict.find(list2[i]);
            if(it!=dict.end()){
                int newAns = it->second+i;//新的索引和=该字符串所对应的数组1的索引+i
                // 如果新的索引和更小
                if(newAns  < ans){
                    ans = newAns;//记录该索引和
                    res.clear();// 清空结果字符串
                    res.push_back(list2[i]);
                }
                // 如果新的索引和相等
                else if(newAns== ans){
                    res.push_back(list2[i]);
                }
            }
        }
        return res;
    }
};

49. 字母异位词分组（中等难度）

剑指 Offer II 033. 变位词组（中等难度）

vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string,vector<string>> M;//<排序后的字符串，乱序的字符串数组>
    	// 遍历字符串数组，将每个字符串排序
        for(int i=0;i<strs.size();i++){
            //先对排序
            string key=strs[i];
            sort(key.begin(),key.end());
            //哈希表添加元素
            M[key].push_back(strs[i]);
        }
        //遍历哈希表，将其value加入结果数组
        for(unordered_map<string,vector<string>>::iterator iter=M.begin();iter!=M.end();iter++){
            res.push_back(iter->second);
        }
        return res;
    }