1， (Huffman) 给定字符串”ABACCADCACCDCDA”, 选择各个字符合适的二进制表示，使得： （1） 没有一个表示是另一个表示的前缀； （2） 原字符串的总二进制表示最短。 2， 给定一个数组，找到其中第k小的元素。用代码实现

1. 这里给出使用Python实现哈夫曼编码的代码：

import heapq
from collections import Counter, namedtuple

# 哈夫曼编码节点类
class HuffmanNode(namedtuple("HuffmanNode", ["left", "right"])):
    def walk(self, code, acc):
        self.left.walk(code, acc + "0")
        self.right.walk(code, acc + "1")

# 哈夫曼编码叶子节点类
class HuffmanLeaf(namedtuple("HuffmanLeaf", ["char"])):
    def walk(self, code, acc):
        code[self.char] = acc or "0"

# 构建哈夫曼树
def build_huffman_tree(freqs):
    heap = [HuffmanLeaf(char) for char, freq in freqs.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        node_left = heapq.heappop(heap)
        node_right = heapq.heappop(heap)
        node = HuffmanNode(node_left, node_right)
        heapq.heappush(heap, node)
    return heap[0]

# 哈夫曼编码
def encode(s):
    freqs = Counter(s)
    tree = build_huffman_tree(freqs)
    code = {}
    tree.walk(code, "")
    return "".join(code[char] for char in s)

# 哈夫曼解码
def decode(s, tree):
    res = []
    node = tree
    for ch in s:
        node = node.left if ch == "0" else node.right
        if isinstance(node, HuffmanLeaf):
            res.append(node.char)
            node = tree
    return "".join(res)

# 测试
s = "ABACCADCACCDCDA"
encoded = encode(s)
print("Encoded:", encoded)
tree = build_huffman_tree(Counter(s))
decoded = decode(encoded, tree)
print("Decoded:", decoded)

2. 给定一个数组，找到其中第k小的元素可以使用Python内置的heapq模块中的nlargest函数，该函数可以返回一个数组中前k个最大的元素。因为前k个最大的元素就是后n-k个最小的元素，因此可以通过取反后再使用该函数找到前n-k个最大的元素，然后取反即可得到前k个最小的元素。代码如下：

import heapq

def find_kth_smallest(nums, k):
    if k < 1 or k > len(nums):
        return None
    return -heapq.nlargest(len(nums) - k + 1, [-num for num in nums])[-1]

# 测试
nums = [3, 7, 1, 9, 2, 5, 8, 4, 6]
k = 3
print(find_kth_smallest(nums, k)) # 3