代码收藏家 Python 05 Dict
Python 实例教学_ 05_字典
Python 1-18 字典
哈希表 Hash table
Python collections.Counter
Python collections.defaultdict
第一课
1331. 数组序号转换
class Solution:
def arrayRankTransform(self, arr: List[int]) -> List[int]:
d = {v:k+1 for k, v in enumerate(sorted(set(arr)))}
return [d[i] for i in arr]
1748. 唯一元素的和
class Solution:
def sumOfUnique(self, nums: List[int]) -> int:
d = {}
for i in nums:
d[i] = d.get(i, 0) + 1
return sum(x for x in d if d[x] == 1)
389. 找不同
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
### 方法一：计数
d = {}
for c in s:
d[c] = d.get(c, 0) + 1
for c in t:
d[c] = d.get(c, 0) - 1
if d[c] < 0: return c
### 方法一：计数
d = {}
for c in s + t:
d[c] = d.get(c, 0) + 1
return [x for x in d if d[x]%2][-1]
### 方法二：求和
return chr(sum(ord(c) for c in t) - sum(ord(c) for c in s))
# 利用 Counter (标准库的 collections)
# return list(Counter(t) - Counter(s))[0]
**知识点：**chr，ord，map，reduce (functools 库)，xor，ascii 码。
使用字符（注意不是字符串）异或运算 ^
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
### 方法三：位运算
res = 0
for c in s + t:
res ^= ord(c)
return chr(res)
# return chr(reduce(xor, map(ord, s + t)))
第二课
2006. 差的绝对值为 K 的数对数目
class Solution:
def countKDifference(self, nums: List[int], k: int) -> int:
'''
res, n = 0, len(nums)
for i in range(n):
for j in range(i+1, n):
if abs(nums[i]-nums[j]) == k:
res += 1
return res
'''
res, d = 0, defaultdict(int)
for i in nums:
d[k+i] += 1
for i in nums:
res += d[i]
return res
1880. 检查某单词是否等于两单词之和
class Solution:
def isSumEqual(self, firstWord: str, secondWord: str, targetWord: str) -> bool:
# d = {'a':'0','b':'1','c':'2','d':'3','e':'4','f':'5','g':'6','h':'7','i':'8','j':'9'}
# d[x], str(ord(x)-ord('a'))
f = ''.join([str(ord(x)-97) for x in firstWord])
s = ''.join([str(ord(x)-97) for x in secondWord])
t = ''.join([str(ord(x)-97) for x in targetWord])
return int(f) + int(s) == int(t)
1897. 重新分配字符使所有字符串都相等
class Solution:
def makeEqual(self, words: List[str]) -> bool:
d = defaultdict(int)
for word in words:
for w in word:
d[w] += 1
for i in d:
if d[i] % len(words): return False
return True
第三课
1365. 有多少小于当前数字的数字
class Solution:
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
x = sorted(nums)
d = defaultdict(int)
#for i, v in enumerate(x):
#if v not in d:
#d[v] = i
for i in range(len(nums)-1, -1,-1):
d[x[i]] = i
return [d[i] for i in nums]
1189. “气球” 的最大数量
class Solution:
def maxNumberOfBalloons(self, text: str) -> int:
d = {c:0 for c in 'balon'}
for c in text:
if c in 'balon':
d[c] += 1
return min(d[c]//2 if c in ['o', 'l'] else d[c] for c in d)
1002. 查找共用字符
class Solution:
def commonChars(self, words: List[str]) -> List[str]:
# 以第一个单词为基准统计每一个字符数量，然后其它单词比较。
d = defaultdict(int)
res = []
for c in words[0]:
d[c] += 1
for w in words[1:]:
for c in d:
d[c] = min(d[c], w.count(c))
for c in d:
if d[c]:
res.extend(c*d[c])
return res
第四课
914. 卡牌分组
class Solution:
def hasGroupsSizeX(self, deck: List[int]) -> bool:
d = defaultdict(int)
for i in deck:
d[i] += 1
x = min(d.values())
#if x == 1:return False
for i in range(2, x+1):
for j in d.values():
if j % i:
break
else:
return True
return False
136. 只出现一次的数字
class Solution:
def singleNumber(self, nums: List[int]) -> int:
## 方法一：dict 计数
d = {}
for i in nums: d[i] = d.get(i, 0) + 1
return [x for x in d if d[x] == 1][0]
## 方法二：Counter
count = Counter(nums)
for i in count:
if count[i] == 1: return i
## 方法三：
return sum(set(nums))*2-sum(nums)
846. 一手顺子
class Solution:
def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
if len(hand) % groupSize: return False
hand.sort()
cnt = Counter(hand)
for h in hand:
if cnt[h] == 0: continue
for num in range(h, h + groupSize):
if cnt[num] == 0: return False
cnt[num] -= 1
return True
第五课
1773. 统计匹配检索规则的物品数量
class Solution:
def countMatches(self, items: List[List[str]], ruleKey: str, ruleValue: str) -> int:
ans = 0
for item in items:
if ruleKey == 'type':
if ruleValue == item[0]: ans += 1
elif ruleKey == 'color':
if ruleValue == item[1]: ans += 1
elif ruleKey == 'name':
if ruleValue == item[2]: ans += 1
return ans
# ans = 0
# d = {"type":0, "color":1, "name":2} # 影射
# for item in items:
# if item[d[ruleKey]] == ruleValue:
# ans += 1
# return ans
# idx = {"type":0, "color":1, "name":2}[ruleKey]
# return sum(item[idx] == ruleValue for item in items)
★1. 两数之和
不能排序，因为找的是索引。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# # 方法一：暴力解法
# # 枚举数组中的每一个数 x，在 x 后面的元素中寻找 target - x。
# for i, x in enumerate(nums):
# for j, y in enumerate(nums[i+1:]): # 从 i 后面找
# if x + y == target:
# return [i, i+1 + j]
# return []
# ## 方法二：index
# for i, x in enumerate(nums):
# if target - x in nums[i+1:]:
# return [i, nums.index(target - x, i + 1)]
# # try:
# # j = nums.index(target - element, i + 1)
# # return i, j
# # except: pass
## 方法三：哈希表
# 创建一个字典，对于每一个 x，首先查询哈希表中是否存在 target - x，如果存在，则返回结果，否则将 x 插入到哈希表中。
# 注意：方法一是对于 x，从后面找 target - x；方法二是先把 target - x 和它的下标放到字典中，然后对后面的 x 在字典中找 target - x。
hashtable = dict()
for j, y in enumerate(nums):
x = target - y
if x in hashtable:
return [hashtable[x], j]
hashtable[y] = j
return []
645. 错误的集合
class Solution:
def findErrorNums(self, nums: List[int]) -> List[int]:
c = Counter(nums)
for i in range(1, len(nums) + 1):
if i not in c: y = i
if c[i] == 2: x = i
return [x, y]
第六课
884. 两句话中的不常见单词
class Solution:
def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
c = Counter(s1.split() + s2.split())
return [k for k, v in c.items() if v == 1]
290. 单词规律
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
words = s.split()
d = {}
if len(words) != len(pattern):return False
# for i, c in enumerate(pattern):
# w = words[i]
for c, w in zip(pattern, words):
if c not in d: d[c] = w
elif d[c] != w: return False
return len(d) == len(set(words))
1160. 拼写单词
class Solution:
def countCharacters(self, words: List[str], chars: str) -> int:
d = {}
res = 0
for c in chars:
d[c] = d.get(c, 0) + 1
for w in words:
x = d.copy()
for c in w:
if c not in d or x[c] == 0: break
else:x[c] -= 1
else: res += len(w)
return res
练习题
1748. 唯一元素的和
class Solution:
def sumOfUnique(self, nums: List[int]) -> int:
cnt = Counter(nums)
return sum(k for k, v in cnt.items() if v == 1)
347. 前 K 个高频元素
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
d = {}
for x in nums:
d[x] = d.get(x, 0) + 1
d = defaultdict(int)
for x in nums:
d[x] += 1
return sorted(d, key=lambda y:d[x], reverse=True)[:k]
cnt = Counter(nums)
return sorted(cnt, key=lambda x:-cnt[x])[:k]
return sorted(cnt := Counter(nums), key=lambda x:-cnt[x])[:k]
1399. 统计最大组的数目
class Solution:
def countLargestGroup(self, n: int) -> int:
d = defaultdict(int)
for i in range(1, n + 1):
# dp = sum(int(x) for x in str(i))
# dp = sum(map(int, str(i)))
dp = 0
while i:
# i, r = divmod(i, 10)
i, r = i // 10, i % 10
dp += r
d[dp] += 1
ans, mx = 1, 0
for x in d.values():
if x > mx:
mx = x
ans = 1
elif x == mx:
ans += 1
return ans
# mx = max(d.values())
# return sum(mx == v for v in d.values())
2363. 合并相似的物品
class Solution:
def mergeSimilarItems(self, items1: List[List[int]], items2: List[List[int]]) -> List[List[int]]:
d = defaultdict(int)
for v, w in items1 + items2:
d[v] += w
return sorted(d.items())
1941. 检查是否所有字符出现次数相同
class Solution:
def areOccurrencesEqual(self, s: str) -> bool:
# d = defaultdict(int)
# for c in s:
# d[c] += 1
d = Counter(s)
res = d[s[0]]
for v in d.values():
if v != res: return False
return True
return len(set(Counter(s).values())) == 1
2399. 检查相同字母间的距离
class Solution:
def checkDistances(self, s: str, distance: List[int]) -> bool:
d = {}
for i, c in enumerate(s):
x = ord(c) - ord('a')
if x in d and i - d[x] - 1 != distance[x]: return False
d[x] = i
return True
811. 子域名访问计数
class Solution:
def subdomainVisits(self, cpdomains: List[str]) -> List[str]:
cnt = Counter()
for cpdomain in cpdomains:
x, domain = cpdomain.split()
x = int(x)
cnt[domain] += x
# for _ in range(domain.count('.')):
# _, domain = domain.split('.', 1)
# cnt[domain] += x
# return [str(v) + ' ' + k for k, v in cnt.items()]
while '.' in domain:
domain = domain[domain.index('.') + 1:]
cnt[domain] += x
return [f"{v} {k}" for k, v in cnt.items()]
2053. 数组中第 K 个独一无二的字符串
class Solution:
def kthDistinct(self, arr: List[str], k: int) -> str:
d = Counter(arr)
for i, s in enumerate(arr):
if d[s] == 1:
k -= 1
if k == 0:
return s
return ''
2423. 删除字符使频率相同
class Solution:
def equalFrequency(self, word: str) -> bool:
# 同 1224
a, b = defaultdict(int), defaultdict(int)
ans = 0
n = len(word)
for i, x in enumerate(word):
a[x] += 1
b[a[x]] += 1
if a[x] * b[a[x]] == i + 1 and i != n-1: # 频率相等
ans = i + 2
if a[x] * b[a[x]] == i: # 特判频率为 1，2 的情况
ans = i + 1
return ans == n
d = Counter(word)
for c in d:
d[c] -= 1
s = {v for v in d.values() if v}
if len(s) == 1: return True
d[c] += 1
return False
2404. 出现最频繁的偶数元素
class Solution:
def mostFrequentEven(self, nums: List[int]) -> int:
d = defaultdict(int)
for x in nums:
if x % 2 == 0: d[x] += 1
arr = sorted(d.items(), key=lambda item:(-item[1], item[0]))
return arr[0][0] if arr else -1
作者：Yake1965
