自学内容网 自学内容网

【LeetCode】哈希表精选5题

目录

1. 两数之和(简单)

2. 验证外星语词典(简单)

3. 存在重复元素(简单)

4. 存在重复元素 II(简单)

5. 字母异位词分组(中等)


1. 两数之和(简单)

创建一个哈希表,对于每一个nums[i],我们首先查询哈希表中是否存在target - nums[i],然后将nums[i]插入到哈希表中,即可保证不会让nums[i]和自己匹配。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        unordered_map<int, int> hash; // key——nums[i] value——i
        for (int i = 0; i < n; i++)
        {
            int x = target - nums[i];
            if (hash.count(x))
                return { hash[x],i };
            hash[nums[i]] = i;
        }
        return { -1,-1 };
    }
};

2. 验证外星语词典(简单)​​​​​​​

用数组模拟哈希表,hash[0]表示字母'a'在字母表中的顺序,hash[1]表示字母'b'在字母表中的顺序……

为了判断两个单词是否是按照字母表的顺序排序的,可以扫描两个单词中的字母找出第一个不相同的字母。哪个单词的第一个不相同的字母在字母表中的位置靠前,排序的时候它就排在前面。如果没有找到不相同的字母,那么短的单词在排序的时候应该排在前面。

class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        // 初始化哈希表
        for (int i = 0; i < order.size(); i++)
        {
            hash[order[i] - 'a'] = i;
        }
        // 判断相邻的两个单词是否按照字母表的顺序排序
        for (int i = 0; i < words.size() - 1; i++)
        {
            if (!isSorted(words[i], words[i + 1]))
                return false;
        }
        return true;
    }

private:
    bool isSorted(string& word1, string& word2)
    {
        int i = 0;
        while (i < word1.size() && i < word2.size())
        {
            char ch1 = word1[i];
            char ch2 = word2[i];
            if (ch1 == ch2)
            {
                i++;
            }
            else
            {
                if (hash[ch1 - 'a'] < hash[ch2 - 'a'])
                    return true;
                if (hash[ch1 - 'a'] > hash[ch2 - 'a'])
                    return false;
            }
        }
        return i == word1.size();
    }

    int hash[26]; // 记录字母在字母表中的顺序
};

3. 存在重复元素(简单)

出现至少两次就是数组中存在着重复的元素,因此我们可以无需统计元素出现的数目。仅需在遍历数组的过程中,检查当前元素是否在之前已经出现过即可。

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> hash;
        for (auto& e : nums)
        {
            if (hash.count(e))
                return true;
            else
            {
                hash.insert(e);
            }
        }
        return false;
    }
};

4. 存在重复元素 II(简单)

创建一个哈希表,对于每一个nums[i],我们首先查询哈希表中是否存在nums[i],并且i - hash[nums[i]] <= k,然后将nums[i]插入到哈希表中,即可保证不会让nums[i]和自己匹配。

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int, int> hash; // key——nums[i] value——i
        for (int i = 0; i < n; i++)
        {
            int x = nums[i];
            if (hash.count(x) && i - hash[x] <= k)
                return true;
            hash[x] = i;
        }
        return false;
    }
};

5. 字母异位词分组(中等)

把一组字母异位词映射到同一个单词,由于互为字母异位词的单词的字母出现的次数分别相同,因此如果把单词中的字母排序就会得到相同的字符串。

创建一个哈希表,key为把单词字母排序得到的字符串,value为一组字母异位词。

例如,eat tea ate -> aet,创建哈希表,key——"aet",value——{ "eat","tea","ate" }。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hash;
        for (string& str: strs)
        {
            string s = str;
            sort(s.begin(), s.end());
            hash[s].push_back(str);
        }
        vector<vector<string>> ans;
        for(auto& [x, y] : hash)
        {
            ans.push_back(y);
        }
        return ans;
    }
};

原文地址:https://blog.csdn.net/Qiuhan_909/article/details/135330115

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!