简介西北工业大学“人工智能程序设计”课程的Python NOJ在线评测源代码合集面向正在学习Python与算法基础、需要完成NOJ题目的在校学生。压缩包内共有61个文件包括60个.py源程序和1张说明图片整体仅82KB便于下载与查阅。代码题目覆盖面较广从整型运算、字符串处理、列表与元组、函数与Lambda表达式到斐波那契数列、水仙花数、编辑距离、循环队列、有序链表合并等经典算法与数据结构问题还包含装饰器使用、BMI指数计算、每日温度等贴近实际的小任务。目前已有430人学习下载。通过研读并运行这些源码可以对照每道题的解题思路、边界处理和代码风格有效提升用Python解决人工智能及一般编程问题的能力也可作为NOJ刷题与课程复习的参考题库。1. 从“输出菱形”到“编辑距离”一份西工大NOJ题解的知识跨度拆开这套资源之前我先扫了一遍文件名列表原以为是几个课程设计的拼接结果看到的是从int(input())一路写到编辑距离和前缀和的完整梯度。60 个.py文件编号按照题目难度线性排布前 20 个集中在输入输出、类型转换、分支循环中间 20 个覆盖字符串处理、列表操作、函数式编程最后 20 个直接落到栈、队列、链表、动态规划上。这套东西的价值不在于某个题的答案而在于它把“人工智能程序设计”的前置编程基础拆成了可逐题验收的清单——每道题对应一个语法点或一类算法思维。对于正在刷西工大NOJ的学生它是现成的参考答案对于想系统过一遍 Python 基础语法和常见算法套路的人它是一份按难度组织的练习地图。2. 输入输出与格式化NOJ评测的“门面功夫”NOJ 这类在线评测系统的判题逻辑很简单跑你的程序喂标准输入比对标准输出。这意味着 IO 写不对算法再对也是零分。这套资源里前几道题恰好把 Python 的输入输出模型讲透了。2.1 读入三件套map、split、input 的配合6.整数运算.py是典型的入门题要求读入两个整数输出加减乘除结果。最常见的写法是把读入和类型转换合并成一行a, b map(int, input().split()) print(a b) print(a - b) print(a * b) print(a // b, a % b)input()一次读一行返回字符串.split()默认按任意空白字符空格、制表符、换行切分返回字符串列表map(int, ...)把列表里每个元素逐个转成int再解包给a、b。print默认在行尾加换行所以多个输出可以直接分开写。如果输入规模变大比如30.逆时针原地旋转图像.py这类要读矩阵的题input()逐行读的效率会偏低。我一般换成import sys data list(map(int, sys.stdin.buffer.read().split()))这里read()把整个标准输入一次读完再统一split()和转换省掉了逐行调用的开销。buffer返回字节流比文本流快一截。小数据量看不出差别但 NOJ 某些题目会把输入卡到 1e6 行以上这时 IO 就是性能瓶颈。2.2 进制转换的两种写法内置函数与格式说明符3.二进制八进制和十六进制.py要求转换进制。刚学 Python 的人最容易写成n int(input()) print(bin(n)[2:], oct(n)[2:], hex(n)[2:])bin()、oct()、hex()返回带前缀的字符串分别是0b、0o、0x所以要切片去掉前缀。这个写法对正数没问题但负数会返回-0b101这种形式切片后变成-101看起来对其实前缀处理是拼凑的。更干净的做法是用内置格式说明符n int(input()) print(f{n:b} {n:o} {n:x})这两种方式在本题输出上是一致的区别体现在负数和大整数场景。format(n, b)的语义是“把这个整数的二进制表示输出”不会掺入前缀bin(n)的语义是“给出这个整数的二进制字面量”前缀是它的一部分。建议统一用格式说明符。格式说明符含义示例n26:b二进制11010:o八进制32:d十进制26:x十六进制小写1a:X十六进制大写1A:5d右对齐宽度 526宽度和对齐在2.动态宽度.py这类输出图案的题目里非常关键。比如要输出一个宽度可变的直角三角形可以写成f{* * i:5}这里的5表示左补空格到 5 个字符宽度把格式化的活交给字符串本身而不是手动拼空格。2.3 split() 与 split( ) 的区别一个被单独截图的知识点这套资源里有一个图片文件叫split()和split( )的区别.png说明老师也认为这是高频易错点。两者行为差异很大s a b c # 连续多个空格 print(s.split()) # [a, b, c] print(s.split( )) # [a, , b, , , c]无参split()会按任意连续的空白字符切分并且自动丢弃空串split( )则严格按单个空格切分连续空格之间会切出空字符串。8.字符串处理.py这类题如果输入里混入了制表符或末尾换行用split( )解析出来的列表里会莫名多出空串后续下标访问全部错位。判断到底用哪个看题目对“分隔符”的定义如果题目说“以空格分隔”输入又是人工键入的直接split()最安全如果要求保留空字段比如 CSV 风格的解析才需要显式指定分隔符。2.4 类型转换的隐患int(3.0) 为什么报错11.类型转换.py里最常见的坑是拿int()去转浮点数字符串# 错误 print(int(3.0)) # ValueError # 正确 print(int(float(3.0))) # 3 print(float(3.14)) # 3.14int()的入参是字符串时要求它本身是整数字面量小数点和科学计数法都不接受。int(3.9)这种从浮点数转整数的操作则直接截断小数部分不是四舍五入。NOJ 里“百分制转五分制”这类题15.百分制成绩转换五分制.py边界判断最好先用浮点数算完再转回整数避免整数除法把 89.5 直接砍成 89导致档位判错。提示涉及四舍五入时不要依赖int(x 0.5)用round()或Decimal前者是银行家舍入.5 可能舍向偶数后者可指定舍入模式。3. 字符串与数学逻辑从回文判断到罗马数字字符串处理是这套资源的中坚部分。题目本身不复杂但每种解法都能牵引出一个基础算法思维切片、双指针、查表、条件合并。3.1 回文判断的三种写法切片、双指针与 all()56.判断回文字符串.py看起来只需要一行s input().strip() print(YES if s s[::-1] else NO)切片反转最直观但不是所有场景都适用。如果题目要求原地判断且不产生新字符串或者字符串长到内存受限双指针更稳def is_palindrome(s: str) - bool: left, right 0, len(s) - 1 while left right: if s[left] ! s[right]: return False left 1 right - 1 return True双指针每次对比一对首尾字符遇到不等直接返回平均比切片少遍历一半。对纯语法练习第三种写法值得一提print(all(s[i] s[~i] for i in range(len(s) // 2)))~i是位运算取反等价于-i - 1对正索引i来说得到的是从尾部数的对称位置。all()会在遇到第一个False时短路本质上和双指针的退出条件一致。3.2 罗马数字转换贪心表和减法规则10.罗马数字.py要求整数转罗马数字。这个题的常规思路是维护一张“值到符号”的映射表每次都取不超过当前数的最大符号这种贪心策略在罗马数字规则下是完备的def int_to_roman(num: int) - str: table [ (1000, M), (900, CM), (500, D), (400, CD), (100, C), (90, XC), (50, L), (40, XL), (10, X), (9, IX), (5, V), (4, IV), (1, I), ] res [] for value, symbol in table: if num value: count, num divmod(num, value) res.append(symbol * count) return .join(res)注意table必须从大到小排列且把900、400、90、40、9、4这些减法形式显式写进表里否则按1000→500→100→50→10→5→1的简化表贪心1994 会拼成MDCCCCLXXXXIV不符合规范。divmod(num, value)同时拿到商和余数商决定符号重复几次余数进入下一轮循环。3.3 日期与素数闰年判断和累加优化14.今年多少天.py的输入是年月日输出它是这一年的第几天。核心只有闰年判断def is_leap(y: int) - bool: return (y % 4 0 and y % 100 ! 0) or (y % 400 0)闰年的充要条件是“能被 4 整除但不能被 100 整除或者能被 400 整除”这个条件表达式的顺序不能反y % 400 0本身已经覆盖了能被 400 整除的世纪年。累加天数直接用sum加days[:month-1]别手写循环。26.100~200素数累加求和.py可以直接逐个判断total sum(x for x in range(100, 201) if all(x % i for i in range(2, int(x ** 0.5) 1)))判断素数只需要试除到sqrt(x)。这里的all(x % i for i in ...)表示“对所有 ix 都不能被整除”x % i为 0 时该元素为假值all返回False。3.4 字符统计与大小写转换API 和 Counter28.字符统计.py要求统计字母、数字、空格等类别数量。逐字符判断可以但用str.isalpha()、str.isdigit()、str.isspace()这些内置判定方法更少出错。44.转换大小写.py注意str.swapcase()会把大写转小写、小写转大写而str.lower()和str.upper()只做单向转换。如果题目要求的“转换大小写”是大写变小写、小写变大写三者要分清。统计字符频率时我习惯用collections.Counterfrom collections import Counter freq Counter(s)Counter底层是dict支持freq[a]取值还能直接调freq.most_common(3)取频率最高的前三个比手写字典再排序干净得多。4. 列表、数组与数据结构把“数据结构”落到 Python 语法资源中段有大量数组类题目表面上考语法实际上在训练两种能力一是双指针这种原地操作技巧二是用 Python 内置类型模拟内存结构的能力。4.1 有序数组去重快慢指针与 in-place 修改54.有序数组去重.py要求原地去重并返回新长度这是 LeetCode 26 的原题。Python 里list(set(nums))能去重但会打乱顺序且不满足“原地”约束。标准解法是快慢指针def dedup(nums: list) - int: if not nums: return 0 slow 0 for fast in range(1, len(nums)): if nums[fast] ! nums[slow]: slow 1 nums[slow] nums[fast] return slow 1fast负责扫描slow指向最后一个不重复元素的位置。遇到新值时先移动slow再把新值写进去。这个技巧在“集群数”51.集群数.py和“每日温度”53.每日温度.py里都有变体前者是并查集或 BFS 的集群计数后者是单调栈但指针思想一脉相承。4.2 合并区间先排序再贪心38.合并区间.py的输入是一堆[start, end]要求合并重叠区间。常规套路是先按起点排序再依次合并def merge(intervals: list) - list: intervals.sort(keylambda x: x[0]) res [] for l, r in intervals: if not res or res[-1][1] l: res.append([l, r]) else: res[-1][1] max(res[-1][1], r) return res排序保证了后续遍历时新区间的起点一定不小于上一区间的起点所以合并时只需要看res最后一个区间的终点是否覆盖当前起点。覆盖则扩展到最大终点不覆盖则新开一段。sort(keylambda x: x[0])指定按子列表第一个元素排序这是 Python 排序最常用的参数形式。4.3 栈与循环队列用 list 模拟线性结构47.实现栈.py可以直接用list的append和popclass Stack: def __init__(self): self.data [] def push(self, x): self.data.append(x) def pop(self): return self.data.pop() def top(self): return self.data[-1] def empty(self): return not self.datalist.pop()默认弹出末尾元素复杂度 O(1)这就是栈顶。55.数组实现循环队列.py稍微绕一点要用头部指针和取模运算模拟环形缓冲区class MyCircularQueue: def __init__(self, k: int): self.q [0] * k self.head self.tail 0 self.size 0 self.cap k def push(self, x: int) - bool: if self.size self.cap: return False self.q[self.tail] x self.tail (self.tail 1) % self.cap self.size 1 return True def pop(self) - bool: if self.size 0: return False self.head (self.head 1) % self.cap self.size - 1 return True循环队列的核心在(self.tail 1) % self.cap取模让索引在到达数组末尾时绕回开头。size用于区分“空”和“满”因为只靠head tail无法判断是哪种状态。数据结构Python 实现插入复杂度删除复杂度适用场景栈list.append / popO(1)O(1)括号匹配、递归转迭代队列collections.dequeO(1)O(1)BFS、滑动窗口循环队列定长 list 取模指针O(1)O(1)固定容量的缓冲在 NOJ 的判题环境里deque比自定义循环队列的可读性更好但“数组模拟队列”这道题本身考的就是取模绕回的原理实现一次有助于理解 BFS 里队列的深层结构。4.4 合并两个有序链表类定义与迭代法60.合并两个有序链表.py是从数组跳到链表的第一个题。链表节点需要自己定义class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def merge_two_lists(l1: ListNode, l2: ListNode) - ListNode: dummy ListNode() cur dummy while l1 and l2: if l1.val l2.val: cur.next, l1 l1, l1.next else: cur.next, l2 l2, l2.next cur cur.next cur.next l1 or l2 return dummy.nextdummy哨兵节点是链表题里最常见的省事技巧避免处理头节点的特判。cur.next, l1 l1, l1.next这一步同时完成“挂上新节点”和“移动指针”利用 Python 的多元赋值先算右值再统一赋值的特性不会出现先用旧值后用新值的错乱。最后cur.next l1 or l2把剩余那段直接接上因为链表本身有序剩下的整体就是答案的一部分。5. Lambda、闭包与装饰器AI 课程里隐性的函数式训练如果只看文件列表这章容易被当成“编程技巧选做题”跳过。但实际上“五十个题目里塞了六个函数式编程题”这件事本身说明课程在刻意铺垫人工智能课程后面讲损失函数、梯度、评估指标时经常要把函数作为参数传来传去lambda、闭包、装饰器就是 Python 里实现“函数是一等公民”的手段。5.1 Sort 与 Lambda多关键字排序34.Sort与Lambda函数.py和33.使用lambda函数.py的核心是sorted的key参数students [ (zhang, 88), (li, 95), (wang, 88), ] students.sort(keylambda x: (-x[1], x[0]))这里key接收一个函数函数对每个元素返回一个用于比较的值。元组作为返回值时Python 会依次比较元组里的每一项所以(-x[1], x[0])实现“先按成绩降序成绩相同按姓名升序”。注意成绩取负值是为了把升序变成降序这是不引入reverseTrue时控制多关键字方向的标准技巧。lambda适合写这种一行的简单表达式。逻辑一旦超过一个条件我建议用def定义具名函数方便单元测试也方便读懂def sort_key(stu): return (-stu[1], stu[0])5.2 闭包实现计数器nonlocal 的用法35.闭包函数实现计数器.py考察的是闭包对变量的捕获。闭包可以记住定义时的环境但默认只能读取外层变量修改要显式声明nonlocaldef make_counter(): count 0 def counter(): nonlocal count count 1 return count return counter c1 make_counter() print(c1()) # 1 print(c1()) # 2count是make_counter的局部变量理论上make_counter返回后它就应该被回收。但闭包counter持有了它的引用所以count的生命周期被延长了。nonlocal count告诉解释器“这个变量不是局部变量去外层函数找”。如果不写nonlocalcount 1会被当成创建新的局部变量运行时报UnboundLocalError。一个容易混淆的误解是“函数内可以读外层变量所以不加也行”。读确实可以比如只打印不修改。但一旦出现赋值语句Python 的编译规则就把它视为局部变量声明必须用nonlocal显式解除。5.3 装饰器给函数叠加行为50.1装饰器的使用.py要求写装饰器。装饰器本质是一个接收函数、返回函数的函数import time from functools import wraps def timer(func): wraps(func) def wrapper(*args, **kwargs): start time.perf_counter() result func(*args, **kwargs) print(f{func.__name__} 耗时 {time.perf_counter() - start:.6f}s) return result return wrapper timer def hard_work(): total sum(range(10**6)) return totaltimer是hard_work timer(hard_work)的语法糖。wrapper用*args, **kwargs接收任意参数再透传给原函数保证装饰器不关心被装饰函数的签名。functools.wraps把原函数的__name__、__doc__等元信息复制到wrapper上否则装饰后函数名会变成wrapper对调试和日志都不友好。AI 课程里的实际场景是给模型训练函数的每个 epoch 加计时或者给数据加载函数加重试逻辑这个模式几乎原样复用。装饰器的可组合性多层装饰和参数化装饰器工厂是从这道题往后延伸的两个方向。5.4 all() 与 any()判断逻辑的向量化9.all()和any()函数的使用.py是纯语法题但实际价值在于替代循环里的布尔标记位。判断一个列表是否都为正数nums [1, 2, -3, 4] print(all(x 0 for x in nums)) # False print(any(x 0 for x in nums)) # Trueall和any都从左到右遍历遇到能确定结果的值立即短路。all遇到第一个假值返回Falseany遇到第一个真值返回True所以它们的时间复杂度是 O(最短路径) 而不是 O(全量)。这在处理大列表时比先用列表推导式生成中间列表再判断更省内存。6. 进阶题目与自查方法前缀和、编辑距离与本地验证最后这批题开始有信息量了。它们不是考察 Python 语法而是考察算法设计。这里挑两道最有代表性的展开顺便给出脱离 NOJ 后自己验证代码正确性的方法。6.1 和为 K 的子数组前缀和加哈希表59.和为K的子数组.py要求统计连续子数组中和为K的个数。暴力枚举所有i, j组合是 O(n^2)n 到 1e5 就会超时。标准做法是维护前缀和并用哈希表记录每个前缀和出现的次数from collections import defaultdict def subarray_sum(nums: list, k: int) - int: prefix_count defaultdict(int) prefix_count[0] 1 ans, cur 0, 0 for x in nums: cur x ans prefix_count.get(cur - k, 0) prefix_count[cur] 1 return ans设prefix[i]为前 i 个元素的和子数组(j, i]的和是prefix[i] - prefix[j]令其等于 K就变成判断prefix[j] prefix[i] - K是否在之前出现过。prefix_count里存的是“这个前缀和出现过几次”。初始化prefix_count[0] 1是为了处理“从第 0 个元素开始”的子数组——当cur恰好等于 K 时需要能从哈希表里查到 0。注意遍历过程中边算边存保证每次查到的是当前下标之前的前缀和不会重复计数。这道题“为什么不能用双指针”值得多想一步数组里可能同时存在正数和负数窗口的单调性被破坏左指针右移并不能保证窗口和单调变化所以只能回退到前缀和。6.2 编辑距离二维 DP 的状态转移36.Python的编辑距离.py是经典的字符串 DP。dp[i][j]表示word1[:i]变成word2[:j]的最小编辑次数三种操作对应三个转移方向def min_distance(w1: str, w2: str) - int: m, n len(w1), len(w2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(m 1): dp[i][0] i for j in range(n 1): dp[0][j] j for i in range(1, m 1): for j in range(1, n 1): if w1[i - 1] w2[j - 1]: dp[i][j] dp[i - 1][j - 1] else: dp[i][j] min( dp[i - 1][j] 1, # 删除 w1[i-1] dp[i][j - 1] 1, # 插入 w2[j-1] dp[i - 1][j - 1] 1 # 替换 ) return dp[m][n]初始化那两行循环对应空字符串的编辑代价从一个空串变成 j 个字符需要 j 次插入。状态转移时若当前字符相等直接继承左上角结果不产生新操作不等时取删除、插入、替换三种方案的最小值加 1。这里的“删除”“插入”是站在w1视角描述的逻辑上对称怎么理解都行。空间上这个二维表可以压缩成一维数组滚动更新但 NOJ 的评测通常不会卡这道题的内存二维 DP 的写法更直白、更容易和状态转移图对应。6.3 本地自测三件套边界值、随机对拍与复杂度估算脱离评测系统之后自己验证代码要盯三个层面。第一是边界值比如14.今年多少天.py一定要测2024-02-29闰年二月末和1900-02-28整百年不是闰年55.数组实现循环队列.py的边界是k1时连续 push/pop 的轮转。第二是随机对拍写一个暴力解和优化解用随机数据反复比对这是验证算法正确性的通用做法import random def brute(nums, k): ans 0 for i in range(len(nums)): s 0 for j in range(i, len(nums)): s nums[j] if s k: ans 1 return ans def stress(): for _ in range(10000): nums [random.randint(-10, 10) for _ in range(random.randint(1, 30))] k random.randint(-10, 10) if subarray_sum(nums, k) ! brute(nums, k): print(mismatch:, nums, k) return stress()对拍程序的本质是“用复杂度换正确性”暴力解慢但逻辑绝对直白优化解快但容易在边界上出错两者输出不一致就说明某一边有 bug。第三是估算复杂度刷到53.每日温度.py这类题时如果解法是双重循环而 n 是 1e5预判就会超时应当主动转向单调栈。VSCode 里把 Python 解释器指到项目的虚拟环境CtrlShiftP选Python: Select Interpreter给subarray_sum这类函数打上断点单步看prefix_count在重复元素出现时的取值变化比在代码里写print更直观。对拍覆盖正确性断点帮理解每一步状态这套组合应对 NOJ 的隐藏测例足够了。本文还有配套的精品资源点击获取