LeetCode刷题笔记（十）哈希表
十. 哈希表
- 1.1 列表(list)
list是一种有序的集合，可以随时添加和删除其中的元素。
classmates = ['Michael', 'Bob', 'Tracy']
- 1.2 字典(dict)
dict在其他语言中也称为map，使用键-值（key-value）存储，具有极快的查找速度。
fruit={'apple':10, 'pears':5, 'bananas':20, 'orange':4}
- 1.3 集合(set)
set是一个无重复的数据集合。
s = set([1, 1, 2, 2, 3, 3])
# 等价于 s = {1, 2, 3}
-1.4 元组(tuple)
有序列表,tuple一旦初始化就不能修改。如果可能，能用tuple代替list就尽量用tuple,代码更安全。
classmates = ('Michael', 'Bob', 'Tracy')
1. 两数之和
题目：找到两数之和为target，返回下标
输入：nums = [2,7,11,15], target = 9
输出：[0,1] # 2+7=9
def twoSum(self, nums: List[int], target: int):
hashtable = dict()
for i, num in enumerate(nums):
if target - num in hashtable:
return [hashtable[target - num], i]
hashtable[nums[i]] = i # key: nums[i] -> value: i
return []
167. 两数之和II-输入有序数组
题目：找到两数之和为target，返回下标，输入有序数组
输入：nums = [2,7,11,15], target = 9
输出：[1,2] # 2+7=9
思考：用1的解法即可，不过如果能用上有序这个条件，可以进一步减少复杂度。
def twoSum(self, numbers: List[int], target: int) -> List[int]:
hashtable = dict()
for i, num in enumerate(numbers):
if target - num in hashtable:
return [hashtable[target - num], i+1]
hashtable[numbers[i]] = i+1
return []
20. 有效的括号
题目：有效的括号
输入：s = "()[]{}"
输出：true
def isValid(self, s: str) -> bool:
stack = []
p_map = {')':'(', ']':'[', '}':'{'}
for c in s:
if c not in p_map:
stack.append(c)
elif not stack or p_map[c] != stack.pop():
return False
return not stack
27. 移除元素
题目：给你一个数组 nums和一个值 val，你需要原地移除所有数值等于 val的元素，并返回移除后数组的新长度。
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
def removeElement(self, nums: List[int], val: int) -> int:
while(val in nums):
nums.pop(nums.index(val))
return len(nums)
169. 多数元素
题目：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
输入：[2,2,1,1,1,2,2]
输出：2
def majorityElement(self, nums: List[int]) -> int:
# create a set
d = dict()
for x in nums:
# 若不存在
if x in d.keys():
d[x] = d[x] + 1
else:
d[x] = 1
# find max value, then get key
max_value = -1
for x in d:
if d[x] > max_value:
max_value = d[x]
res = x
return res
217. 存在重复元素
题目：给定一个整数数组，判断是否存在重复元素。如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
输入：[1,2,3,1]
输出：true
def containsDuplicate(self, nums: List[int]) -> bool:
s = set() # 维护一个hash表即可
for i, x in enumerate(nums):
if x in s:
return True
else:
s.add(x)
return False
219. 存在重复元素 II
题目：给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
输入：nums = [1,2,3,1], k = 3
输出：true
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
d = dict()
for idx, i in enumerate(nums):
if not i in d:
d[i] = idx # 如果没有收录，收录它
elif abs(d[i] - idx)<=k:
return True # 如果存在重复且距离在k以内，返回
else: d[i] = idx # 如果距离不满足，更新标记
return False
242. 有效的字母异位词
题目：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
输入： s = "anagram", t = "nagaram"
输出：true
def isAnagram(self, s: str, t: str) -> bool:
dic1, dic2 = {}, {}
for item in s: # 需要dict1和dict2互相检查
dic1[item] = dic1.get(item, 0)+1
for item in t:
dic2[item] = dic2.get(item, 0)+1
return dic1 == dic2
290. 单词规律
题目：给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。
输入：pattern = "abba", str = "dog cat cat dog"
输出：true
思考：这是242的进化版本。
def wordPattern(self, pattern: str, s: str) -> bool:
s = s.split()
if len(s) != len(pattern):
return False
dp = dict()
ds = dict()
for i in range(0, len(pattern)):
if pattern[i] in dp:
if s[i] != dp[pattern[i]]:
return False
elif s[i] in ds:
if pattern[i] != ds[s[i]]:
return False
else:
dp[pattern[i]] = s[i]
ds[s[i]] = pattern[i]
return True
13. 罗马数字转整数
题目：罗马数字转整数
class Solution:
SYMBOL_VALUES = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000,
}
def romanToInt(self, s: str) -> int:
ans = 0
n = len(s)
for i, ch in enumerate(s):
value = Solution.SYMBOL_VALUES[ch] # 当前值
if i < n - 1 and value < Solution.SYMBOL_VALUES[s[i + 1]]:
ans -= value # 左减
else:
ans += value # 右加
return ans
168. Excel表列名称
题目：给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。
def convertToTitle(self, columnNumber: int) -> str:
ans = list()
while columnNumber > 0:
a0 = (columnNumber - 1) % 26 + 1
ans.append(chr(a0 - 1 + ord("A")))
columnNumber = (columnNumber - a0) // 26
return "".join(ans[::-1])
171. Excel 表列序号
题目：给你一个字符串 columnTitle ，表示 Excel 表格中的列名称。返回该列名称对应的列序号。
def titleToNumber(self, columnTitle: str) -> int:
number, multiple = 0, 1
for i in range(len(columnTitle) - 1, -1, -1):
k = ord(columnTitle[i]) - ord("A") + 1
number += k * multiple
multiple *= 26
return number
