简介：这份资源是面向华为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:T+1]。这套模板的好处是无论输入是一行还是多行，你都能用同一套逻辑去拆，不用每道题重新想怎么读。

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, left+1, 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 到 nums1，nums1 有效长度 m，nums2 长度 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[:j+1] = nums2[:j+1]

逻辑说明：从后往前比较，把较大的放到nums1末尾。k始终指向当前待填位置。循环结束后如果nums2还有剩余，直接切片赋值过去；如果nums1有剩余，不用动，因为它们本来就在正确位置。

参数说明：m和n是有效元素个数，不是数组长度。nums1的实际长度是m+n，后面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"], input=inp, capture_output=True, text=True) r2 = subprocess.run([sys.executable, "fast.py"], input=inp, capture_output=True, text=True) if r1.stdout.strip() != r2.stdout.strip(): print("发现差异！输入：") print(inp) print("暴力输出：", r1.stdout) print("优化输出：", r2.stdout) break else: print("500 组随机测试全部通过")

逻辑说明：subprocess.run分别执行两个脚本，把生成的输入通过input参数传进去。capture_output=True捕获标准输出，text=True让返回值是字符串而不是字节。循环 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", file=sys.stderr) return result

注意计时输出要写到sys.stderr，不要混进stdout，否则会影响判题结果。通过分段计时，你能快速判断是排序慢、循环慢还是输入读取慢。如果排序占了大头，考虑用计数排序或桶排序替代；如果循环慢，检查是否有重复计算可以提到循环外。

5.3 考场习惯：先写注释再写代码

最后说一个不是技术但比技术更重要的习惯。我见过太多人考场上一上来就敲代码，写到一半发现思路错了，删了重来，时间全浪费在返工上。从那以后我每次拿到题目，都强制自己在草稿纸上写三行注释：输入是什么、输出是什么、核心步骤分几步。然后再把这三行注释抄到代码里，每步下面填实现。这样即使中途卡住，也能清楚知道自己在哪一步，不会全局崩盘。希望这套题解和这些习惯，能帮你在机试里少走点弯路。

本文还有配套的精品资源，点击获取