Python 实例教程
- Python 实例教学_ 05_字典
- 第一课
- 1331. 数组序号转换
- 1748. 唯一元素的和
- 389. 找不同
- 方法一：计数
- 方法二：求和
- 方法三：位运算
- 第二课
- 2006. 差的绝对值为 K 的数对数目
- 1880. 检查某单词是否等于两单词之和
- 1897. 重新分配字符使所有字符串都相等
- 第三课
- 1365. 有多少小于当前数字的数字
- 1189. “气球” 的最大数量
- 1002. 查找共用字符
- 第四课
- 914. 卡牌分组
- [136. 只出现一次的数字](https://leetcode-cn.com/problems/single-number/)
- [846. 一手顺子](https://leetcode-cn.com/problems/hand-of-straights)
- 第五课
- [1773. 统计匹配检索规则的物品数量](https://leetcode.cn/problems/count-items-matching-a-rule/)
- [★1. 两数之和](https://leetcode-cn.com/problems/two-sum/)
- [645. 错误的集合](https://leetcode.cn/problems/set-mismatch/)
- 第六课
- [884. 两句话中的不常见单词](https://leetcode.cn/problems/uncommon-words-from-two-sentences/)
- [290. 单词规律](https://leetcode.cn/problems/word-pattern/)
- [1160. 拼写单词](https://leetcode.cn/problems/find-words-that-can-be-formed-by-characters/)
- 练习题
- [1748. 唯一元素的和](https://leetcode.cn/problems/sum-of-unique-elements/)
- [347. 前 K 个高频元素](https://leetcode.cn/problems/top-k-frequent-elements/)
- [1399. 统计最大组的数目](https://leetcode.cn/problems/count-largest-group/)
- [2363. 合并相似的物品](https://leetcode.cn/problems/merge-similar-items/)
- [1941. 检查是否所有字符出现次数相同](https://leetcode.cn/problems/check-if-all-characters-have-equal-number-of-occurrences/)
- [2399. 检查相同字母间的距离](https://leetcode.cn/problems/check-distances-between-same-letters/)
- [811. 子域名访问计数](https://leetcode.cn/problems/subdomain-visit-count/)
- [2053. 数组中第 K 个独一无二的字符串](https://leetcode.cn/problems/kth-distinct-string-in-an-array/)
- [2423. 删除字符使频率相同](https://leetcode.cn/problems/remove-letter-to-equalize-frequency/)
- [2404. 出现最频繁的偶数元素](https://leetcode.cn/problems/most-frequent-even-element/)
Python 实例教学_ 05_字典
Python 1-18 字典
哈希表 Hash table
Python collections.Counter
Python collections.defaultdict
第一课
1331. 数组序号转换
Leetcode
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. 唯一元素的和
Leetcode
class Solution:def sumOfUnique(self, nums: List[int]) -> int:res = {}for i in nums:res[i] = res.get(i, 0) + 1return sum(x for x in res if res[x] == 1)
389. 找不同
Leetcode
方法一：计数
class Solution:def findTheDifference(self, s: str, t: str) -> str:d = {}for c in s:d[c] = d.get(c, 0) + 1for c in t:d[c] = d.get(c, 0) - 1 if d[c] < 0:return cclass Solution:def findTheDifference(self, s: str, t: str) -> str:d = {}for c in s + t:d[c] = d.get(c, 0) + 1return [x for x in d if d[x]%2][-1]
方法二：求和
class Solution:def findTheDifference(self, s: str, t: str) -> str: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 码。
使用字符（注意不是字符串）异或运算 ^
- 一个数和 0 做 XOR 运算等于本身：a⊕0 = a
- 一个数和其本身做 XOR 运算等于 0：a⊕a = 0
- XOR 运算满足交换律和结合律：a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b
class Solution:def findTheDifference(self, s: str, t: str) -> str:res = 0for c in s + t:res ^= ord(c)return chr(res)# return chr(reduce(xor, map(ord, s + t)))
第二课
2006. 差的绝对值为 K 的数对数目
Leetcode
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 += 1return res'''res, d = 0, defaultdict(int)for i in nums:d[k+i] += 1for i in nums: res += d[i]return res
1880. 检查某单词是否等于两单词之和
Leetcode
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. 重新分配字符使所有字符串都相等
Leetcode
class Solution:def makeEqual(self, words: List[str]) -> bool:d = defaultdict(int)for word in words:for w in word:d[w] += 1for i in d:if d[i] % len(words): return False return True
第三课
1365. 有多少小于当前数字的数字
Leetcode
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] = ifor i in range(len(nums)-1, -1,-1):d[x[i]] = ireturn [d[i] for i in nums]
1189. “气球” 的最大数量
Leetcode
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] += 1return min(d[c]//2 if c in ['o', 'l'] else d[c] for c in d)
1002. 查找共用字符
Leetcode
class Solution:def commonChars(self, words: List[str]) -> List[str]:# 以第一个单词为基准统计每一个字符数量，然后其它单词比较。d = defaultdict(int)res = []for c in words[0]:d[c] += 1for 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. 卡牌分组
Leetcode
class Solution:def hasGroupsSizeX(self, deck: List[int]) -> bool:d = defaultdict(int)for i in deck:d[i] += 1x = min(d.values())#if x == 1:return Falsefor i in range(2, x+1):for j in d.values():if j % i:breakelse: return Truereturn 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]## 方法二：Countercount = 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 Falsehand.sort()cnt = Counter(hand)for h in hand:if cnt[h] == 0: continuefor num in range(h, h + groupSize):if cnt[num] == 0: return Falsecnt[num] -= 1 return True
第五课
1773. 统计匹配检索规则的物品数量
class Solution:def countMatches(self, items: List[List[str]], ruleKey: str, ruleValue: str) -> int:ans = 0for item in items:if ruleKey == 'type': if ruleValue == item[0]: ans += 1elif ruleKey == 'color': if ruleValue == item[1]: ans += 1elif ruleKey == 'name': if ruleValue == item[2]: ans += 1return 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 - yif 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 = iif c[i] == 2: x = ireturn [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] = welif d[c] != w: return Falsereturn 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: breakelse:x[c] -= 1else: 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] += 1return 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 = 0while i:# i, r = divmod(i, 10)i, r = i // 10, i % 10dp += rd[dp] += 1ans, mx = 1, 0for x in d.values():if x > mx:mx = xans = 1elif x == mx:ans += 1return 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] += wreturn sorted(d.items())
1941. 检查是否所有字符出现次数相同
class Solution:def areOccurrencesEqual(self, s: str) -> bool:# d = defaultdict(int)# for c in s:# d[c] += 1d = Counter(s)res = d[s[0]]for v in d.values():if v != res: return Falsereturn 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 Falsed[x] = ireturn 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] += xreturn [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 -= 1if k == 0:return sreturn ''
2423. 删除字符使频率相同
class Solution:def equalFrequency(self, word: str) -> bool: # 同 1224a, b = defaultdict(int), defaultdict(int) ans = 0n = len(word)for i, x in enumerate(word):a[x] += 1b[a[x]] += 1if a[x] * b[a[x]] == i + 1 and i != n-1: # 频率相等ans = i + 2if a[x] * b[a[x]] == i: # 特判频率为 1，2 的情况ans = i + 1return ans == nd = Counter(word)for c in d:d[c] -= 1s = {v for v in d.values() if v}if len(s) == 1: return Trued[c] += 1return False
2404. 出现最频繁的偶数元素
class Solution:def mostFrequentEven(self, nums: List[int]) -> int:d = defaultdict(int)for x in nums:if x % 2 == 0: d[x] += 1arr = sorted(d.items(), key=lambda item:(-item[1], item[0]))return arr[0][0] if arr else -1
