代码随想录二刷哈希表day10

发布时间:2024年01月14日

哈希表理论基础

  • 哈希表

    • 哈希表中关键码就是数组的索引下标,然后通过下标直接访问数组中的元素

    • 一般哈希表都是用来快速判断一个元素是否出现在集合

  • 哈希函数

    • 通过hashCode把名字转化为数值,一般hashcode是通过特定编码方式,可以将其他数据格式转化为不同的数值

    • 如果hashcode得到的数值大于哈希表的大小,会再次对数值做一个取模的操作

  • 哈希碰撞

    • 学生的数量大于哈希表的大小,就算哈希函数计算的再均匀,也避免不了会有几位学生的名字同时映射到哈希表 同一个索引下标的位置

    • 拉链法

      • 发生冲突的元素都被存储再链表中

    • 线性探测法

      • 保证tableSize>dataSize,需要依靠哈希表中的空位解决碰撞问题

?

  • 常见的哈希结构

    • 数组

    • set(集合)

      • std::set

        • 底层实现红黑树,有序且数值不可以重复,不可以更改数值

      • std::multiset

        • 底层实现红黑树,有序且数值可以重复,不可以更改数值

      • std::unordered_set

        • 底层实现哈希表,无序且数值不可以重复,不可以更改数值

    • map(映射)

      • std::map

        • 底层实现红黑树,key有序且key不可重复不可修改

      • std::multimap

        • 底层实现红黑树,key有序且key可重复不可修改

      • std::unordered_map

        • 底层实现哈希表,key无序且key不可以重复不可修改

    • 当需要使用集合来解决哈希问题的时候,优先使用unordered_set,因为他的查询和增删效率是最优的,如果需要集合是有序的,那么就用set,如果要求不仅有序还要有重复数据的话,就用multiset

    • map是一个key-value结构的数据结构,map中对key有限制,对value没有限制,因为key的存储方式使用红黑树实现

242.有效的字母异位词

242. 有效的字母异位词 - 力扣(LeetCode)

给定两个字符串?s?和?t?,编写一个函数来判断?t?是否是?s?的字母异位词。

1.哈希表:数组做哈希,将字母元素转化为数值作为键存入哈希表,然后遍历两个字符串,如果哈希表中存在键的值不为0,那么就不是字母异位词

class Solution {
public:
    bool isAnagram(string s, string t) {
      int record[26] = {0};
      for(int i = 0; i < s.size(); i++) {
        record[s[i] - 'a']++;
      }
      for(int j = 0; j < t.size(); j++) {
        record[t[j] - 'a']--;
      }
      for(int i = 0; i < 26; i++) {
        if(record[i] != 0) {
          return false;
        }
      }
      return true;

    }
};

2.排序:t是s的异位词等价于两个字符串排序后相等 ps:可以直接用 s==t判断字符串是否相等,不需要像数组一样遍历所有元素

class Solution {
public:
    bool isAnagram(string s, string t) {
      if(s.size() != t.size()) {
        return false;
      }
      sort(s.begin(), s.end());
      sort(t.begin(), t.end());
      return s == t;
    }
};

383.赎金信

383. 赎金信 - 力扣(LeetCode)

给你两个字符串:ransomNote?和?magazine?,判断?ransomNote?能不能由?magazine?里面的字符构成。

如果可以,返回?true?;否则返回?false?。

magazine?中的每个字符只能在?ransomNote?中使用一次。

1.数组做哈希,状态可见就可以用数组做哈希,第二个数组能否构成第一个数组,遍历第二个数组存入哈希表,再遍历第一个数组,如果发现元素不够用了,则不能构成

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record[26] = {0};
        for(int i = 0; i < magazine.size(); i++) {
            record[magazine[i] - 'a']++;
        }
        for(int j = 0; j < ransomNote.size(); j++) {
            record[ransomNote[j] - 'a']--;
            if(record[ransomNote[j] - 'a'] < 0) {
                return false;
            }
        }
        return true;

    }
};

2.暴力解法:两层for循环不断寻找

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        for(int i = 0; i < magazine.size(); i++) {
            for(int j = 0; j < ransomNote.size(); j++) {
                // 在ransomNote中找和magazine相同的字符
                if(magazine[i] == ransomNote[j]) {
                    ransomNote.erase(ransomNote.begin() + j); // ransomNote删除这个字符
                    break;
                }
            }
        }
        // 如果ransomNote为空,则说明magazine的字符可以组成ransomNote
        if(ransomNote.size() == 0) {
            return true;
        }
        return false;
    }
};

?

349.两个数组的交集

349. 两个数组的交集 - 力扣(LeetCode)

给定两个数组?nums1?和?nums2?,返回?它们的交集?。输出结果中的每个元素一定是?唯一?的。我们可以?不考虑输出结果的顺序?。

逻辑理解上很好理解,本题的关键在于学会使用unordered_set这个set结构 PS:还有一点返回的结果是需要去重的,所以需要用哈希表来存储返回的结果,像我第一次做的时候用数组存储就完全没有考虑到去重这一操作

1.unordered_set的使用:一个结果set,一个存放元素set,如果第二个数组里存在第一个数组的元素,就把他存入结果set,去重结束后返回数组

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set;     // 存放结果,之所以用set是为了给结果集去重
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
        for(int num : nums2) {
            // 发现nums2的元素  在nums_set里又出现过
            if(nums_set.find(num) != nums_set.end()) {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

2.数组做哈希

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set;
        int hash[1005] = {0};
        for(int num : nums1) {
            hash[num]++;
        }
        for(int num : nums2) {
            if(hash[num]) {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

?

49.字母异位词分组

49. 字母异位词分组 - 力扣(LeetCode)

给你一个字符串数组,请你将?字母异位词?组合在一起。可以按任意顺序返回结果列表。

字母异位词?是由重新排列源单词的所有字母得到的一个新单词。

本题的核心理解:首先发现是一个二维数组,所以数据结构的选择是unordered_map,这是一个key-value结构的哈希表,细节在于把判断相同的条件作为key,相同的元素存入该key的value?

1.排序法:利用排序法,判断是否是字母异位词,然后将其存入vector

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for(string& str : strs) {
            string key = str;
            sort(key.begin(), key.end());
            mp[key].emplace_back(str);
        }
        vector<vector<string>> ans;
        for(auto it = mp.begin(); it != mp.end(); it++) {
            ans.emplace_back(it->second);
        }
        return ans;
    }
};

2.统计法:利用字符统计判断是否是字母异位词

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string, vector<string>> u_mapRes;
        for(auto& str : strs) {
            string count(26, '0');

            for(auto& c : str) {
                count[c - 'a']++;
            }
            u_mapRes[count].push_back(str);
        }
        for(auto& pair : u_mapRes) {
            res.push_back(pair.second);
        }
        return res;
    }
};

?加油!

文章来源:https://blog.csdn.net/sin___cosy/article/details/135578077
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。