五月集训-07【哈希表】

• 前言
• 一、练习题目
• 二、思路及题解
• • 1. LC1512-好数对的数目
  • 2. LC2006-差的绝对值为 K 的数对数目
  • 3. LC1347-制造字母异位词的最小步骤数
  • 4. 面试题 10.02. 变位词组
• 总结

        欢迎大家积极在评论区留言一起讨论交流，知无不言，言无不尽，共同进步。本文是 哈希表 专题，更多其他专题内容详见《LeetCode每月集训系列》

方法一：暴力循环

（1）双重循环遍历即可求解。

代码如下：

class Solution {
public:
    int numIdenticalPairs(vector& nums) {
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = i + 1; j < nums.size(); ++j) {
                if (nums[i] == nums[j]) {
                    ++ans;
                }
            }
        }
        return ans;
    }
};

方法二：

（1）创建一个哈希表，遍历数组统计数组中数字重复出现的次数n；
（2）当遍历时必然是i < j的，则可以组成好数对的组合有1 + 2 + ··· + (n - 1)对。

代码如下：

class Solution {
public:
    int numIdenticalPairs(vector& nums) {
        unordered_map  cnt;
        int ans = 0;
        for (int num: nums) {
            ans += cnt[num]++;
        }
        return ans;
    }
};

方法一：哈希表

（1）对于每一个j而言，只需要再找到满足条件的i即可；
（2）满足 ∣nums[i] − nums[j]∣ = k 的i的个数，也就相当于满足 nums[i] = nums[j] + k 或 nums[i] = nums[j] − k 的 i 的个数。

代码如下：

class Solution {
public:
    int countKDifference(vector& nums, int k) {
        unordered_map cnt;
        int ans = 0;
        for (auto j : nums) {
            ans += cnt[j - k] + cnt[j + k];
            cnt[j]++;
        }
        return ans;
    }
};

方法二：

（1）创建一个哈希表统计数组中每个数字出现的次数；
（2）依次将相隔为k的两个值相乘，即可统计出符合要求的数对个数。

代码如下：

class Solution {
public:
    int countKDifference(vector& nums, int k) {
        int hash[101];
        memset(hash, 0, sizeof(hash));
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            ++hash[nums[i]];
        }
        for (int num = 1; num + k < 101; ++num) {
            ans += hash[num] * hash[num + k];  // 数组中的都数字大于0
        }
        return ans;
    }
};

方法一：

（1）创建两个哈希表，分别对字符串中字符的个数进行计数；
（2）遍历目标字符串s，若s-t大于0，其差值即为要替换字符的个数。

代码如下：

class Solution {
public:
    int minSteps(string s, string t) {
        unordered_map smap, tmap;
        int ans = 0;
        for (int i = 0; i < s.size(); ++i) {
            ++smap[s[i]];
            ++tmap[t[i]];
        }
        for (auto& [ch, _] : smap) {
            int n = smap[ch] - tmap[ch];
            if (n > 0) {
                ans += n; 
            }
        }
        return ans;
    }
};

方法一：哈希表+排序

（1）遍历字符串数组，并对每个字符串排序使得不同的变位词达成统一，从而定义一个字符串到字符串的哈希映射；
（2）然后遍历哈希表，将同一类型变位词放在一起输出即可。

代码如下：

class Solution {
public:
    vector> groupAnagrams(vector& strs) {
        unordered_map> hash;
        vector> ans;
        for (int i = 0; i < strs.size(); ++i) {
            string s = strs[i];
            sort(s.begin(), s.end());
            hash[s].push_back(strs[i]);
        }
        for (const auto& val : hash) {
            ans.push_back(val.second);
        }
        return ans;
    }
};

        题目难不要怕，只要每个月的每一天都坚持刷题学习，总有一天会熟练掌握的。欢迎加入【知识星球｜英雄算法联盟】与我们一同早起刷刷刷⛽️