今日题目:
今天的题目也不难,主要学习了使用 HashSet 和 HashMap 来解决一些需要查重或记录 kv 映射关系的问题。其中应用 3 “设计 HasMap 的 key” 的思路很新颖有趣,要学会这种思想。
哈希集合主要用来查重。
经典的使用 HashSet 来解决问题的题目,较简单。
这个题需要从题干的“无限循环”中推导出可能会有重复循环,进而想到使用 HashSet 来避免一直死循环的问题。
我一开始就没想到这点,导致有点不知道怎么下手。
什么情况下会想到使用哈希表呢?当我们需要同时得到关联信息时,可以使用哈希表建立 key 与 value 的映射关系。我们需要通过分析题目的相关因素之间的关系,为 key 和 value 选择合适的数据类型。
常见的 key 与 value 的关系有:
key -> 下标:比如两数之和题目,需要通过一个数字找出它在数组中的下标。key -> 频次:用于统计使用频率最高的元素key -> 数组:如果一个键对应的信息是一组元素,可使用数组或链表存储。key -> 平面坐标:某些矩阵类习题可能会存储坐标;key -> 其他:一般出现在模拟题中,根据实际需要设计哈希表。经典问题了,使用 key -> 下标 形式的哈希映射可以轻松解决。
需要同时使用 HashMap 和 HashSet 用于记录映射关系和查重,题目较容易。
这也是考察对利用 HashMap 来记录 key -> index 关系的一个题目,较为简单。
前面在使用 HasMap 时,key 的设计相对简单,然而在某些题目中,需要我们设计出合适的 key,才能利用 HashMap 来解题。
做下面这几个题目,关键是学会通过自己设计 HashMap 的 key 的形式来解决一些具体问题。
这个题是经典的需要你去设计 key 的题目。
字母异位词指字母相同,但排列不同的字符串,比如 “ate” 与 “eat” 是一组字母异位词。如果单纯地把每个字符串作为键,显然没有起到任何作用。经过分析发现,同一组字母异位词中,如果按照字典序排列,得到的字符串相同,且长度相等。这时我们自然想到以 按照字典序排列后的字符串 作为键,这样就能合理区分出字母异位词了。
也是需要自己设计 key,这里主要一个坑:“可以认为字母表首尾相接,所以 ‘z’ 的后续为 ‘a’”
题目很有意思,难度还行,能想到解决思路的话就不难。