【LeetCode】升级打怪之路 Day 06：哈希表的应用

今���题目：

• 349. 两个数组的交集 | LeetCode
• 202. 快乐数 | LeetCode
• 1. 两数之和 | LeetCode
• 205. 同构字符串 | LeetCode
• 599. 两个列表的最小索引总和 | LeetCode
• 49. 字母异位词分组
• 249. 移位字符串分组
• 36. 有效的数独

  目录

  • • 应用 1 -- 哈希集合
    • • LeetCode 349. 两个数组的交集 【easy】
      • LeetCode 202. 快乐数 【小技巧】
      • 应用 2 -- 哈希映射 之 构造哈希表
      • • LeetCode 1. 两数之和 【classic】
        • LeetCode 205. 同构字符串 【easy】
        • LeetCode 599. 两个列表的最小索引总和 【easy】
        • 应用 3 -- 哈希映射 之 设计键
        • • LeetCode 49. 字母异位词分组 ⭐⭐⭐⭐⭐
          • LeetCode 249. 移位字符串分组 【还行】
          • LeetCode 36. 有效的数独 【还行】

            今天的题目也不难，主要学习了使用 HashSet 和 HashMap 来解决一些需要查重或记录 kv 映射关系的问题。其中应用 3 “设计 HasMap 的 key” 的思路很新颖有趣，要学会这种思想。

            应用 1 – 哈希集合

            哈希集合主要用来查重。

            （）

            LeetCode 349. 两个数组的交集 【easy】

            349. 两个数组的交集 | LeetCode

            经典的使用 HashSet 来解决问题的题目，较简单。

            LeetCode 202. 快乐数 【小技巧】

            202. 快乐数 | LeetCode

            这个题需要从题干的“无限循环”中推导出可能会有重复循环，进而想到使用 HashSet 来避免一直***循环的问题。

            我一开始就没想到这点，导致有点不知道怎么下手。

            应用 2 – 哈希映射 之 构造哈希表

            什么情况下会想到使用哈希表呢？当我们需要同时得到关联信息时，可以使用哈希表建立 key 与 value 的映射关系。我们需要通过分析题目的相关因素之间的关系，为 key 和 value 选择合适的数据类型。

            常见的 key 与 value 的关系有：

            • key -> 下标：比如两数之和题目，需要通过一个数字找出它在数组中的下标。
            • key -> 频次：用于统计使用频率最高的元素
            • key -> 数组：如果一个键对应的信息是一组元素，可使用数组或链表存储。
            • key -> 平面坐标：某些矩阵类习题可能会存储坐标；
            • key -> 其他：一般出现在模拟题中，根据实际需要设计哈希表。

              LeetCode 1. 两数之和 【classic】

              1. 两数之和 | LeetCode

              经典问题了，使用 key -> 下标 形式的哈希映射可以轻松解决。

              LeetCode 205. 同构字符串 【easy】

              205. 同构字符串 | LeetCode

              需要同时使用 HashMap 和 HashSet 用于记录映射关系和查重，题目较容易。

              LeetCode 599. 两个列表的最小索引总和 【easy】

              599. 两个列表的最小索引总和 | LeetCode

              这也是考察对利用 HashMap 来记录 key -> index 关系的一个题目，较为简单。

              应用 3 – 哈希映射 之 设计键

              前面在使用 HasMap 时，key 的设计相对简单，然而在某些题目中，需要我们设计出合适的 key，才能利用 HashMap 来解题。

              做下面这几个题目，关键是学会通过自己设计 HashMap 的 key 的形式来解决一些具体问题。

              LeetCode 49. 字母异位词分组 ⭐⭐⭐⭐⭐

              49. 字母异位词分组 | LeetCode

              这个题是经典的需要你去设计 key 的题目。

              字母异位词指字母相同，但排列不同的字符串，比如 “ate” 与 “eat” 是一组字母异位词。如果单纯地把每个字符串作为键，显然没有起到任何作用。经过分析发现，同一组字母异位词中，如果按照字典序排列，得到的字符串相同，且长度相等。这时我们自然想到以 按照字典序排列后的字符串 作为键，这样就能合理区分出字母异位词了。

              LeetCode 249. 移位字符串分组 【还行】

              249. 移位字符串分组 | LeetCode

              也是需要自己设计 key，这里主要一个坑：“可以认为字母表首尾相接，所以 ‘z’ 的后续为 ‘a’”

              LeetCode 36. 有效的数独 【还行】

              36. 有效的数独 | LeetCode

              题目很有意思，难度还行，能想到解决思路的话就不难。