【算法专题训练】21、哈希表应用

1、LCR 032. 有效的字母异位词

题目信息：

• https://leetcode.cn/problems/dKk3P7/description/

给定两个字符串 s 和 t ，编写一个函数来判断它们是不是一组变位词（字母异位词）。
注意：若 s 和 t 中每个字符出现的次数都相同且字符顺序不完全相同，则称 s 和 t 互为变位词（字母异位词）。

示例 1：
输入：s = "anagram", t = "nagaram"
输出：true

示例 2：
输入：s = "rat", t = "car"
输出：false

示例 3：
输入：s = "a", t = "a"
输出：false

提示：
1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

解题思路：

• 1、审题：输入两个字符串，判断这两个字符串是否是异位词，异位词是两个字符串中的各个字母个数都相同
• 2、解题：使用数组保存对应字母出现的次数
• 因为字符串限制了只包含小写字母，可以使用26个长度的int数组，来保存单个字母出现的次数
• 先判断两个字符串的长度，不一样直接返回false
• 字符串长度相同，则先遍历字符串1，保存每个字母出现的个数
• 接着遍历字符串2，遍历到的字母个数需要减1，如果出现了字母个数为0，则不满足异位词条件
• 判断如果两个字符串都一样，与不符合异位词情况，需要过滤
• 如果字符串内容没有限制，则使用map哈希表结构来保存字符出现的次数

代码实现：

bool isAnagram(string s, string t)
{
    if (s.length() != t.length())
    {
        return false;
    }
    if (s == t)
    {
        return false;
    }

    std::vector<int> nums(26, 0);

    for (int i = 0; i < s.length(); i++)
    {
        nums[s[i] - 'a']++;
    }

    for (int i = 0; i < t.length(); i++)
    {
        if (nums[t[i] - 'a'] == 0)
        {
            return false;
        }
        nums[t[i] - 'a']--;
    }

    return true;
}

2、LCR 033. 字母异位词分组

题目信息：

• https://leetcode.cn/problems/sfvd7V/description/

给定一个字符串数组 strs ，将 变位词 组合在一起。 可以按任意顺序返回结果列表。
注意：若两个字符串中每个字符出现的次数都相同，则称它们互为变位词。

示例 1：
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2：
输入: strs = [""]
输出: [[""]]

示例 3：
输入: strs = ["a"]
输出: [["a"]]

提示：
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

解题思路：

• 1、审题：输入一个字符串数组，要求找出数组中互为变位词的字符串，相同变位词的字符串放到一个数组中，最后合并到一起然后返回一个大的数组
• 2、解题：
• 遍历字符串数组，遍历到的字符串，要查找是否已经存在互为变位词的字符串，需要使用map集合存储，key值为变位词，value为对应变位词存储的集合
• 如何高效的寻找到变位词呢？将字符串进行排序，只要是变位词排序后最终结果都一样

代码实现：

vector<vector<string>> groupAnagrams(vector<string> &strs)
{
    std::vector<std::vector<std::string>> res;
    std::map<std::string, std::vector<std::string>> map;

    for (std::string str : strs)
    {
        std::string sortStr = str;
        // 先进行排序
        std::sort(sortStr.begin(), sortStr.end());

        if (map.find(sortStr) == map.end()) // 不包含，则添加
        {
            std::vector<std::string> items;
            items.push_back(str);
            map[sortStr] = items;
        }
        else
        {
            // 包含，则取出value进行添加
            map[sortStr].push_back(str);
        }
    }

    // 将map中所有value取出来放到res中
    for (const auto &pair : map)
    {
        res.push_back(pair.second);
    }

    return res;
}

3、LCR 034. 验证外星语词典

题目信息：

• https://leetcode.cn/problems/lwyVBB/description/

某种外星语也使用英文小写字母，但可能顺序 order 不同。字母表的顺序（order）是一些小写字母的排列。
给定一组用外星语书写的单词 words，以及其字母表的顺序 order，只有当给定的单词在这种外星语中按字典序排列时，返回 true；否则，返回 false。

示例 1：
输入：words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
输出：true
解释：在该语言的字母表中，'h' 位于 'l' 之前，所以单词序列是按字典序排列的。

示例 2：
输入：words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
输出：false
解释：在该语言的字母表中，'d' 位于 'l' 之后，那么 words[0] > words[1]，因此单词序列不是按字典序排列的。

示例 3：
输入：words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
输出：false
解释：当前三个字符 "app" 匹配时，第二个字符串相对短一些，然后根据词典编纂规则 "apple" > "app"，因为 'l' > '∅'，其中 '∅' 是空白字符，定义为比任何其他字符都小（更多信息）。

提示：
1 <= words.length <= 100
1 <= words[i].length <= 20
order.length == 26
在 words[i] 和 order 中的所有字符都是英文小写字母。

解题思路：

• 1、审题：输入一个字符串数组和对应的字母排序规则order，判断输入的字符串数组中的字符串是否是升序的，是的话返回true否则返回false
• 2、解题：
• 遍历字符串数组，只要判断前后两个字符串是否是符合排序规则，如果是的话继续遍历下一组字符串，如果不符合规则则直接返回false
• 所以核心点在于判断两个字符串是否符合给出的order排序规则，使用哈希表map保存order规则中字母顺序所在的下标位置，

代码实现：

bool judgeSort(std::string str1, std::string str2, std::map<char, int> orderMap)
{
    for (int i = 0; i < str1.length(); i++)
    {
        char ch1 = str1[i];
        // 长度判断
        if (str2.length() <= i)
        {
            return false;
        }
        else
        {
            char ch2 = str2[i];
            // 判断字母位置
            if (orderMap[ch1] < orderMap[ch2])
            {
                return true;
            }
            else if (orderMap[ch1] == orderMap[ch2]) // 相等继续遍历
            {
                continue;
            }
            else
            {
                return false;
            }
        }
    }
    // str1的长度为空，不存在
    return true;
}

bool isAlienSorted(vector<string> &words, string order)
{
    std::map<char, int> orderMap;
    for (int i = 0; i < order.length(); i++)
    {
        orderMap[order[i]] = i;
    }

    for (int i = 0; i < words.size() - 1; i++)
    {
        // 判断两个字符串，是否符合规则
        if (!judgeSort(words[i], words[i + 1], orderMap))
        {
            return false;
        }
    }

    return true;
}

4、LCR 035. 最小时间差

题目信息：

• https://leetcode.cn/problems/569nqc/description/

给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。

示例 1：
输入：timePoints = ["23:59","00:00"]
输出：1

示例 2：
输入：timePoints = ["00:00","23:59","00:00"]
输出：0

提示：
2 <= timePoints <= 2 * 104
timePoints[i] 格式为 "HH:MM"

解题思路：

解法1：暴力解法

• 让每个时间和其他的时间进行比较并求差值，获取最小值，时间复杂度高为O(n的平方)

解法2：先排序后求差值

• 对输入的vector时间进行排序，先判断小时，再判断分钟时间，按照升序进行排序
• 对遍历后的时间数组，进行两两求差值，得到差值最小的数据，
• 还要注意头尾两个时间的处理，也要求他们之间的差值
• 如果遇到两个时间相同，则直接返回0

代码实现：

// 使用find找到冒号：的位置pos，再使用substr方法进行时间的切割
static std::pair<int, int> parseTime(const std::string &time)
{
    int pos = time.find(":");
    if (pos == std::string::npos)
    {
        return {0, 0};
    }

    // 获取到小时
    std::string hourStr = time.substr(0, pos);
    std::string minStr = time.substr(pos + 1);
    return {std::stoi(hourStr), std::stoi(minStr)};
}

int findMinDifference1(vector<string> &timePoints)
{
    // 升序排序处理
    std::sort(timePoints.begin(), timePoints.end(),
              [](const std::string &a, const std::string &b)
              {
                  // 将a，b处理，获取到小时和分钟,根据：进行分割
                  auto aTime = parseTime(a);
                  std::cout << "a:" << aTime.first << ":" << aTime.second << std::endl;
                  auto bTime = parseTime(b);
                  std::cout << "b:" << bTime.first << ":" << bTime.second << std::endl;
                  if (aTime.first == bTime.first) // 小时相等，比较分钟
                  {
                      return aTime.second < bTime.second;
                  }
                  else
                  {
                      return aTime.first < bTime.first;
                  }
              });

    std::cout << "for ----- :" << std::endl;
    for (auto element : timePoints)
    {
        std::cout << element << ",";
    }
    std::cout << std::endl;

    int res = INT32_MAX;

    // 遍历排序后的数据，求取他们之间的差值
    for (int i = 1; i < timePoints.size(); i++)
    {
        auto preTime = parseTime(timePoints[i - 1]);
        auto currTime = parseTime(timePoints[i]);
        int diff = (currTime.first - preTime.first) * 60 + (currTime.second - preTime.second);

        if (diff == 0)
        { // 存在相同的两个时间
            return 0;
        }
        if (diff < res)
        {
            res = diff;
        }
        std::cout << "res1 :" << res << std::endl;
    }
    // 前后两个时间点的差值
    auto firstTime = parseTime(timePoints[0]);
    firstTime.first = firstTime.first + 24;
    auto lastTime = parseTime(timePoints[timePoints.size() - 1]);
    int diff = (firstTime.first - lastTime.first) * 60 + (firstTime.second - lastTime.second);
    if (diff < res)
    {
        res = diff;
    }
    std::cout << "res2 :" << res << std::endl;

    return res;
}

解法3：哈希表解法

• 将一天的时间全部按照分钟来表示，全部数值为 60*24 = 1440
• 使用一个布尔数组bool[24]，表示该时间是否有值，这样就转换成求1440个数组内，有bool=true值的差值
• 还是要注意头尾两个时间的差值计算

代码实现：

static int getMin(const std::string &time)
{
    int pos = time.find(":");
    if (pos == std::string::npos)
    {
        return 0;
    }

    // 获取到小时
    std::string hourStr = time.substr(0, pos);
    std::string minStr = time.substr(pos + 1);
    return std::stoi(hourStr) * 60 + std::stoi(minStr);
}

/**
 * 哈希表解法：将时间数组中的时间，转成bool数组
 */
int findMinDifference(vector<string> &timePoints)
{
    std::vector<bool> timeBools(1440, false);
    if (timePoints.size() > 1440)
    {
        return 0;
    }
    // 遍历，组合bool数组
    for (int i = 0; i < timePoints.size(); i++)
    {
        int min = getMin(timePoints[i]);
        std::cout << "min:" << min << std::endl;
        if (timeBools[min])
        {
            return 0;
        }
        timeBools[min] = true;
    }

    // 继续遍历timeBools 求时间差
    int res = INT32_MAX;
    // 临时变量，标记前一个值为true的数据，和最前，最后的位置
    int prev = -1;
    int first = timeBools.size();
    int last = 0;

    for (int i = 0; i < timeBools.size(); i++)
    {
        if (timeBools[i]) // 为true
        {
            if (prev != -1)
            {
                // 求差值
                int diff = i - prev;
                if (diff < res)
                {
                    res = diff;
                }
            }
            prev = i;
            first = std::min(first, i);
            last = std::max(last, i);
        }
    }

    std::cout << "res1:" << res << std::endl;
    // 求头尾两个时间的差值
    int diff = first + timeBools.size() - last;
    if (diff < res)
    {
        res = diff;
    }
    std::cout << "res2:" << res << std::endl;

    return res;
}

5、总结

• pair的使用
• find和substr方法，对字符串进行截取，如果有多个截取使用getline进行循环截取
• 将时间字符串转成数字，因为一天的时间是固定的，使用数组代替哈希表进行数据的保存