Python 实例教学_ 05_字典

Python 1-18 字典
哈希表 Hash table
Python collections.Counter
Python collections.defaultdict

第二十二课

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