1. 项目背景与核心价值最近在整理资料时翻到了当年在西工大NOJ平台上刷题的记录特别是81到90这十道题。对于很多刚接触Python编程的同学来说NOJ的题目设计其实很有嚼头它不像一些纯算法平台那样上来就搞动态规划、图论而是更侧重于用Python的特性去解决一些实际问题考察你对语言本身的理解和运用。这十道题表面上看是独立的作业但串联起来恰好能帮你把Python里几个核心但容易混淆的概念——比如列表推导式、字典的妙用、字符串处理、函数式编程的map/filter——给彻底捋清楚。很多人学Python语法背得滚瓜烂熟一写代码就卡壳问题往往就出在这些“知道但不会用”的细节上。我打算结合当年的解题思路和后来工作中积累的经验把这十道题重新拆解一遍目标不是单纯给出答案而是带你理解每道题“为什么这么出”以及“除了常规解法还有哪些更Pythonic的写法”。无论你是正在啃NOJ作业的西工大学弟学妹还是想通过经典题目巩固Python基础的自学者这篇长文都能给你提供一条清晰的进阶路径。2. 题目81矩阵对角线元素之和——理解索引与循环的边界这道题通常要求计算一个N*N矩阵的主对角线和副对角线元素之和。这是二维列表列表嵌套操作的经典入门题。2.1 问题核心与常见误区很多新手的第一反应是用两层嵌套循环遍历所有i和j当i j时累加到主对角线当i j N-1时累加到副对角线。这个方法直观但效率是O(N²)并且容易在副对角线的判断条件上出错N-1这个边界值。更关键的是它没有利用Python序列索引的特性。一个更Pythonic的思路是直接通过索引访问。对于主对角线元素位置是(0,0), (1,1), ..., (N-1, N-1)我们可以用单层循环for i in range(N)然后累加matrix[i][i]即可。对于副对角线元素位置是(0, N-1), (1, N-2), ..., (N-1, 0)规律是matrix[i][N-1-i]。def diagonal_sum(matrix): n len(matrix) primary_sum sum(matrix[i][i] for i in range(n)) secondary_sum sum(matrix[i][n-1-i] for i in range(n)) # 注意如果矩阵阶数为奇数中心元素会被计算两次根据题目要求决定是否减去 total primary_sum secondary_sum if n % 2 1: center matrix[n//2][n//2] total - center # 如果要求和不相交则需要减去一次中心元素 return total实操心得 这里用到了生成器表达式(matrix[i][i] for i in range(n))配合sum()函数比显式写循环累加更简洁、高效。判断奇数阶中心元素是否需要减去是这道题一个常见的陷阱务必仔细阅读题目要求是“求两条对角线所有元素的和”还是“求两条对角线上不重复元素的和”。2.2 进阶思考使用NumPy库在实际的数据科学或工程计算中我们几乎不会自己写循环处理矩阵。NumPy库是事实上的标准。用NumPy这道题一行代码就能解决import numpy as np def diagonal_sum_numpy(matrix): arr np.array(matrix) primary_sum np.trace(arr) # 主对角线之和 secondary_sum np.trace(np.fliplr(arr)) # 翻转后取主对角线即原副对角线之和 return primary_sum secondary_sumnp.trace()是专门用来求迹对角线元素和的函数np.fliplr()是左右翻转矩阵。虽然NOJ作业可能不允许用第三方库但了解这种工业级做法能极大开阔思路明白“工具选型”的重要性。当你未来处理真实数据时一个优化过的库函数和手写循环性能可能有成百上千倍的差距。3. 题目82字符串中数字字符个数统计——掌握字符串遍历与字符判断这道题要求统计一个给定字符串中数字字符‘0’到‘9’的个数。它训练的是对字符串的迭代操作和字符分类判断。3.1 多种解法对比方法一显式循环与比较这是最基础的方法遍历字符串用if char in ‘0123456789’:或if ‘0’ char ‘9’:进行判断。def count_digits_v1(s): count 0 for char in s: if 0 char 9: count 1 return count方法二使用str.isdigit()方法这是更Pythonic的做法。str.isdigit()方法会判断字符串是否只包含数字对于单个字符也适用。它比方法一更简洁意图更清晰。def count_digits_v2(s): return sum(1 for char in s if char.isdigit())这里再次使用了生成器表达式为每一个是数字的字符生成一个1然后用sum()求和避免了显式的计数器变量。方法三使用filter()函数filter()函数接受一个判断函数和一个可迭代对象返回一个迭代器其中包含所有使判断函数为True的元素。我们可以用它过滤出所有数字字符然后计算长度。def count_digits_v3(s): return len(list(filter(str.isdigit, s)))这种方法函数式编程的味道更浓。需要注意的是filter()返回的是迭代器我们需要用list()将其转化为列表才能获取长度。对于超长字符串list()可能会消耗较多内存此时可以用sum(1 for _ in filter(...))的变体。3.2 性能与可读性权衡对于这种简单任务三种方法性能差异微乎其微。选择哪种方法更多取决于团队编码风格和上下文。在强调可读性的日常开发中方法二sumisdigit通常是首选因为它一行代码清晰表达了“对字符串中所有数字字符计数”的意图没有多余的循环变量和条件判断结构。注意str.isdigit()和str.isnumeric()、str.isdecimal()有细微区别。isdigit()对于ASCII数字0-9和一些其他语言中的数字字符如上标数字也会返回True。在NOJ的语境下通常只考虑ASCII数字所以用‘0’ char ‘9’是绝对安全的。但在更广泛的场景理解这些方法的区别很重要。4. 题目83列表元素偶奇拆分与重组——深入列表操作与切片这道题通常要求将一个列表中的所有偶数放到前面奇数放到后面并保持偶数、奇数各自的相对顺序。这是一个经典的“稳定分区”问题。4.1 暴力解法与空间开销最直接的想法是创建两个新列表even_list和odd_list遍历原列表分别将偶数和奇数添加进去最后将两个列表连接。def separate_parity_naive(lst): evens [] odds [] for num in lst: if num % 2 0: evens.append(num) else: odds.append(num) return evens odds这个方法的时间复杂度是O(N)空间复杂度也是O(N)因为它需要额外的两个列表来存储结果。优点是稳定保持顺序且极其清晰易懂。4.2 原地重排的挑战与“双指针”思想如果题目要求“原地修改”列表即不使用额外空间O(1)空间复杂度难度就上来了。这引入了算法中常见的“双指针”或“快慢指针”思想。一种思路是模仿快速排序的分区操作但快速排序的分区是不稳定的会打乱偶数和奇数内部的顺序。为了稳定地原地重排一个巧妙的做法是使用“插入”的思想遍历列表当遇到偶数时将其“插入”到已整理好的偶数序列的末尾。这可以通过一个指向下一个偶数应放置位置的指针even_index来实现。def separate_parity_inplace(lst): even_index 0 for i in range(len(lst)): if lst[i] % 2 0: # 将当前偶数移动到even_index位置 lst[even_index], lst[i] lst[i], lst[even_index] # 如果交换的不是同一个元素需要将i位置被换过来的元素可能是奇数放到合适位置 # 更简单的做法将偶数依次前插 # 这里提供一种更清晰的稳定原地重排写法但可能不是最优 pass # 此处代码略复杂通常NOJ不要求稳定原地实际上稳定的原地重排代码会稍显复杂在面试或算法竞赛中可能出现但在NOJ的基础作业中使用额外空间的清晰解法是完全可接受的。重要的是理解不同解法在时间和空间上的权衡。4.3 Pythonic的列表推导式解法利用列表推导式我们可以写出非常简洁的一行代码def separate_parity_pythonic(lst): return [x for x in lst if x % 2 0] [x for x in lst if x % 2 ! 0]这个解法本质上和暴力解法一样创建了两个新列表然后连接。它的优势在于语法简洁意图一目了然“返回所有偶数组成的列表加上所有奇数组成的列表”。在Python社区这种写法深受欢迎。踩坑提醒 注意判断奇偶时对于负数num % 2的结果可能是1或-1取决于Python版本在Python中-1 % 2 1。所以用num % 2 0判断偶数是安全的。如果使用位运算num 1 0对于负数也同样有效且速度更快但可读性稍差。5. 题目84字典合并与值累加——驾驭字典的get()与update()这道题通常给出两个字典要求合并它们。如果键重复则将其对应的值相加。这是学习字典核心操作get()、update()和字典推导式的绝佳例题。5.1 基础解法遍历与get()方法最稳健的方法是创建一个新字典或复制其中一个字典然后遍历另一个字典。对于遍历到的每个键值对使用get(key, 0)来安全地获取当前结果字典中该键的值如果不存在则返回0然后加上新值。def merge_dicts(dict1, dict2): result dict1.copy() # 避免修改原字典 for key, value in dict2.items(): result[key] result.get(key, 0) value return result这里dict.get(key, default)方法是关键。它避免了直接使用result[key]可能引发的KeyError异常。dict.items()方法用于同时遍历键和值。5.2 使用collections.Counter工具类Python标准库中的collections.Counter是专门为计数场景设计的字典子类。它重载了加法运算符合并时自动对相同键的值进行相加。from collections import Counter def merge_dicts_counter(dict1, dict2): return dict(Counter(dict1) Counter(dict2))Counter(dict1)将普通字典转换为计数器操作符完成合并与累加最后再用dict()转回普通字典如果需要。这种方法代码极其简洁且性能优异因为它底层是用C实现的。强烈建议掌握Counter它在处理词频统计、投票汇总等场景时是无敌神器。5.3 字典推导式与union操作Python 3.9从Python 3.9开始字典支持合并运算符|。我们可以利用它和字典推导式写出更现代的代码def merge_dicts_modern(dict1, dict2): # 先取并集键然后计算每个键的和 all_keys dict1.keys() | dict2.keys() return {key: dict1.get(key, 0) dict2.get(key, 0) for key in all_keys}dict1.keys() | dict2.keys()得到两个字典所有键的并集集合。然后推导式为每个键计算两个字典中值的和。这种方法不修改原字典也一目了然。经验之谈 在真实项目中如果合并操作频繁或者字典很大collections.Counter通常是性能和代码简洁性的最佳选择。如果环境受限如某些嵌入式环境或无标准库则采用基础遍历法。理解get(key, default)这个模式是处理字典“可能存在也可能不存在”的键的标准做法这个模式会贯穿你的整个Python编程生涯。6. 题目85寻找列表中的第二大元素——避免排序的线性扫描这道题要求找出列表中第二大的数。一个偷懒的办法是排序sorted_list sorted(set(lst), reverseTrue)然后取sorted_list[1]。但排序的时间复杂度是O(N log N)而且如果列表中有重复元素需要先用set()去重否则“第二大”可能和第一大相等。6.1 线性扫描算法一次遍历更高效的算法是只扫描一次列表用两个变量first和second分别记录当前遇到的最大值和第二大值。def find_second_largest(lst): if len(lst) 2: return None # 或根据题目要求处理 # 初始化first和second first second float(-inf) for num in lst: if num first: # 发现新的最大值原最大值变成第二大值 second first first num elif first num second: # 当前数介于当前最大值和第二大值之间更新第二大值 second num # 如果num second忽略 if second float(-inf): return None # 所有元素都相同没有真正的第二大值 return second这个算法的时间复杂度是O(N)空间复杂度是O(1)。关键在于更新逻辑只有当遇到比first更大的数时才同时更新first和second如果遇到比first小但比second大的数只更新second。6.2 使用堆Heap数据结构另一种思路是利用堆。我们可以使用heapq模块的nlargest函数。import heapq def find_second_largest_heap(lst): if len(lst) 2: return None # 获取最大的两个元素 two_largest heapq.nlargest(2, set(lst)) # 先去重 return two_largest[1] if len(two_largest) 2 else Noneheapq.nlargest(2, iterable)内部实现会维护一个大小为2的最小堆时间复杂度约为O(N log 2) O(N)对于找少量最大/最小元素的情况非常高效。同样需要先对列表去重。避坑指南 这道题最大的坑在于重复元素和输入边界。如果列表是[5, 5, 4, 3]第二大值应该是4而不是5。所以必须在逻辑中处理相等的情况上述线性扫描算法中的elif first num second条件就避免了等于first的情况。同时要考虑列表元素少于2个、所有元素都相同等边界情况确保程序健壮性。7. 题目86字符串单词反转保留空格——精细化的字符串处理这道题要求将字符串中的每个单词反转同时保留单词间的原始空格。例如Hello World变成olleH dlroW。它综合考察字符串分割、反转、连接操作。7.1 使用split()和join()的标准解法最直接的思路是用str.split()将字符串按空白字符空格、制表符等分割成单词列表反转每个单词再用str.join()连接起来。但这里有个陷阱split()在不指定分隔符时会合并连续的空白字符。如果原字符串有多个连续空格split()后的列表会丢失这个信息导致最后连接时只能用单个空格。为了保留所有空格我们需要使用str.split( )即明确指定按单个空格分割。这样连续空格会产生空字符串元素。def reverse_words_preserve_spaces(s): words s.split( ) # 按单个空格分割 reversed_words [word[::-1] for word in words] # 反转每个单词 return .join(reversed_words) # 用单个空格连接但是如果原字符串包含制表符\t或其他空白这个方法就不准确了因为它只按空格分割。7.2 通用解法正则表达式与re.findall()为了完美保留所有空白字符包括空格、制表符、换行符等的原始位置和数量我们需要更强大的工具——正则表达式。思路是找到所有连续的非空白字符序列即单词分别反转它们。import re def reverse_words_general(s): # 使用正则表达式找到所有单词连续的非空白字符 words re.findall(r\S, s) # 同时用split捕获所有空白字符包括作为分隔符的 # 更巧妙的方法用re.sub对每个匹配的单词进行反转替换 def reverse_match(match): return match.group(0)[::-1] return re.sub(r\S, reverse_match, s)re.sub(pattern, repl, string)会将字符串中所有匹配模式\S一个或多个非空白字符的部分替换为函数reverse_match的返回值。这个函数接收一个匹配对象返回该匹配字符串的反转。这样所有空白字符原封不动只有单词被原地反转。性能考量 对于简单的、只有普通空格的字符串第一种方法更快。如果需要处理复杂的空白字符或要求绝对精确正则表达式方法更可靠。在NOJ的语境下通常输入比较规范第一种方法足够。但了解正则表达式的应用场景是处理复杂文本的必备技能。8. 题目87计算斐波那契数列第N项——递归、迭代与优化斐波那契数列是经典的递归教学案例但直接使用朴素递归会导致指数级的时间复杂度。这道题要求计算第N项N可能较大因此必须考虑效率。8.1 朴素递归及其问题定义F(0)0, F(1)1, F(n)F(n-1)F(n-2)。递归写法非常简洁def fib_recursive(n): if n 1: return n return fib_recursive(n-1) fib_recursive(n-2)这个算法的时间复杂度是O(2^N)因为存在大量的重复计算例如计算F(5)需要计算F(4)和F(3)而计算F(4)又要计算F(3)和F(2)F(3)被计算了两次。对于稍大的N如50程序就会慢到无法接受。8.2 迭代动态规划解法我们可以从底向上计算只使用两个变量来存储前两项依次递推。def fib_iterative(n): if n 1: return n a, b 0, 1 # F(0), F(1) for _ in range(2, n1): a, b b, a b # 同时更新b成为新的F(i)a成为旧的F(i-1) return b这个算法的时间复杂度是O(N)空间复杂度是O(1)效率极高。a, b b, a b这行代码是Python中交换并计算的经典写法它先计算右边的元组(b, ab)然后同时赋值给左边的(a, b)避免了使用临时变量。8.3 记忆化递归Memoization如果我们想保留递归形式的清晰逻辑又避免重复计算可以使用“记忆化”技术即用一个缓存字典来存储已经计算过的结果。from functools import lru_cache lru_cache(maxsizeNone) def fib_memo(n): if n 1: return n return fib_memo(n-1) fib_memo(n-2)lru_cache是Python标准库提供的一个装饰器它会自动为函数添加缓存。maxsizeNone表示缓存不限大小。第一次计算fib_memo(n)时它会递归计算并缓存所有中间结果。后续再次调用相同参数时直接返回缓存值时间复杂度也降到了O(N)。选型建议 在NOJ作业或算法竞赛中迭代解法是首选因为它既快又省内存。在工程代码中如果递归逻辑更清晰且调用频繁记忆化递归是优雅且高效的选择。理解这三种方法的差异是理解算法优化和计算机如何“思考”的重要一步。9. 题目88列表去重并保持顺序——dict的妙用与Python 3.7特性这道题要求去除列表中的重复元素同时保持元素第一次出现的顺序。例如[3, 1, 2, 1, 3, 2]去重后应为[3, 1, 2]。9.1 使用字典维护顺序Python 3.6之前在Python 3.6之前字典不保证插入顺序。但我们可以利用字典键的唯一性并结合一个列表来记录顺序。def remove_duplicates_old(lst): seen {} result [] for item in lst: if item not in seen: seen[item] True result.append(item) return result或者更简洁地使用collections.OrderedDict有序字典from collections import OrderedDict def remove_duplicates_ordereddict(lst): return list(OrderedDict.fromkeys(lst))OrderedDict.fromkeys(lst)会以lst中的元素为键创建一个有序字典因为字典键唯一所以自动去重并且OrderedDict记住了键的插入顺序。9.2 利用Python 3.7字典的插入顺序特性从Python 3.7开始语言规范正式规定字典会保持元素的插入顺序。这使得去重变得异常简单def remove_duplicates(lst): return list(dict.fromkeys(lst))dict.fromkeys(lst)创建一个新字典以lst中的元素为键所有键对应的值均为None。由于字典键的唯一性重复元素被自动去除。又因为字典保持插入顺序所以list()转换回列表时顺序得以保留。这行代码简洁、高效是当前最Pythonic的写法。9.3 使用集合与列表推导式不保序如果不需要保持顺序最简单的是使用集合def remove_duplicates_no_order(lst): return list(set(lst))但注意set()是无序的结果的顺序是随机的实际上基于哈希值。一个常见的坑对于包含不可哈希unhashable元素如列表、字典的列表上述所有基于字典或集合的方法都会报错TypeError。此时如果需要去重只能使用遍历比较的方法时间复杂度为O(N²)。经验总结list(dict.fromkeys(lst))是处理可哈希元素列表去重保序的黄金标准记住它。同时要清楚其前提列表元素必须是可哈希的Python版本需在3.7以上。在团队协作或维护老代码时需要留意运行环境。10. 题目89验证回文串忽略大小写与非字母数字——字符串预处理与双指针这道题要求判断一个字符串在忽略大小写、忽略非字母数字字符后是否是一个回文串。例如A man, a plan, a canal: Panama应该返回True。10.1 预处理反转比较法最直观的思路是先对字符串进行清洗只保留字母数字并统一转为小写或大写然后判断清洗后的字符串是否等于其反转。def is_palindrome_simple(s): # 1. 清洗字符串 cleaned .join(ch.lower() for ch in s if ch.isalnum()) # 2. 判断是否回文 return cleaned cleaned[::-1]ch.isalnum()用来判断字符是否是字母或数字。cleaned[::-1]是字符串反转的切片技巧。这个方法逻辑清晰但需要额外的O(N)空间来存储清洗后的字符串。10.2 双指针原地判断法为了节省空间我们可以使用双指针一个从头部开始一个从尾部开始向中间移动在移动过程中跳过非字母数字字符并进行比较。def is_palindrome_two_pointers(s): left, right 0, len(s) - 1 while left right: # 移动左指针直到指向一个字母数字字符 while left right and not s[left].isalnum(): left 1 # 移动右指针直到指向一个字母数字字符 while left right and not s[right].isalnum(): right - 1 # 比较忽略大小写 if s[left].lower() ! s[right].lower(): return False left 1 right - 1 return True这个算法的时间复杂度是O(N)但只需要常数级别的额外空间。关键在于内层的两个while循环它们负责跳过无效字符。注意循环条件left right防止指针越界。细节与陷阱字符判断一定要使用.isalnum()而不是.isalpha()因为题目要求字母和数字。大小写转换比较前使用.lower()或.upper()统一大小写。指针移动在双指针法中每次比较成功后别忘记将left和right各移动一位否则会陷入死循环。空字符串或全无效字符对于!!!这样的字符串双指针法中的内层while循环会一直移动指针直到left right然后外层循环结束返回True空字符串或单字符被视为回文。这通常是符合逻辑的。选型建议 如果字符串很长且非字母数字字符很多双指针法在空间上有优势。但代码稍复杂。对于大多数情况预处理反转法因其极高的可读性和不易出错的特点是更推荐的选择。除非有明确的内存限制否则“清晰正确”比“极致优化”更重要。11. 题目90生成杨辉三角的前N行——理解列表的引用与复制杨辉三角的每个数是其左上方和右上方的数的和。要求生成前N行返回一个二维列表。11.1 逐行构造法最自然的方法是逐行计算。每一行的第一个和最后一个元素是1中间的元素是上一行对应位置和前一个位置的和。def generate_pascal_triangle(n): triangle [] for row_num in range(n): # 每一行都是一个列表 row [None for _ in range(row_num 1)] # 首尾元素为1 row[0], row[-1] 1, 1 # 计算中间元素 for j in range(1, len(row) - 1): row[j] triangle[row_num - 1][j - 1] triangle[row_num - 1][j] triangle.append(row) return triangle11.2 利用Python的列表生成式与zip技巧有一种非常巧妙的Python式写法利用上一行来生成下一行def generate_pascal_triangle_pythonic(n): triangle [] for _ in range(n): # 当前行基于上一行生成 # 每一行可以看作是 [1] [上一行相邻两元素之和] [1] # 对于第一行我们定义上一行为[] row [1] if triangle: # 如果不是第一行 last_row triangle[-1] # 计算相邻两元素之和 row.extend([last_row[i] last_row[i1] for i in range(len(last_row)-1)]) row.append(1) triangle.append(row) return triangle或者更紧凑地利用zip配对上一行的元素def generate_pascal_triangle_zip(n): triangle [[1]] for _ in range(1, n): prev_row triangle[-1] # 将prev_row和它自身偏移一位进行zip得到相邻元素对 new_row [1] [a b for a, b in zip(prev_row, prev_row[1:])] [1] triangle.append(new_row) return trianglezip(prev_row, prev_row[1:])会生成形如[(prev_row[0], prev_row[1]), (prev_row[1], prev_row[2]), ...]的元组对正好是计算下一行中间元素所需的相邻两数。一个关键陷阱列表的引用在尝试用row [1] * (row_num1)初始化一行然后修改中间元素时如果后续操作不当可能会因为列表的引用特性导致错误。例如# 错误示范列表乘法创建的是对同一对象的引用对于可变对象 triangle [[1] * 3] * 3 # 这创建了三个对同一个列表的引用 triangle[0][0] 100 # 你会发现三行的第一个元素都变成了100正确初始化二维列表应使用列表推导式[[0 for _ in range(cols)] for _ in range(rows)]。杨辉三角的变体与应用 杨辉三角不仅是一个数学图形它的每一行对应二项式系数在组合数学中应用广泛。理解其生成过程有助于加深对动态规划、列表操作和Python中zip、列表推导式等高级用法的理解。在写这道题时重点体会如何利用已知的上一行数据高效地推导出下一行这是动态规划思想的雏形。