Python 字典与集合专项练习:6 道编程题从入门到精通

输入：nums = [2, 7, 11, 15], target = 9输出：[0, 1]解释：nums[0] + nums[1] = 2 + 7 = 9

def two_sum(nums, target):    """    两数之和 —— 哈希表法 O(n)    思路：遍历时记录已见数字，对于每个num检查(target-num)是否已存在    """    seen = {}  # 数字 -> 索引    for i, num in enumerate(nums):        complement = target - num        if complement in seen:            return [seen[complement], i]        seen[num] = i    return []  # 无解# 测试if __name__ == "__main__":    print(two_sum([2, 7, 11, 15], 9))   # [0, 1]    print(two_sum([3, 2, 4], 6))        # [1, 2]    print(two_sum([3, 3], 6))           # [0, 1]    # 边界测试    print(two_sum([], 10))              # []    print(two_sum([1], 2))              # []

输入：["eat", "tea", "tan", "ate", "nat", "bat"]输出：[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

from collections import defaultdictdef group_anagrams_sort(strs):    """方法一：排序作为键"""    groups = defaultdict(list)    for s in strs:        key = ''.join(sorted(s))  # 排序后作为键        groups[key].append(s)    return list(groups.values())def group_anagrams_count(strs):    """方法二：字母计数作为键（避免排序）"""    groups = defaultdict(list)    for s in strs:        # 统计26个字母出现次数        count = [0] * 26        for ch in s:            count[ord(ch) - ord('a')] += 1        key = tuple(count)  # 列表不可哈希，转元组        groups[key].append(s)    return list(groups.values())# 测试if __name__ == "__main__":    strs = ["eat", "tea", "tan", "ate", "nat", "bat"]    print(group_anagrams_sort(strs))    # [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]    print(group_anagrams_count(strs))    # [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]    # 边界测试    print(group_anagrams_sort([""]))    # [['']]    print(group_anagrams_sort(["a"]))   # [['a']]

输入：nums = [1, 1, 1, 2, 2, 3], k = 2输出：[1, 2]解释：1出现3次，2出现2次，是前两个高频元素

from collections import Counterimport heapqdef top_k_frequent_sort(nums, k):    """方法一：排序 —— O(n log n)"""    counter = Counter(nums)    # 按频率降序排序    sorted_items = sorted(counter.items(), key=lambda x: x[1], reverse=True)    return [item[0] for item in sorted_items[:k]]def top_k_frequent_heap(nums, k):    """方法二：堆 —— O(n + k log n)"""    counter = Counter(nums)    # heapq.nlargest 内部使用堆    return [item[0] for item in heapq.nlargest(k, counter.items(), key=lambda x: x[1])]def top_k_frequent_bucket(nums, k):    """方法三：桶排序 —— O(n)"""    counter = Counter(nums)    # 桶：索引是频率，值是该频率的元素列表    max_freq = max(counter.values())    buckets = [[] for _ in range(max_freq + 1)]    for num, freq in counter.items():        buckets[freq].append(num)    # 从高频到低频收集    result = []    for i in range(max_freq, 0, -1):        result.extend(buckets[i])        if len(result) >= k:            return result[:k]    return result# 测试if __name__ == "__main__":    nums = [1, 1, 1, 2, 2, 3]    k = 2    print(top_k_frequent_sort(nums, k))   # [1, 2]    print(top_k_frequent_heap(nums, k))   # [1, 2]    print(top_k_frequent_bucket(nums, k)) # [1, 2]    # 性能对比    import timeit    import random    big_nums = [random.randint(1, 1000) for _ in range(100000)]    t1 = timeit.timeit(lambda: top_k_frequent_sort(big_nums, 10), number=10)    t2 = timeit.timeit(lambda: top_k_frequent_heap(big_nums, 10), number=10)    t3 = timeit.timeit(lambda: top_k_frequent_bucket(big_nums, 10), number=10)    print(f"\n排序法: {t1:.4f}s")    print(f"堆方法: {t2:.4f}s")    print(f"桶排序: {t3:.4f}s")

输入：nums = [100, 4, 200, 1, 3, 2]输出：4解释：最长连续序列是 [1, 2, 3, 4]，长度为 4

def longest_consecutive(nums):    """最长连续序列 —— 集合 + O(n) 遍历"""    if not nums:        return 0    num_set = set(nums)    max_length = 0    for num in num_set:        # 只有当 num-1 不存在时，才作为序列起点        if num - 1 not in num_set:            current_num = num            current_length = 1            # 向后查找连续数字            while current_num + 1 in num_set:                current_num += 1                current_length += 1            max_length = max(max_length, current_length)    return max_length# 测试if __name__ == "__main__":    print(longest_consecutive([100, 4, 200, 1, 3, 2]))  # 4    print(longest_consecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]))  # 9    print(longest_consecutive([]))  # 0    print(longest_consecutive([1]))  # 1    # 性能测试    import timeit    import random    big_nums = random.sample(range(1000000), 100000)    t = timeit.timeit(lambda: longest_consecutive(big_nums), number=10)    print(f"\n10万数据耗时: {t:.4f}s")

cache = LRUCache(2)cache.put(1, 1)cache.put(2, 2)print(cache.get(1))    # 返回 1cache.put(3, 3)        # 淘汰 key=2print(cache.get(2))    # 返回 -1（未找到）cache.put(4, 4)        # 淘汰 key=1print(cache.get(1))    # 返回 -1print(cache.get(3))    # 返回 3print(cache.get(4))    # 返回 4

from collections import OrderedDictclass LRUCache:    """LRU 缓存 —— 基于 OrderedDict 实现"""    def __init__(self, capacity: int):        self.capacity = capacity        self.cache = OrderedDict()    def get(self, key: int) -> int:        if key not in self.cache:            return -1        # 移动到末尾（表示最近使用）        self.cache.move_to_end(key)        return self.cache[key]    def put(self, key: int, value: int) -> None:        if key in self.cache:            # 更新并移动到末尾            self.cache.move_to_end(key)        else:            # 检查容量            if len(self.cache) >= self.capacity:                # 弹出最久未使用的（头部）                self.cache.popitem(last=False)        self.cache[key] = value# 手动实现版本（双向链表 + 字典）class DLinkedNode:    """双向链表节点"""    def __init__(self, key=0, value=0):        self.key = key        self.value = value        self.prev = None        self.next = Noneclass LRUCacheManual:    """LRU 缓存 —— 手动实现双向链表"""    def __init__(self, capacity: int):        self.capacity = capacity        self.cache = {}  # key -> Node        # 虚拟头尾节点（简化边界处理）        self.head = DLinkedNode()        self.tail = DLinkedNode()        self.head.next = self.tail        self.tail.prev = self.head    def _add_node(self, node):        """添加到头部（最近使用）"""        node.prev = self.head        node.next = self.head.next        self.head.next.prev = node        self.head.next = node    def _remove_node(self, node):        """移除节点"""        node.prev.next = node.next        node.next.prev = node.prev    def _move_to_head(self, node):        """移动到头部"""        self._remove_node(node)        self._add_node(node)    def _pop_tail(self):        """弹出尾部节点（最久未使用）"""        node = self.tail.prev        self._remove_node(node)        return node    def get(self, key: int) -> int:        if key not in self.cache:            return -1        node = self.cache[key]        self._move_to_head(node)        return node.value    def put(self, key: int, value: int) -> None:        if key in self.cache:            node = self.cache[key]            node.value = value            self._move_to_head(node)        else:            if len(self.cache) >= self.capacity:                tail = self._pop_tail()                del self.cache[tail.key]            node = DLinkedNode(key, value)            self.cache[key] = node            self._add_node(node)# 测试if __name__ == "__main__":    # OrderedDict 版本    cache = LRUCache(2)    cache.put(1, 1)    cache.put(2, 2)    print(cache.get(1))  # 1    cache.put(3, 3)    print(cache.get(2))  # -1    cache.put(4, 4)    print(cache.get(1))  # -1    print(cache.get(3))  # 3    print(cache.get(4))  # 4    print("\n--- 手动实现版本 ---")    cache2 = LRUCacheManual(2)    cache2.put(1, 1)    cache2.put(2, 2)    print(cache2.get(1))  # 1    cache2.put(3, 3)    print(cache2.get(2))  # -1

hashMap = MyHashMap()hashMap.put(1, 10)hashMap.put(2, 20)print(hashMap.get(1))   # 10print(hashMap.get(3))   # -1hashMap.put(2, 30)print(hashMap.get(2))   # 30hashMap.remove(2)print(hashMap.get(2))   # -1

class MyHashMap:    """简易哈希表 —— 链地址法实现"""    def __init__(self, capacity=1000, load_factor=0.75):        self.capacity = capacity        self.load_factor = load_factor        self.size = 0        # 每个桶是一个列表，存储 (key, value) 元组        self.buckets = [[] for _ in range(capacity)]    def _hash(self, key):        """哈希函数"""        return key % self.capacity    def _resize(self):        """扩容并重新哈希"""        old_buckets = self.buckets        self.capacity *= 2        self.buckets = [[] for _ in range(self.capacity)]        self.size = 0        # 重新插入所有元素        for bucket in old_buckets:            for key, value in bucket:                self.put(key, value)    def put(self, key, value):        """插入或更新"""        if self.size >= self.capacity * self.load_factor:            self._resize()        idx = self._hash(key)        bucket = self.buckets[idx]        # 查找是否已存在        for i, (k, v) in enumerate(bucket):            if k == key:                bucket[i] = (key, value)  # 更新                return        # 不存在则追加        bucket.append((key, value))        self.size += 1    def get(self, key):        """获取值"""        idx = self._hash(key)        bucket = self.buckets[idx]        for k, v in bucket:            if k == key:                return v        return -1    def remove(self, key):        """删除键值对"""        idx = self._hash(key)        bucket = self.buckets[idx]        for i, (k, v) in enumerate(bucket):            if k == key:                del bucket[i]                self.size -= 1                return    def __repr__(self):        items = []        for bucket in self.buckets:            for k, v in bucket:                items.append(f"{k}: {v}")        return "{" + ", ".join(items) + "}"# 测试if __name__ == "__main__":    hashMap = MyHashMap()    hashMap.put(1, 10)    hashMap.put(2, 20)    print(hashMap.get(1))   # 10    print(hashMap.get(3))   # -1    hashMap.put(2, 30)    print(hashMap.get(2))   # 30    hashMap.remove(2)    print(hashMap.get(2))   # -1    # 冲突测试    hashMap.put(1, 100)    hashMap.put(1001, 200)  # 与 key=1 哈希冲突（假设 capacity=1000）    print(hashMap.get(1))    # 100    print(hashMap.get(1001)) # 200    # 扩容测试    print(f"\n扩容前 capacity: {hashMap.capacity}")    for i in range(1000):        hashMap.put(i, i * 10)    print(f"扩容后 capacity: {hashMap.capacity}")    print(hashMap.get(500))  # 5000