算法刷题笔记04：Hash Table
04 Hash Table
242.有效的字母异位词
题目描述
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true示例 2:
输入: s = "rat", t = "car"
输出: false题目链接：https://leetcode-cn.com/problems/valid-anagram/
解法 1：排序后求解
将字符串转换为列表，排序后判断是否相等。时间复杂度为O(n\log{n})。（Python 语言排序的时间复杂度为O(n\log{n})）
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
s,t = list(s),list(t)
s.sort()
t.sort()
return s == t解法 2：使用哈希表
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 函数
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return collections.Counter(s) == collections.Counter(t) 解法 4：使用 collections.defaultdict 函数
国际站看到的，也是一种骚操作
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.字母异位词分组
题目描述
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]解法 1：哈希表
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，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
你可以按任意顺序返回答案。
示例 ：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。哈希表解法
这题可以采用哈希表来解，也是最优的解法。
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 []本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
