pta python 选择填空题

### Python 实现自定义 `split` 函数 对于想要实现类似于Python内置`split`方法功能的需求，可以编写一个名为`custom_split`的函数来模拟这一行为。此函数接收两个参数：一个是待分割字符串`s`；另一个是分隔符`delimiter`。如果未提供分隔符，默认为空白字符。 ```python def custom_split(s, delimiter=None): result = [] temp_str = '' if not isinstance(s, str): # 如果输入不是字符串则返回空列表 return [] if delimiter is None or delimiter == '': # 处理默认空白字符的情况 import re words = re.split(r'\s+', s.strip()) return [word for word in words if word] for char in s: if char != delimiter: temp_str += char elif temp_str: result.append(temp_str) temp_str = '' if temp_str: # 添加最后一个子串（如果有） result.append(temp_str) return result ``` 上述代码实现了基本的按指定分隔符拆分子串逻辑，并处理了一些特殊情况，如连续多个相同分隔符或首尾存在分隔符的情形[^1]。 ### PTA 平台算法程序填空题练习示例 考虑到PTA平台上常见的编程题目形式，在这里给出一道关于字符串操作的基础练习题作为例子： #### 题目描述 给定一段英文文章，请统计其中单词的数量并按照字母顺序输出各个不同单词及其出现次数。注意忽略大小写的区别，即认为 "Word" 和 "word" 是相同的词。 #### 输入样例 ``` This is a test. This TEST has some repeated WORDS. ``` #### 输出样例 ``` a : 1 has : 1 is : 1 repeated : 1 some : 1 test : 2 this : 2 words : 1 ``` #### 参考解答思路 - 将整个文本转换为小写字母； - 使用之前提到的手动实现的`custom_split()`函数去除标点符号并将句子分解成单个词语组成的列表； - 创建字典记录各不重复单词对应的计数值； - 对键集合进行排序后遍历打印结果。 ```python import string text = input().lower() # 获取用户输入并转为全小写 translator = str.maketrans('', '', string.punctuation) # 定义移除所有标点符号表 cleaned_text = text.translate(translator) # 应用翻译器清理掉标点符号 words_list = custom_split(cleaned_text) # 调用手动编写的split替代方案得到单词序列 frequency_dict = {} for word in words_list: frequency_dict[word] = frequency_dict.get(word, 0) + 1 sorted_keys = sorted(frequency_dict.keys()) for key in sorted_keys: print(f"{key} : {frequency_dict[key]}") ``` 这段代码展示了如何利用前面介绍过的`custom_split`函数解决实际问题的同时也满足了PTA平台上的典型作业要求。

### 关于哈夫曼编码的PTA练习题解析 #### 题目描述 给定一段文字，如果统计出字母出现的频率，则可以根据哈夫曼算法给出一套编码方案，使得用此编码压缩原文可以获得最短的编码总长。然而，哈夫曼编码并不是唯一的。例如对字符串`"aaaxuaxz"`，容易得出字母‘a’、‘x’、‘u’、‘z’的出现频率分别为4、2、1、1。可以通过不同方式设计编码{‘a’=0, ‘x’=10, ‘u’=110,‘z’=111}或{‘a’=1, ‘x’=01, ‘u’=001, ‘z’=000}等，这些都能使原文被压缩至相同长度[^3]。 #### 解决方法概述 为了验证一组编码是否为有效的哈夫曼编码，需满足两个条件： - 编码具有唯一可译性：即不存在一个字符的编码是另一个字符编码的前缀。 - 所有字符按照其频次构建出来的二叉树应当是最优二叉树（最小加权路径长度），从而保证该组编码能够实现最优压缩效果。 #### 实现过程 下面展示了一个简单的Python程序来解决这个问题: ```python from collections import Counter import heapq def is_huffman_code(text, code_dict): freq = dict(Counter(text)) # 构建优先队列并初始化节点列表 heap = [[weight, [char, '']] for char, weight in freq.items()] heapq.heapify(heap) while len(heap) > 1: lo = heapq.heappop(heap) hi = heapq.heappop(heap) for pair in lo[1:]: pair[1] = '0' + pair[1] for pair in hi[1:]: pair[1] = '1' + pair[1] heapq.heappush(heap, [lo[0]+hi[0]] + lo[1:] + hi[1:]) huffman_tree = sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]),p)) # 判断输入code_dict 是否符合huffman tree 结构 for item in huffman_tree: if item[1]!=code_dict[item[0]]: return False return True text_example = "aaaxuaxz" codes_to_check = {'a': '0', 'x': '10', 'u': '110', 'z': '111'} print(is_huffman_code(text_example,codes_to_check)) # 输出True表示这是一个合法的Huffman编码 ``` 这段代码首先计算了原始文本中各个字符出现次数作为权重；接着利用贪心策略不断选取当前剩余集合里权重最低的两棵树合并成新的子树直到只剩下一棵完整的霍夫曼树为止；最后比较生成的霍夫曼编码表与待检验的编码表是否一致即可完成校验工作。