简介这份资源是面向华为OD机试备考者与Python算法学习者的题解代码合集聚焦在线编程面试中的高频算法与数据结构挑战帮助读者在实战中打磨Python解题能力。压缩包共106个文件以103个py脚本为主辅以3个txt说明文件整体约59KB轻量便于本地运行与逐题调试。内容覆盖IP地址识别、01背包动态规划、扑克牌大小比较、素数伴侣、数字转英语、索引统计等典型题型并穿插输出格式化、深拷贝、排序交换等基础技巧可当作刷题索引与思路参照。目前已有1592人学习下载适合希望系统梳理算法套路、积累可复用代码模板的初中级开发者通过对照实现理解状态转移、字符串处理与自定义排序等关键知识点。1. 从一道字符串压缩题说起这套 Python 题解到底能帮你省下多少时间去年帮一个学弟复盘机试他卡在一道“字符串压缩与解压”上整整四十分钟最后暴力模拟过了样例但隐藏用例全挂。事后我翻了下他刷的题库发现他缺的不是算法能力而是对这类机试题目输入输出格式的敏感度——题目要求把aaabbc压成a3b2c1但边界条件里藏着空串、单字符、连续超过 9 个相同字符时数字占位的问题。这套 Python 题解资源核心价值就在于把这类“看起来会做、写出来就错”的机试高频题型按输入解析、核心逻辑、边界处理、输出格式四个环节拆成了可直接复用的代码模板。它适合正在准备机试的在校生、想转岗练手感的开发者以及需要快速回顾常见算法套路的人。整套代码以 Python 3 编写覆盖字符串、数组、动态规划、贪心、模拟等机试出现频率最高的几类题型每个文件独立可运行不依赖第三方库。2. 环境准备与代码结构把题解跑起来需要几步2.1 Python 版本选择与依赖确认这套题解对 Python 版本的要求并不苛刻但有一个容易被忽略的细节部分题目用到了math.gcd和functools.lru_cache这两个在 Python 3.5 和 3.8 之后才有稳定行为。我一般建议直接用 Python 3.8 以上避免在dict有序性和math模块上翻车。如果你机器上有多个版本用python3 --version确认一下别用系统自带的 Python 2 去跑否则print语句和整除行为会让你怀疑人生。依赖方面整套代码只用了标准库没有numpy、pandas这类重型包。这意味着你不需要配虚拟环境直接全局跑就行。但如果你习惯用venv创建一个干净环境也就两条命令的事python3 -m venv od_env source od_env/bin/activate # Windows 用 od_env\Scripts\activate激活后不需要pip install任何东西直接进代码目录就能执行。这一点对机试场景很关键——真实考试环境往往不允许你装包平时练习就养成只用标准库的习惯上了考场才不会因为import报错而慌神。2.2 目录组织与单题运行方式拿到代码包后你会看到类似这样的结构根目录下按题型分了string/、array/、dp/、greedy/、simulation/几个文件夹每个文件夹里是独立的.py文件文件名就是题目缩写比如string/compress_string.py。每个文件都遵循同一套骨架顶部是sys.stdin读取中间是solve()函数底部是if __name__ __main__:调用。运行单题的方式有两种。第一种是直接喂输入echo aaabbc | python3 string/compress_string.py第二种是在文件里改sys.stdin为io.StringIO做本地调试这样不用每次都在终端敲输入。我一般会在调试阶段临时加一行import sys, io sys.stdin io.StringIO(aaabbc\n)这样在 IDE 里按 F5 就能跑省去终端切换的麻烦。注意调试完要把这行删掉或注释掉否则提交到在线判题系统时会因为输入被劫持而 WA。2.3 输入解析的通用模式机试题最坑的地方往往不是算法本身而是输入格式。有的题目一行给一个整数有的给一行空格分隔的数组有的给多行直到 EOF。这套题解里统一用了一个read_input()辅助函数来处理import sys def read_input(): 读取全部输入并按行拆分去除首尾空白 data sys.stdin.read().strip() if not data: return [] return data.split(\n) def parse_ints(line): 把一行空格分隔的字符串转成整数列表 return list(map(int, line.split()))逻辑说明sys.stdin.read()一次性读完所有输入避免input()在循环里反复调用导致的性能问题。strip()去掉末尾换行防止空行被当成有效数据。parse_ints里用map而不是列表推导在数据量大时略快一点但差异不大主要是写法统一。参数说明如果你的题目输入是单行多组数据比如第一行是测试用例数T后面跟T行那就在read_input()之后取data[0]作为T然后循环data[1:T1]。这套模板的好处是无论输入是一行还是多行你都能用同一套逻辑去拆不用每道题重新想怎么读。3. 高频题型拆解字符串、数组与动态规划的代码模板3.1 字符串处理压缩、展开与回文判断字符串题在机试里出现频率极高因为出题成本低、边界条件多。以压缩题为例题目要求把连续重复字符压成“字符次数”的形式但次数为 1 时省略数字。这套代码里的实现是这样的def compress(s): 字符串压缩aaabbc - a3b2c if not s: return res [] count 1 for i in range(1, len(s)): if s[i] s[i-1]: count 1 else: res.append(s[i-1] (str(count) if count 1 else )) count 1 # 处理最后一组 res.append(s[-1] (str(count) if count 1 else )) return .join(res)逻辑说明用res列表收集结果而不是字符串拼接是因为 Python 里字符串不可变循环里会反复创建新对象数据量大时性能差距明显。count 1的判断处理了“单字符不写数字”的规则。循环结束后别忘了最后一组这是新手最容易漏的地方。参数说明输入s是纯字母字符串不含空格和数字。如果题目允许数字出现在原串里那压缩后的解析就会产生歧义比如a12到底是“1 个 a 后面跟 2”还是“12 个 a”。遇到这种题通常题目会保证原串只含字母或者要求用特殊分隔符读题时务必确认。回文判断的变种也很多比如“最多删除一个字符能否成为回文”。这套代码里用了双指针加一次跳过机会def valid_palindrome(s): 最多删一个字符判断能否成回文 left, right 0, len(s) - 1 while left right: if s[left] ! s[right]: # 尝试跳过左边或右边 return is_pal(s, left1, right) or is_pal(s, left, right-1) left 1 right - 1 return True def is_pal(s, l, r): while l r: if s[l] ! s[r]: return False l 1 r - 1 return True这里的关键是遇到不匹配时只给一次“后悔药”——要么跳过左指针要么跳过右指针然后检查剩余子串是否回文。注意is_pal是左闭右闭区间传参时别搞错边界。3.2 数组与双指针去重、合并与滑动窗口数组题的核心套路就那几个排序后双指针、哈希表计数、滑动窗口。这套代码里有一道“合并两个有序数组”的题要求原地合并到第一个数组里。常见做法是从后往前填避免覆盖def merge_sorted(nums1, m, nums2, n): 合并 nums2 到 nums1nums1 有效长度 mnums2 长度 n i, j, k m - 1, n - 1, m n - 1 while i 0 and j 0: if nums1[i] nums2[j]: nums1[k] nums1[i] i - 1 else: nums1[k] nums2[j] j - 1 k - 1 # nums2 剩余的直接拷贝 nums1[:j1] nums2[:j1]逻辑说明从后往前比较把较大的放到nums1末尾。k始终指向当前待填位置。循环结束后如果nums2还有剩余直接切片赋值过去如果nums1有剩余不用动因为它们本来就在正确位置。参数说明m和n是有效元素个数不是数组长度。nums1的实际长度是mn后面n个位置是占位用的。这个题在机试里经常改条件比如改成“合并后去重”或者“合并到新数组”核心思路不变只是输出位置变了。滑动窗口的模板更通用比如“最长无重复子串”def length_of_longest_substring(s): 最长无重复字符子串长度 last_seen {} left 0 max_len 0 for right, ch in enumerate(s): if ch in last_seen and last_seen[ch] left: left last_seen[ch] 1 last_seen[ch] right max_len max(max_len, right - left 1) return max_len这里last_seen记录字符最后出现的位置left只在遇到重复且重复位置在当前窗口内时才跳。注意last_seen[ch] left这个条件如果重复字符在窗口外不影响当前窗口不用跳。3.3 动态规划从背包到最长递增子序列动态规划是机试的分水岭会的人觉得套路固定不会的人连状态定义都写不出来。这套代码里 DP 部分覆盖了 0-1 背包、完全背包、LIS、LCS 这几个经典模型。以 0-1 背包为例def knapsack(weights, values, capacity): 0-1 背包每个物品只能选一次 n len(weights) dp [0] * (capacity 1) for i in range(n): # 倒序遍历保证每个物品只被选一次 for w in range(capacity, weights[i] - 1, -1): dp[w] max(dp[w], dp[w - weights[i]] values[i]) return dp[capacity]逻辑说明一维 DP 数组里dp[w]表示容量为w时的最大价值。外层循环遍历物品内层倒序遍历容量这样dp[w - weights[i]]用的是上一轮没选当前物品的状态避免同一物品被重复选。如果内层正序遍历就变成了完全背包。参数说明weights和values长度一致capacity是背包总容量。如果题目要求“恰好装满”初始化时dp[0]0其余为负无穷如果只求“不超过容量”全部初始化为 0 即可。这个区别在机试里经常考写之前先确认题意。LIS 的 O(n log n) 解法也值得记一下import bisect def length_of_lis(nums): 最长严格递增子序列长度 tails [] for x in nums: pos bisect.bisect_left(tails, x) if pos len(tails): tails.append(x) else: tails[pos] x return len(tails)tails数组维护的是当前长度下最小的结尾元素bisect_left找到第一个大于等于x的位置替换。注意这里是严格递增如果题目允许非递减把bisect_left换成bisect_right。4. 避坑与排查机试代码最容易翻车的五个地方4.1 输入读取方式不匹配导致全 WA现象本地跑样例没问题提交后一个用例都过不了。原因通常是题目输入是多行但你用了input()只读了一行或者题目是单行多组数据你却按行去拆。解决方法是先用sys.stdin.read()把全部输入拿到手再根据题目描述决定怎么切分。如果不确定打印一下repr(data)看看实际读到了什么。4.2 边界条件漏判空串、单元素、全相同现象样例过了隐藏用例挂。原因多半是没处理空输入或单元素。比如字符串压缩题空串直接返回空串单字符返回原字符。数组题里len(nums) 0或 1时很多循环逻辑会直接跳过导致返回默认值。解决方法是写完核心逻辑后手动构造、a、[1]、[1,1,1]这几组输入跑一遍。4.3 递归深度超限与记忆化遗漏现象树或图相关的题报RecursionError。原因是 Python 默认递归深度 1000题目数据规模可能到 10^4。解决方法是加sys.setrecursionlimit(10000)或者改写成迭代。另一个常见问题是写了递归但忘了加lru_cache导致重复子问题指数级膨胀小数据能过大数据超时。4.4 浮点数比较与整除陷阱现象结果差一点或者整数除法得到浮点数。原因是 Python 的/永远返回浮点数而机试通常要求整数输出。解决方法是整除用//取余用%。浮点数比较不要用用abs(a - b) 1e-9。如果题目要求保留小数注意round的银行家舍入规则必要时用decimal模块。4.5 输出格式多空格少换行现象逻辑全对但判题系统说格式错误。原因是输出多了空格、少了换行或者列表打印带了方括号。解决方法是把结果转成字符串后strip()一下列表输出用 .join(map(str, res))不要直接print(res)。每道题提交前把样例输入输出复制到本地 diff 一下确认字符级一致。5. 进阶技巧用对拍和性能计时把代码磨到考场级别5.1 对拍脚本用暴力验证优化解机试里最怕的是“我觉得对但实际错”。对拍是解决这个问题的终极手段写一个暴力解法再写一个优化解法随机生成小规模输入比较两者输出。这套题解里我加了一个stress_test.py模板import random, subprocess, sys def gen_input(): 生成随机小规模输入 n random.randint(1, 8) return str(n) \n .join(str(random.randint(1, 20)) for _ in range(n)) for i in range(500): inp gen_input() r1 subprocess.run([sys.executable, brute.py], inputinp, capture_outputTrue, textTrue) r2 subprocess.run([sys.executable, fast.py], inputinp, capture_outputTrue, textTrue) if r1.stdout.strip() ! r2.stdout.strip(): print(发现差异输入) print(inp) print(暴力输出, r1.stdout) print(优化输出, r2.stdout) break else: print(500 组随机测试全部通过)逻辑说明subprocess.run分别执行两个脚本把生成的输入通过input参数传进去。capture_outputTrue捕获标准输出textTrue让返回值是字符串而不是字节。循环 500 次一旦发现输出不一致就打印输入和双方输出方便定位。参数说明gen_input里的数据规模要小一般n不超过 10数值范围不超过 20这样暴力解法不会超时。如果 500 组都过可以逐步放大规模再测。注意对拍只能验证“两个解法一致”不能证明优化解法一定对但能帮你排除绝大多数边界错误。5.2 性能计时找到隐藏的超时用例有些题逻辑正确但超时你需要知道瓶颈在哪。用time.perf_counter()给关键步骤打点import time def solve(nums): t0 time.perf_counter() # 步骤一排序 nums.sort() t1 time.perf_counter() # 步骤二双指针 left, right 0, len(nums) - 1 while left right: # 核心逻辑 left 1 right - 1 t2 time.perf_counter() print(f排序耗时{t1-t0:.4f}s双指针耗时{t2-t1:.4f}s, filesys.stderr) return result注意计时输出要写到sys.stderr不要混进stdout否则会影响判题结果。通过分段计时你能快速判断是排序慢、循环慢还是输入读取慢。如果排序占了大头考虑用计数排序或桶排序替代如果循环慢检查是否有重复计算可以提到循环外。5.3 考场习惯先写注释再写代码最后说一个不是技术但比技术更重要的习惯。我见过太多人考场上一上来就敲代码写到一半发现思路错了删了重来时间全浪费在返工上。从那以后我每次拿到题目都强制自己在草稿纸上写三行注释输入是什么、输出是什么、核心步骤分几步。然后再把这三行注释抄到代码里每步下面填实现。这样即使中途卡住也能清楚知道自己在哪一步不会全局崩盘。希望这套题解和这些习惯能帮你在机试里少走点弯路。本文还有配套的精品资源点击获取