机试打卡 -06 异位词分组（哈希表）-Toy模板网

这篇具有很好参考价值的文章主要介绍了机试打卡 -06 异位词分组（哈希表）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

机试打卡 -06 异位词分组（哈希表）

最容易想到的是利用 ord( ) 函数，按照字母计数的特征归类，代码如下：

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:

        ans_list=[]
        
        # 哈希表 {word_count:ans_list中的索引}
        word_count_dict=dict()

        # 遍历str
        for word in strs:

            # word 对应的字母计数元组
            word_count=self.Count_letters(word)
            
            # 若计数元组之前出现，则直接将word根据value值添加到ans_list中
            if word_count in word_count_dict:
                ans_list[word_count_dict[word_count]].append(word)

            # 若未出现，则将添加至哈希表，value值为len(ans_list)
            # 再将 [word] 添加至 ans_list 的末尾
            else:
                word_count_dict[word_count]=len(ans_list)
                ans_list.append([word])
        
        return ans_list


    def Count_letters(self,word):
        lst=[0]*26

        for letter in word:
            lst[ord(letter)-97]+=1
        
        # 此处必须转化成tuple元组
        #因为字典的key必须是可哈希的（即保持不变的--tuple）

        return tuple(lst)

①ord('a')==97。

②字典的key必须是可哈希的！

一个对象在其生命周期内，如果保持不变，就是hashable(可哈希的)。

hashable ≈ imutable 可哈希 ≈ 不可变

在Python中：

list、set和dictionary 都是可改变的，比如可以通过list.append()，set.remove()，dict[‘key‘] = value对其进行修改，所以它们都是不可哈希的；

而tuple和string是不可变的，只可以做复制或者切片等操作，所以它们就是可哈希的。

所以此处需要将 list转换为tuple 作为字典的key。

官方题解方法一：排序

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:

        # 构建哈希表 {排序后的st：[]}    collections模块
        mp = collections.defaultdict(list)

        for st in strs:
            
            # sorted排序完成之后返回列表
            # "".join(list) 重新组合成字符串
            key = "".join(sorted(st))

            # 添加至对应value中
            mp[key].append(st)
        
        # 利用 dict.values() 方法
        #再用list()转换数据类型，直接返回结果列表

        return list(mp.values())

①sorted() 函数将返回一个排序后的列表，若需要重新组合成字符串，需使用 "".join()函数。

②dict.values() 将字典中的所有 value 全部取出，但需要使再用 list() 或 tuple() 转换数据类型；

dict.keys() 同理。

官方题解方法二：计数

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list)

        for st in strs:
            counts = [0] * 26
            for ch in st:
                counts[ord(ch) - ord("a")] += 1

            # 需要将 list 转换成 tuple 才能进行哈希
            mp[tuple(counts)].append(st)
        
        return list(mp.values())

文章来源地址https://www.toymoban.com/news/detail-458495.html

到了这里，关于机试打卡 -06 异位词分组（哈希表）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！