1. 项目概述与背景最近在整理资料时翻到了2019年腾讯编程营的练习题集。这套题目在当时是面向有一定编程基础特别是Python初学者的夏令营活动设计的涵盖了从基础语法到简单算法、数据处理等多个维度的练习。虽然时间过去几年但编程的核心逻辑和解决问题的思路是相通的。我发现很多朋友在自学Python时常常苦于找不到合适的、有梯度的练习题来巩固知识或者即使找到了题目面对五花八门的“参考答案”也感到困惑不知道哪种解法更优、更“Pythonic”。因此我决定花些时间把这套练习题的下半部分拿出来结合我这些年的开发经验不仅给出答案更重要的是拆解每一道题背后的考察点、解题思路的演变过程以及不同解法之间的优劣对比。我希望这份“解答”更像是一份“解题笔记”或“思路复盘”能帮助正在爬坡的Python学习者在理解“怎么做”的同时更明白“为什么这么做”以及“有没有更好的做法”。这套练习题的下半部分难度相较于上半部分有所提升开始涉及一些经典的算法思想如递归、动态规划的雏形、对数据结构的灵活运用列表、字典、集合以及一些实际编程中常见的场景模拟。对于已经掌握了if-else、for循环、函数定义等基础语法的朋友来说这是一个非常好的进阶练习场。接下来我将挑选其中最具代表性的几道题目进行深度剖析。2. 核心题目解析与思路拆解2.1 题目一字符串模式匹配与统计原题描述简述给定一个长字符串text和一个短字符串pattern要求统计pattern在text中出现的所有位置索引从0开始并返回一个列表。例如text “ababababc”, pattern “aba”则应返回[0, 2, 4]。这道题看似简单直接使用str.find()或str.index()循环查找即可但它实际上是一个引子引导我们思考更高效的字符串匹配算法。2.1.1 基础解法与陷阱分析最直观的解法是使用滑动窗口def find_pattern_naive(text, pattern): positions [] len_text, len_pat len(text), len(pattern) # 滑动窗口的起始位置 i 只需遍历到 len_text - len_pat for i in range(len_text - len_pat 1): if text[i:ilen_pat] pattern: positions.append(i) return positions这个解法的时间复杂度是 O((n-m1)*m)其中 n 是text长度m 是pattern长度。在pattern较短时完全可行也是面试中快速写出的基础答案。但这里有一个新手极易忽略的边界陷阱range(len_text - len_pat 1)中的1。如果pattern长度大于textlen_text - len_pat为负数range()接收负数参数会直接返回空迭代器逻辑上是对的不可能找到。但更严谨的写法是先判断 iflen_pat len_text: return []这样意图更清晰。注意在 Python 中text[i:ilen_pat]当ilen_pat超过字符串长度时会自动截取到末尾不会报错。这虽然方便但在这个算法里我们通过循环范围控制避免了无意义的切片是更优的。2.1.2 进阶思考KMP算法引介当题目追问“是否有更优解”或text和pattern规模很大时就需要引入经典的 KMP (Knuth-Morris-Pratt) 算法。它的核心是利用匹配失败时的信息通过一个“部分匹配表”(Next数组)来避免主串指针的回退将时间复杂度降到 O(nm)。对于初学者理解 KMP 的关键在于明白“最长相同前后缀”的概念。我们不必在解答中实现完整的 KMP除非题目明确要求但可以指出这种更优算法的存在并说明其思想“实际上对于大规模字符串匹配有更高效的算法如 KMP。它的精髓在于当某次匹配失败时pattern串本身的信息哪些前缀和后缀是相同的可以告诉我们下一次可以直接将pattern滑动多长的距离而无需回头重新比较text中已经检查过的字符。虽然实现起来稍复杂但这是算法学习路上一个重要的里程碑。”在编程营的练习题层面掌握基础滑动窗口解法并注意边界条件已经能够拿到满分。但作为学习笔记点出更广阔的技术视野是非常有价值的。2.2 题目二列表去重与顺序保持原题描述给定一个可能包含重复元素的列表要求去除重复元素并保持元素在原列表中首次出现的相对顺序。例如输入[3, 2, 1, 2, 4, 3, 1]输出[3, 2, 1, 4]。这道题完美考察了对 Python 数据结构特性和时间复杂度的理解。2.2.1 常见误区与低效解法新手可能会想到用一个新列表遍历原列表如果元素不在新列表中则追加def remove_duplicates(lst): new_lst [] for item in lst: if item not in new_lst: # 这里每次 in 操作都是 O(k), k 为新列表当前长度 new_lst.append(item) return new_lst这个方法虽然能保持顺序但效率很低。因为if item not in new_lst本质是线性查找整个算法的时间复杂度是 O(n²)。2.2.2 高效解法利用集合Set进行成员检测优化的关键是快速判断一个元素是否已经出现过。Python 的set基于哈希表其in操作的平均时间复杂度是 O(1)。我们可以利用一个辅助集合来记录已经遇到过的元素def remove_duplicates_efficient(lst): seen set() result [] for item in lst: if item not in seen: seen.add(item) result.append(item) return result这个算法的时间复杂度是 O(n)因为每次查找和插入set的操作平均都是常数时间。空间复杂度是 O(n)用于存储集合和结果列表。2.2.3 更“Pythonic”的写法与原理对于熟悉 Python 的朋友可能会想到用dict.fromkeys或者利用 Python 3.7 中字典保持插入顺序的特性# 方法一利用字典键的唯一性和顺序性 (Python 3.7 保证) def remove_duplicates_dict(lst): return list(dict.fromkeys(lst)) # 方法二使用 collections.OrderedDict (兼容更早版本) from collections import OrderedDict def remove_duplicates_ordereddict(lst): return list(OrderedDict.fromkeys(lst))dict.fromkeys(lst)会以lst中的元素为键创建一个字典重复的键自然被去重并且从 Python 3.7 开始字典正式保证了插入顺序。这行代码非常简洁其内在原理和我们上面“集合列表”的方法异曲同工可读性极高是生产环境中常用的写法。实操心得在面试或快速原型开发中list(dict.fromkeys(lst))是首选因为它简洁且高效。但在向初学者讲解时务必先揭示set辅助查找的原理这是理解算法效率的关键。同时要指出如果列表元素是不可哈希的类型如列表、字典那么上述所有方法都会报错这是由set和dict的底层实现决定的。2.3 题目三模拟简单缓存LRU 最近最少使用机制原题描述设计一个简易的缓存系统缓存容量为capacity。提供put(key, value)和get(key)方法。当缓存满时put操作需要淘汰最久未被访问的键值对LRU策略。要求get和put操作的时间复杂度尽可能低。这道题已经触及了数据结构设计的核心是面试中的高频题。它综合考察了哈希表字典和双向链表或 OrderedDict的应用。2.3.1 问题抽象与数据结构选型核心需求快速访问通过key快速找到对应的value。这指向哈希表Python 字典O(1) 时间复杂度。维护顺序需要知道哪些数据是“最近使用过”的哪些是“最久未使用”的。这需要一种有序的数据结构并且要支持在任意位置快速插入和删除。数组列表删除非末尾元素是 O(n)不合适。单向链表删除指定节点需要知道前驱节点不方便。因此经典解决方案是哈希表 双向链表。哈希表{key: ListNode}实现 O(1) 的查找。双向链表节点按访问时间排序头节点是最近访问的尾节点是最久未访问的。链表支持在任意位置 O(1) 时间插入和删除节点前提是已获得该节点的引用。2.3.2 详细设计与 Python 实现我们先定义双向链表节点class DLinkedNode: def __init__(self, key0, value0): self.key key self.value value self.prev None self.next None然后实现 LRU 缓存类class LRUCache: def __init__(self, capacity: int): self.capacity capacity self.size 0 self.cache {} # 哈希表映射 key - Node # 使用伪头部和伪尾部节点简化边界条件判断 self.head DLinkedNode() self.tail DLinkedNode() self.head.next self.tail self.tail.prev self.head def _add_node_to_head(self, node: DLinkedNode): 将节点添加到伪头部之后链表头部 node.prev self.head node.next self.head.next self.head.next.prev node self.head.next node def _remove_node(self, node: DLinkedNode): 从链表中移除指定节点 node.prev.next node.next node.next.prev node.prev def _move_node_to_head(self, node: DLinkedNode): 将某个已存在的节点移动到链表头部 self._remove_node(node) self._add_node_to_head(node) def _pop_tail(self) - DLinkedNode: 弹出并返回链表尾部的节点最久未使用 node self.tail.prev self._remove_node(node) return node def get(self, key: int) - int: if key not in self.cache: return -1 # 题目通常要求未找到返回 -1 node self.cache[key] # 访问了该节点需将其移动到头部 self._move_node_to_head(node) return node.value def put(self, key: int, value: int) - None: if key in self.cache: # key 已存在更新值并移动到头部 node self.cache[key] node.value value self._move_node_to_head(node) else: # key 不存在创建新节点 new_node DLinkedNode(key, value) self.cache[key] new_node self._add_node_to_head(new_node) self.size 1 # 如果超出容量移除尾部节点 if self.size self.capacity: tail_node self._pop_tail() del self.cache[tail_node.key] # 从哈希表中也删除 self.size - 12.3.3 利用collections.OrderedDict的取巧实现在 Python 中collections.OrderedDict本身就是一个维护插入顺序的字典并且提供了move_to_end(key, lastTrue)方法将某个键移动到末尾lastTrue或开头lastFalse。我们可以将链表尾部视为最久未使用那么get和put更新时就把键移到开头容量满时弹出最后一个键。from collections import OrderedDict class LRUCacheUsingOrderedDict: 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) self.cache[key] value # 检查容量 if len(self.cache) self.capacity: # popitem(lastFalse) 移除并返回第一个插入的键值对最久未使用 self.cache.popitem(lastFalse)注意事项OrderedDict的实现通常也是基于双向链表所以其move_to_end和popitem操作也是 O(1)。这种写法极其简洁是 Python 解决此类问题的“作弊器”。但在面试中面试官很可能要求你实现底层结构以考察你对数据结构的掌握程度。所以理解“哈希表双向链表”的原理是根本。3. 题目四递归与分治思想的应用——计算x的n次幂原题描述实现函数pow(x, n)计算x的n次幂。要求效率尽可能高。这道题是递归和分治算法的经典入门题。暴力解法是循环n次连乘时间复杂度 O(n)。但利用分治思想可以优化到 O(log n)。3.1 思路演化从暴力到分治最直接的想法def pow_naive(x, n): result 1 for _ in range(n): result * x return result如果n很大比如上亿这个循环将非常慢。我们观察到x^n x^(n/2) * x^(n/2)当 n 为偶数。这样我们可以把一个大问题n次方分解成两个规模减半的子问题n/2次方子问题的结果可以复用。这就是分治。3.2 递归分治实现与细节处理递归实现需要考虑以下几点终止条件n 0时返回 1任何数的0次幂为1。负数次幂x^(-n) 1 / (x^n)。奇偶性如果n是偶数pow(x, n) pow(x, n//2) ** 2如果n是奇数pow(x, n) x * pow(x, n//2) ** 2注意n//2在 Python 中是向下取整def pow_recursive(x: float, n: int) - float: # 处理 n 为负数的情况 if n 0: x 1 / x n -n # 递归辅助函数 def helper(x, n): if n 0: return 1 half helper(x, n // 2) # 计算子问题 if n % 2 0: return half * half else: return x * half * half return helper(x, n)3.3 迭代实现与位运算优化递归实现有函数调用开销我们可以用迭代方式重写并利用位运算判断奇偶性和进行除以2的操作效率更高。思路是将指数n用二进制表示。例如x^13 x^(1101)_2 x^(8) * x^(4) * x^(1)。我们在迭代中让x不断自乘x x * x相当于计算x^1, x^2, x^4, x^8...。同时我们检查n的二进制位如果某位是1就把当前的x乘到结果中。def pow_iterative(x: float, n: int) - float: if n 0: x 1 / x n -n result 1 current_product x while n 0: # 如果当前二进制位为1则乘入结果 if n 1: # n % 2 1 result * current_product # current_product 自乘相当于计算 x^(2^k) current_product * current_product # n 右移一位相当于 n // 2 n 1 return result这个迭代版本的时间复杂度是 O(log n)空间复杂度是 O(1)是最优的解法之一。常见问题为什么current_product初始值是x而不是1因为current_product代表的是x^(2^0)即x^1。在第一次循环时如果n的最低位是1result就应该乘以x^1。4. 题目五利用栈处理表达式求值简化版原题描述给定一个字符串表达式包含数字、、-、*、/和空格实现一个基本计算器来计算其值。表达式中的运算都是整数运算/为整数除法向零取整。这是一个简化版假设输入表达式总是有效的。这道题是栈数据结构的典型应用考察对运算符优先级和计算顺序的理解。4.1 核心思路双栈法我们可以使用两个栈操作数栈 (num_stack)存放待计算的数字。运算符栈 (op_stack)存放运算符。算法流程调度场算法思想的简化遍历表达式字符串。遇到数字解析完整的数字并入操作数栈。遇到运算符如果当前运算符优先级小于或等于运算符栈顶运算符的优先级则先进行栈顶运算符的运算从操作数栈弹出两个数从运算符栈弹出一个运算符计算后将结果压回操作数栈然后再将当前运算符入栈。这保证了*和/在和-之前计算。否则直接入栈。遍历结束后依次弹出运算符栈中的运算符进行计算直到运算符栈为空。操作数栈中剩下的最后一个数就是结果。4.2 优先级处理与代码实现我们需要一个函数来定义运算符的优先级。def calculate(s: str) - int: def precedence(op): if op in (, -): return 1 if op in (*, /): return 2 return 0 def apply_operation(a, b, op): if op : return a b if op -: return a - b if op *: return a * b if op /: # 向零取整的整数除法 return int(a / b) # 使用 int() 而非 //因为 // 是向下取整 num_stack [] op_stack [] i 0 n len(s) while i n: if s[i] : i 1 continue elif s[i].isdigit(): # 解析完整数字 num 0 while i n and s[i].isdigit(): num num * 10 int(s[i]) i 1 num_stack.append(num) # 注意这里已经 i 指向了数字后的字符循环末尾不 i1 continue else: # 是运算符 while op_stack and precedence(op_stack[-1]) precedence(s[i]): b num_stack.pop() a num_stack.pop() op op_stack.pop() num_stack.append(apply_operation(a, b, op)) op_stack.append(s[i]) i 1 # 处理剩余的运算符 while op_stack: b num_stack.pop() a num_stack.pop() op op_stack.pop() num_stack.append(apply_operation(a, b, op)) return num_stack[0]4.3 处理负数与括号的扩展思考原题是简化版。更完整的计算器还需要处理负数例如“-12”。可以在解析时如果遇到-号且前面不是数字也不是右括号)则认为是负号将下一个数字解析为负数入栈。括号括号会改变运算顺序。遇到左括号(直接入运算符栈遇到右括号)则不断弹出运算符栈进行计算直到遇到左括号(为止。实操心得表达式求值的关键在于延迟计算。栈帮助我们保存了暂时不能计算的操作数和运算符直到遇到优先级更低的运算符或表达式结束时才进行之前的计算。在编写这类代码时要特别注意索引i的移动和continue的使用确保完整解析数字。调试时可以打印出每一步两个栈的状态这对理解算法流程非常有帮助。5. 常见问题与调试技巧实录在解决这些练习题的过程中尤其是自己动手实现时肯定会遇到各种“坑”。下面我总结几个高频问题和调试技巧。5.1 关于递归的深度与栈溢出问题在实现递归分治如pow函数或深度优先搜索时如果递归层数过深例如n很大Python 可能会抛出RecursionError: maximum recursion depth exceeded。排查与解决检查终止条件确保递归函数一定有终止条件并且每次递归调用都向终止条件靠近。尾递归优化Python 默认不支持尾递归优化。对于可以写成尾递归形式的函数可以尝试手动改写成迭代形式这是最根本的解决方法。例如pow的迭代版本。修改递归深度限制不推荐作为常规手段可以通过sys.setrecursionlimit(limit)提高限制但这只是权宜之计可能掩盖程序逻辑问题并消耗大量内存。5.2 列表修改与迭代的陷阱问题在遍历列表的同时对其进行增删操作可能导致意想不到的结果或RuntimeError。# 错误示例想删除列表中所有的偶数 lst [1, 2, 3, 4, 5, 6] for i, num in enumerate(lst): if num % 2 0: lst.pop(i) # 这会改变列表长度和索引导致后续迭代出错或漏删解决创建新列表最安全的方法是使用列表推导式创建新列表。lst [1, 2, 3, 4, 5, 6] lst [num for num in lst if num % 2 ! 0] # [1, 3, 5]反向遍历如果必须在原列表上操作可以反向遍历这样删除元素不会影响未遍历部分的索引。lst [1, 2, 3, 4, 5, 6] for i in range(len(lst)-1, -1, -1): if lst[i] % 2 0: lst.pop(i)5.3 字典键的存在性判断问题在 LRU 缓存或类似场景中直接if dict[key]来判断键是否存在如果键不存在且其对应的值为假值如0,[],False则会误判。解决始终使用key in dict或dict.get(key)方法。my_dict {a: 0, b: []} # 错误 if my_dict.get(a): # 条件为 False因为 my_dict[a] 0 print(a exists) # 正确 if a in my_dict: # 条件为 True print(a exists) value my_dict.get(c, default) # 安全地获取不存在则返回default5.4 浮点数比较的精度问题问题在涉及浮点数计算如pow(x, n)中的x为浮点数或比较时直接使用可能因为精度问题得到错误结果。解决判断两个浮点数是否“足够接近”而不是完全相等。# 错误 if result expected: ... # 正确 if abs(result - expected) 1e-9: # 设置一个极小的误差容忍度 ...5.5 调试利器print与pdb对于算法题最直接的调试方法就是在关键步骤插入print语句打印变量的状态如栈的内容、循环索引、中间结果。对于更复杂的逻辑可以学习使用 Python 内置的调试器pdb。在代码中插入import pdb; pdb.set_trace()程序运行到此处会进入交互式调试环境。常用命令n(执行下一行)s(进入函数)c(继续运行)p 变量名(打印变量)l(查看当前代码上下文)。5.6 单元测试意识养成为自己写的函数编写简单测试用例的习惯。这能快速验证基本功能是否正确并在修改代码后快速回归测试。def test_pow(): assert pow_iterative(2, 10) 1024 assert pow_iterative(2, -2) 0.25 assert pow_iterative(0, 10) 0 assert pow_iterative(5, 0) 1 print(All tests passed!) test_pow()解决编程练习题最终目的不是“做出这一道题”而是通过这道题掌握一类问题的解决方法并锻炼将思路转化为严谨、高效代码的能力。希望这份针对腾讯编程营部分练习题的深度解析能为你提供除了答案之外更多关于“如何思考”和“如何实现得更好”的启发。编程之路道阻且长行则将至。多练、多思、多总结共勉。