「LeetCode Top100」之哈希篇

1. 两数之和

题目链接:https://leetcode.cn/problems/two-sum/description/?envType=study-plan-v2&envId=top-100-liked
解题状态:通过
标签:数组哈希表

思路:

通过创建一个哈希表来保存数组中的元素,每当遍历一个元素时,若哈希表中不存在另一个与之相加为目标值的元素,就将元素插入到哈希表中。

代码:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> num;
        for(int i = 0; i < nums.size(); ++i) {
            auto iter = num.find(target - nums[i]);
            if(iter != num.end()) {
                return {iter->second, i};
            }
            num[nums[i]] = i;
        }
        return {};
    }
};

49. 字母异位词分组

题目链接:https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-100-liked
解题状态:个人思路无法实现,看题解通过!
标签:数组哈希表字符串排序

思路一:

使用unordered_map

由于异位词中的字母是相同的且个数也是相同的,首先将字符串中每个数组内部排序,获得唯一的排序,然后使用map来存储当前唯一排序对应的字符串,最后输出map中的字符串即可。

代码一:

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>> res;
        for(auto it = mp.begin(); it != mp.end(); ++it) {
            res.emplace_back(it->second);
        }
        return res;
    }
};

思路二:

使用哈希表,官方题解中将字符串中每个字母出现的次数使用字符串表示,作为哈希表的键。但是代码写的真是一言难尽,根本不想看。

代码二:

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // 自定义对 array<int, 26> 类型的哈希函数
        auto arrayHash = [fn = hash<int>{}] (const array<int, 26>& arr) -> size_t {
            return accumulate(arr.begin(), arr.end(), 0u, [&](size_t acc, int num) {
                return (acc << 1) ^ fn(num);
            });
        };

        unordered_map<array<int, 26>, vector<string>, decltype(arrayHash)> mp(0, arrayHash);
        for (string& str: strs) {
            array<int, 26> counts{};
            int length = str.length();
            for (int i = 0; i < length; ++i) {
                counts[str[i] - 'a'] ++;
            }
            mp[counts].emplace_back(str);
        }
        vector<vector<string>> ans;
        for (auto it = mp.begin(); it != mp.end(); ++it) {
            ans.emplace_back(it->second);
        }
        return ans;
    }
};

128. 最长连续序列

题目链接:https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked
解题状态:个人思路无法实现,看题解通过!
标签:并查集数组哈希表

思路:

使用哈希表来存储序列中的所有元素,然后遍历每个元素,先判断当前元素的前一个数值是否存在这个哈希表中,若不存在则表示当前元素是第一个连续元素,接着遍历是否包含下一个数值,最后返回最长的连续序列。

代码:

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> num_set;
        for(auto &num : nums) num_set.insert(num);
        int longStreak = 0;
        for(auto &num : num_set) {
            if(!num_set.count(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
                while(num_set.count(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }
                longStreak = max(longStreak, currentStreak);
            }
        }
        return longStreak;
    }
};

热门相关:天龙剑尊   我的女友不可能是怪物   99次出墙:老公,情难自禁   凤惊天之狂妃难求   伏天剑尊