贪心算法全解析（三）：Huffman 编码、进阶问题与全系列总结

         [*]
        /   \
      [*]   [c: 1]
     /   \
  [a: 0] [b: 10]

编码：a = 00, b = 01, c = 1
总长度 = f_a·2 + f_b·2 + f_c·1

import heapq
from typing import List, Optional

class HuffmanNode:
    def __init__(self, freq: int, char: Optional[str] = None):
        self.freq = freq
        self.char = char
        self.left: Optional['HuffmanNode'] = None
        self.right: Optional['HuffmanNode'] = None

    def __lt__(self, other: 'HuffmanNode') -> bool:
        return self.freq < other.freq

def build_huffman_tree(freqs: dict) -> Optional['HuffmanNode']:
    """根据字符频率字典构造 Huffman 树"""
    heap: List[HuffmanNode] = []
    for char, freq in freqs.items():
        heapq.heappush(heap, HuffmanNode(freq, char))

    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        parent = HuffmanNode(left.freq + right.freq)
        parent.left = left
        parent.right = right
        heapq.heappush(heap, parent)

    return heap[0] if heap else None

def generate_codes(root: Optional['HuffmanNode'], prefix: str = '',
                   codebook: Optional[dict] = None) -> dict:
    """DFS 遍历 Huffman 树，生成字符→编码的映射"""
    if codebook is None:
        codebook = {}
    if root is None:
        return codebook
    if root.char is not None:           # 叶子节点
        codebook[root.char] = prefix
    else:
        generate_codes(root.left, prefix + '0', codebook)
        generate_codes(root.right, prefix + '1', codebook)
    return codebook

# 示例
freqs = {'a': 45, 'b': 13, 'c': 12, 'd': 16, 'e': 9, 'f': 5}
root = build_huffman_tree(freqs)
codes = generate_codes(root)
# {'a': '0', 'c': '100', 'b': '101', 'f': '1100', 'e': '1101', 'd': '111'}

import heapq
from typing import List, Dict, Tuple

def dijkstra(graph: Dict[int, List[Tuple[int, int]]], start: int) -> Dict[int, int]:
    """
    graph: 邻接表 {node: [(neighbor, weight), ...]}
    返回: {node: shortest_distance_from_start}
    """
    dist: Dict[int, int] = {start: 0}
    heap: List[Tuple[int, int]] = [(0, start)]   # (distance, node)

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, float('inf')):
            continue   # 惰性删除：过时的条目

        for v, w in graph.get(u, []):
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(heap, (nd, v))

    return dist

tasks = ["A","A","A","B","B","B"], n = 2

时间轴：A _ _ A _ _ A
       ↑     ↑     ↑
将 B 填入空位：A B _ A B _ A B

最少时间 = max(6, (3-1)*(2+1) + 2) = max(6, 8) = 6
(实际任务总数 6 < 8，但任务就这么多，所以答案是 6)

from typing import List
from collections import Counter

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        freq = list(Counter(tasks).values())
        max_freq = max(freq)
        max_count = freq.count(max_freq)   # 有多少个任务达到了最高频率

        frame = (max_freq - 1) * (n + 1) + max_count
        return max(len(tasks), frame)

import heapq
from typing import List
from collections import Counter

class Solution:
    def reorganizeString(self, s: str) -> str:
        freq = Counter(s)
        # 最大堆（存储负数来实现）
        heap: List[tuple] = [(-cnt, ch) for ch, cnt in freq.items()]
        heapq.heapify(heap)

        result: List[str] = []
        prev_cnt, prev_ch = 0, ''      # 上一个放置的字符

        while heap:
            cnt, ch = heapq.heappop(heap)
            result.append(ch)
            # 上一个字符可以放回堆中（如果还有剩余）
            if prev_cnt < 0:
                heapq.heappush(heap, (prev_cnt, prev_ch))
            prev_cnt, prev_ch = cnt + 1, ch   # 减少 1 个（cnt 是负数）

        return ''.join(result) if len(result) == len(s) else ""

from typing import List

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1

        start = 0
        tank = 0
        for i in range(len(gas)):
            tank += gas[i] - cost[i]
            if tank < 0:
                start = i + 1    # 从下一站重试
                tank = 0

        return start