Loading... # 04 Hash Table ## 242.有效的字母异位词 ### 题目描述 给定两个字符串 *s* 和 *t* ，编写一个函数来判断 *t* 是否是 *s* 的字母异位词。 **示例 1:** ```bash 输入: s = "anagram", t = "nagaram" 输出: true ``` **示例 2:** ```bash 输入: s = "rat", t = "car" 输出: false ``` 题目链接：https://leetcode-cn.com/problems/valid-anagram/ ### 解法 1：排序后求解 将字符串转换为列表，排序后判断是否相等。时间复杂度为$O(n\log{n})$。（Python 语言排序的时间复杂度为$O(n\log{n})$） ```python class Solution: def isAnagram(self, s: str, t: str) -> bool: s,t = list(s),list(t) s.sort() t.sort() return s == t ``` ### 解法 2：使用哈希表 ```python class Solution: def isAnagram(self, s: str, t: str) -> bool: if len(s) != len(t): return False # 构造hash table words = [chr(i) for i in range(97,123)] values = [0] * 26 word_s = dict(zip(words,values)) # 遍历两个字符串，最后判断字典是否每个值都为空 for i in range(len(s)): word_s[s[i]] += 1 word_s[t[i]] -= 1 for i in word_s: if word_s[i] != 0: return False return True ``` ### 解法 3：使用 collections.Counter 函数 ```python class Solution: def isAnagram(self, s: str, t: str) -> bool: return collections.Counter(s) == collections.Counter(t) ``` ### 解法 4：使用 collections.defaultdict 函数 国际站看到的，也是一种骚操作 ```python class Solution: def isAnagram(self, s: str, t: str) -> bool: tracker = collections.defaultdict(int) for x in s: tracker[x] += 1 for x in t: tracker[x] -= 1 return all(x==0 for x in tracker.values()) ``` ## 49.字母异位词分组 ### 题目描述 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。 **示例:** ```bash 输入: ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] ``` ### 解法 1：哈希表 ```python class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: dict = {} for item in strs: key = tuple(sorted(item)) dict[key] = dict.get(key, []) + [item] return list(dict.values()) ``` 注意 dict 的 get()方法，可以不用写非必要的 if else。 ## 1.两数之和 ### 题目描述 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。 你可以按任意顺序返回答案。 **示例 ：** ```bash 输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。 ``` ### 哈希表解法 这题可以采用哈希表来解，也是最优的解法。 ```python class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: hashtable = dict() # i是下标 # num是对应的值 for i, num in enumerate(nums): if target - num in hashtable: return [hashtable[target - num], i] hashtable[nums[i]] = i return [] ``` Last modification：January 30th, 2021 at 09:28 pm © 允许规范转载