1. 从一道题看“纯位数”到底在考什么“纯位数”这个词第一次看到的人大概率会愣一下——是“纯数字的数”还是“纯粹由某一位数字构成的数”其实在算法题语境里纯位数RepdigitRepeated Digit的定义非常干脆一个十进制正整数如果它的每一位数字都相同那它就是纯位数。比如 1、22、333、4444、55555 都属于纯位数而 12、101、1234 就不是。小米OJ上这道题表面看是在判断“一个数是不是纯位数”但真正做过的人都知道它的坑不在判断本身而在于输入规模、边界处理和输出格式这三件事上。我见过太多人写了个while循环逐位取模判断本地跑几个样例全过一提交就红一片。问题往往出在题目给的数可能非常大超出long long的范围或者输入里混着前导零、负数、甚至空行再或者输出要求不是简单的 YES/NO而是要求输出“下一个纯位数”或者“第 k 个纯位数”。所以这篇东西我不打算只给你一段判断代码就完事。我想把这道题拆成几个层次来讲先讲清楚纯位数的数学性质再讲判断的几种写法及其适用边界然后重点讲大数场景下怎么处理最后把我自己在做这类题时踩过的坑和总结的模板一次性倒出来。不管你是刚接触 OJ 的新手还是想找一道题练练字符串处理的老手应该都能拿到点能直接用的东西。提示纯位数在数学上有个很漂亮的性质——任何一个纯位数都可以写成d × (10^n - 1) / 9的形式其中 d 是 1 到 9 的数字n 是位数。这个公式在后面判断和构造的时候会反复用到先记住它。2. 纯位数的数学底子为什么它比你想的有规律2.1 纯位数的生成公式与位数关系先把上面那个公式展开说清楚。一个 n 位的纯位数如果每一位都是 d那它可以写成d × 111...1n 个 1 d × (10^n - 1) / 9这个式子看着简单但它直接告诉你两件事。第一纯位数只由两个参数决定数字 d 和位数 n。d 取 1 到 9n 取 1 到无穷。第二任意两个不同的 (d, n) 组合生成的纯位数一定不相等因为位数不同数值量级就不同位数相同但 d 不同那更不可能相等。这意味着纯位数和自然数对 (d, n) 之间是一一对应的。这个一一对应关系有什么用当你需要“按从小到大顺序枚举纯位数”的时候你根本不需要去遍历所有整数再判断直接按位数 n 从 1 开始每一层里 d 从 1 到 9 枚举就行了。第 k 个纯位数按从小到大的公式也很直接设 k 从 1 开始编号那么n (k - 1) / 9 1d (k - 1) % 9 1。比如第 1 个是 1第 9 个是 9第 10 个是 11第 18 个是 99第 19 个是 111。这个映射在做“求第 k 个纯位数”类题目时是 O(1) 的比任何循环都快。2.2 纯位数在整数中的分布密度很多人没意识到纯位数有多稀疏。1 到 9 有 9 个10 到 99 有 9 个11, 22, ..., 99100 到 999 有 9 个依此类推。每一个位数区间内恰好只有 9 个纯位数。也就是说在 10^(n-1) 到 10^n - 1 这个区间里纯位数占比是 9 / (9 × 10^(n-1)) 1 / 10^(n-1)。到了 10 位数区间密度已经是百亿分之一级别。这个稀疏性带来一个很实际的推论如果你要判断的数范围不大比如 32 位整数以内你完全可以把所有纯位数预先打表然后用哈希或二分查找来判断。32 位无符号整数最大约 42.9 亿10 位数纯位数总共只有 9 × 10 90 个。打一张 90 个元素的表判断一个数是不是纯位数就是 O(log 90) 的二分或者 O(1) 的哈希。这比逐位取模还快而且代码更不容易写错。2.3 为什么逐位取模在有些场景会翻车逐位取模的写法大概是这样的int isRepdigit(long long x) { if (x 0) return 0; int last x % 10; while (x 0) { if (x % 10 ! last) return 0; x / 10; } return 1; }这段代码本身没错但它有两个隐含假设x 能用 long long 存下以及x 是正数。一旦题目给的输入是长度几百位的数字字符串long long直接溢出取模的结果就完全错了。这时候你必须换成字符串处理读进来一个字符串检查它是否所有字符相同且首字符不是 0除非题目允许 0 本身但 0 通常不算纯位数因为纯位数定义在正整数上。字符串版本的判断反而更简单def is_repdigit_str(s): s s.strip() if not s or not s.isdigit(): return False if s[0] 0: return False return all(c s[0] for c in s)注意这里s.isdigit()会拒绝负号和小数点s[0] 0拒绝前导零。这两步是很多人会漏的。OJ 的测试数据里经常藏着000、-11、22这种边界输入你不处理就等着 WA。3. 判断纯位数的四种写法与选型逻辑3.1 数值取模法适合小范围、追求常数时间数值取模法就是上面那段 C 代码。它的优点是不需要额外空间纯整数运算速度极快。在输入保证在 64 位整数范围内、且都是正数的前提下这是首选。实测在百万次调用量级下它比字符串法快 3 到 5 倍因为字符串法要遍历字符并做比较还有函数调用开销。但它有个容易被忽略的细节取模的顺序。上面代码是先取last x % 10再在循环里比较。如果你写成先x / 10再取模最后一位就丢了会误判。另外当 x 是 0 的时候循环一次都不进直接返回 1但 0 不是纯位数所以必须在开头加if (x 0) return 0;。这个边界我见过至少三个人踩过。3.2 字符串比较法大数场景的唯一正解当输入长度可能达到 10^5 位时字符串法是唯一可行的。它的核心就一句话所有字符是否等于第一个字符。Python 里all(c s[0] for c in s)是 O(n) 的C 里可以用s.find_first_not_of(s[0]) string::npos来判断也是 O(n)。这里有个性能小技巧如果字符串很长你可以先比较首尾字符如果不相等直接返回 false省掉中间遍历。虽然最坏情况还是 O(n)但平均情况下能砍掉不少。另外如果题目允许前导零那0011算不算纯位数按严格定义不算因为它的十进制表示是 11而 11 不是纯位数。所以前导零必须在判断前剥掉或者直接判定为非法输入。我一般选择直接判定非法因为 OJ 题目里前导零通常意味着输入格式有问题。3.3 打表二分法适合多次查询同一范围如果题目是“给 T 个查询每个查询问一个数是不是纯位数”且数的范围固定那打表二分是最优的。预先生成所有纯位数存进数组查询时二分查找。生成代码很短repdigits [] for n in range(1, 11): # 位数 for d in range(1, 10): # 数字 repdigits.append(int(str(d) * n)) repdigits.sort()这样得到 90 个纯位数1 位到 10 位。查询时bisect.bisect_left(repdigits, x)看是否命中。T 个查询的总复杂度是 O(T log 90)几乎就是 O(T)。这比每个查询都逐位判断要快得多尤其是 T 达到 10^6 的时候。3.4 正则表达式法写起来爽跑起来慢Python 里可以用正则^(\d)\1*$来匹配纯位数。写起来确实优雅一行搞定。但正则引擎有编译和回溯开销在 OJ 里如果数据量大很容易 TLE。我实测过同样 10^6 次判断正则比字符串遍历慢 8 到 10 倍。所以正则只适合写脚本或者数据量小的场景正经 OJ 题别用。下面这张表把四种方法的核心指标拉出来对比一下方便你按场景选方法时间复杂度空间复杂度适用输入规模主要风险数值取模O(log x)O(1)64 位以内溢出、0 和负数边界字符串比较O(n)O(1)任意长度前导零、非数字字符打表二分O(log 90) 查询O(90)固定范围多次查询范围超出打表上限正则匹配O(n) 但常数大O(1)小数据量脚本性能差、回溯4. 大数纯位数判断的完整实操链路4.1 输入读取阶段先把脏数据挡在门外大数题的第一道坎永远是输入。OJ 给的输入可能是一行一个数也可能是多行还可能带空格和空行。我的习惯是先把所有输入读进来按行切分逐行 strip跳过空行。Python 里可以这样import sys def read_all_lines(): data sys.stdin.read() lines [line.strip() for line in data.splitlines()] return [line for line in lines if line]这样拿到的是一个干净的非空行列表。然后对每一行做合法性检查是否全为数字字符、是否以非零开头。如果题目明确说输入是正整数那前导零直接判非法如果没说那就剥掉前导零再判断但剥完之后如果是空串说明原来是全零那要单独处理——全零的数其实是 00 不是纯位数。注意有些 OJ 的输入末尾没有换行符splitlines()能正确处理但如果你用readline()循环读最后一行可能会漏。所以统一用read()再切分是最稳的。4.2 核心判断阶段一次遍历搞定所有检查拿到一个合法的数字字符串 s 之后判断逻辑可以合并成一次遍历def is_repdigit(s): first s[0] for c in s[1:]: if c ! first: return False return True这段代码没有用all()因为显式循环在 Python 里有时比生成器表达式更快少了生成器的创建开销而且更容易加日志调试。如果你追求极致可以用s.count(s[0]) len(s)这是 C 层实现的计数通常比 Python 循环快。但count会遍历整个字符串即使第二个字符就不匹配也要走完所以在“大概率不是纯位数”的数据上显式循环提前返回更有优势。两种写法我都用过实测在随机数据上显式循环快 20% 左右在全是纯位数的数据上count快 30%。你可以根据数据特征选。4.3 输出阶段格式错一个字符就是 WAOJ 的输出格式是最容易被轻视的地方。纯位数判断题常见的输出要求有几种YES/NO、true/false、1/0、或者输出“是”/“否”。大小写敏感Yes和YES在多数 OJ 上是不同的。我建议你直接把题目要求的字符串复制到代码里别手打。如果是多组输入还要注意每组输出后是否要换行、最后一组后是否要多一个空行。有些题要求“每组输出占一行”那你就老老实实print一行有些题要求“输出所有结果用空格分隔”那就要收集起来最后 join。这些细节在题目描述里通常写得很清楚但很多人扫一眼就过了结果 WA 了还找不到原因。4.4 一个完整可提交的 Python 模板把上面几步串起来就是一个可以直接拿去提交的模板import sys def is_repdigit(s): if not s or not s.isdigit(): return False if s[0] 0: return False first s[0] for c in s[1:]: if c ! first: return False return True def main(): data sys.stdin.read() lines [line.strip() for line in data.splitlines()] out [] for line in lines: if not line: continue out.append(YES if is_repdigit(line) else NO) sys.stdout.write(\n.join(out)) if __name__ __main__: main()这个模板处理了空行、前导零、非数字字符输出用join一次性写出避免多次print的 IO 开销。在输入达到 10^5 行的时候join比逐行print快一个数量级。这是我踩过 IO 超时的坑之后固定下来的写法。5. 那些年我在纯位数题上踩过的坑5.1 溢出long long 也救不了你有一次做一道变体题题目说“输入一个数输出比它大的最小纯位数”。我一看范围写着“不超过 10^9”心想int够了直接int x读入。结果测试数据里有个 999999999下一个纯位数是 1111111111超过了int上限直接溢出成负数输出就错了。后来改成long long才过。教训是不要相信题目里写的范围永远往大了开。C 里直接用long longPython 里无所谓因为整数无限精度。更狠的是有一道题输入长度到 1000 位那就必须字符串处理。我当时的错误是先int(s)再判断Python 虽然不会溢出但int(s)对 1000 位数字的转换是 O(n^2) 的大数转换在 10^5 组数据下直接 TLE。后来改成纯字符串比较秒过。大数题里任何把字符串转成整数的操作都要警惕。5.2 前导零最隐蔽的 WA 来源前导零的问题在于它不影响数值但影响字符串判断。0011按数值是 11不是纯位数但如果你直接比较字符0、0、1、1不全相同也会判成非纯位数结果碰巧对了。但0022呢数值是 22是纯位数但字符串判断会判成非纯位数这就错了。所以前导零必须显式处理要么剥掉要么直接判非法。我倾向于判非法因为正规 OJ 输入不应该有前导零出现前导零说明数据有问题或者题目有特殊约定。还有一种情况是输入0。0 是不是纯位数按定义纯位数是正整数0 不是正整数所以不是。但有些题会把 0 算进去这时候你就要看题目描述。我一般先按“0 不是纯位数”写如果 WA 了再改。别小看这一个 0它经常是压死骆驼的最后一根稻草。5.3 多组输入的终止条件有些题是多组输入以 EOF 结束有些是以0结束有些是先给一个 T 表示组数。这三种模式的读取方式完全不同。EOF 模式用while True: line readline()然后判断空0结束模式要在循环里判断if line 0: breakT 模式要先读 T 再循环 T 次。混用会导致多读或少读输出就全错位了。我印象最深的一次是题目说“输入若干行每行一个数以 0 结束”但 0 本身也是一个合法的查询问 0 是不是纯位数。这时候你就不能简单地在读到 0 时 break因为最后一个 0 可能是查询也可能是终止符。这种歧义题通常会在描述里说明“0 不作为查询”但如果你没看到就会纠结很久。遇到这种题先看样例样例里如果有 0 且后面还有数据那 0 就是查询如果 0 是最后一个那大概率是终止符。5.4 输出格式空格、换行、大小写输出格式的坑我列几个常见的题目要求YES你输出YesWA。题目要求每组输出后换行你最后一组没换行有些 OJ 判 PEPresentation Error有些直接 WA。题目要求输出true/false你输出1/0WA。题目要求多组结果用空格分隔你用了换行WA。这些错误看起来低级但在紧张比赛的时候特别容易犯。我的习惯是写完代码后把样例输入复制进去跑一遍然后用diff对比输出和样例输出一个字符一个字符地看。如果 OJ 支持还可以看错误信息里的“期望输出”和“实际输出”对比通常一眼就能看出问题。6. 从判断到构造纯位数题型的进阶玩法6.1 求下一个纯位数“给一个数 x求大于 x 的最小纯位数”是纯位数题最常见的变体。思路很直接先看 x 的位数 n如果 x 小于 n 位全 d 的最大值那答案就在 n 位里找否则答案在 n1 位里就是 n1 个 1。具体来说设 x 的位数为 n取 x 的首位数字 d。那么 n 位的纯位数里候选是d重复 n 次。如果这个候选大于 x答案就是它否则看(d1)重复 n 次如果 d1 不超过 9答案就是它如果 d 是 9那 n 位里没有更大的纯位数了答案就是 n1 个 1。举个例子x 234n 3d 2候选 222 小于 234下一个候选 333 大于 234所以答案是 333。再比如 x 999n 3d 9候选 999 等于 x 不大于d1 超过 9所以答案是 1111。这个逻辑用字符串处理非常干净不需要任何大数运算。def next_repdigit(s): n len(s) d int(s[0]) cand str(d) * n if cand s: return cand if d 9: return str(d 1) * n return 1 * (n 1)注意字符串比较cand s在等长情况下就是字典序比较等价于数值比较所以不需要转整数。这个技巧在大数场景下非常关键。6.2 求第 k 个纯位数前面提过公式第 k 个纯位数k 从 1 开始的位数是(k-1)//9 1数字是(k-1)%9 1。所以答案就是str((k-1)%9 1) * ((k-1)//9 1)。一行搞定。def kth_repdigit(k): d (k - 1) % 9 1 n (k - 1) // 9 1 return str(d) * n这个公式的推导其实很简单每 9 个纯位数位数加一所以整除 9 得到位数偏移余数决定是 1 到 9 中的哪一个。我一开始还想着用循环生成后来发现这个公式之后所有“第 k 个”类题目都是 O(1) 解决。6.3 统计区间内纯位数个数“求 [L, R] 内纯位数的个数”也是常见题。因为纯位数极其稀疏直接枚举所有纯位数然后判断是否在区间内是最简单的。纯位数总数在 64 位范围内只有 9 × 19 171 个19 位数枚举一遍毫无压力。def count_repdigits(L, R): cnt 0 for n in range(1, 20): for d in range(1, 10): v int(str(d) * n) if L v R: cnt 1 return cnt如果 L 和 R 是大数字符串形式那就把v也转成字符串比较或者用长度和字典序来判断。因为纯位数很少这个枚举法的效率远高于任何基于数位 DP 的复杂解法。有时候最简单的暴力反而是最优解前提是你知道解空间有多小。6.4 纯位数与回文数的关系纯位数一定是回文数因为所有位相同正读反读一样。但回文数不一定是纯位数比如 121。这个性质在有些题里可以用来剪枝如果判断一个数不是回文数那它一定不是纯位数。但反过来不成立所以只能用来快速排除不能用来确认。我在做一道“判断既是纯位数又是质数”的题时用过这个性质。先判断回文O(n)不是回文直接排除是回文再判断纯位数O(n)是纯位数再判断质数大数质数判断很慢。这样能把质数判断的次数降到最低。剪枝的顺序要按判断代价从低到高排这是做组合判断类题目的通用原则。7. 我常用的纯位数工具函数与调试心得7.1 一份可复用的工具函数集把上面零散的东西整理成一份工具函数以后遇到纯位数题直接复制def is_repdigit_str(s): 判断字符串形式的正整数是否为纯位数 if not s or not s.isdigit() or s[0] 0: return False return s.count(s[0]) len(s) def next_repdigit_str(s): 返回大于 s 的最小纯位数字符串形式 n, d len(s), int(s[0]) cand str(d) * n if cand s: return cand if d 9: return str(d 1) * n return 1 * (n 1) def kth_repdigit(k): 返回第 k 个纯位数k 从 1 开始 return str((k - 1) % 9 1) * ((k - 1) // 9 1) def gen_repdigits(max_len19): 生成所有不超过 max_len 位的纯位数整数列表 res [] for n in range(1, max_len 1): for d in range(1, 10): res.append(int(str(d) * n)) return res这几个函数覆盖了判断、构造、枚举三类需求。is_repdigit_str用了count在纯位数多的数据上快如果你数据里纯位数少可以改成显式循环提前返回。next_repdigit_str全程字符串操作不涉及大数转换适合任意长度。kth_repdigit是 O(1) 的。gen_repdigits用于打表。7.2 调试纯位数题的三个习惯第一个习惯是先写暴力再优化。纯位数题的数据范围通常不大除了大数变体暴力枚举所有纯位数往往就能过。先写个暴力版本确认逻辑正确再根据 TLE 情况优化。我见过太多人一上来就写复杂公式结果边界错了调半天。第二个习惯是手动构造边界用例。纯位数题的边界就那么几个1、9、10、11、99、100、111、999、1000。把这几个数代进去跑一遍基本能覆盖 90% 的边界错误。特别是 9 到 11 这个跨越位数的区间以及 99 到 111 这个跨越位数的区间最容易出问题。第三个习惯是用对拍验证。写一个暴力版本和一个优化版本随机生成大量输入对比两者输出。如果一致说明优化版本大概率正确。对拍是发现隐蔽 bug 的最有效手段尤其是涉及字符串和数值转换的题目。7.3 关于性能的一点实测数据我在本地用 Python 跑过一组测试对 10^6 个随机 10 位数字字符串做纯位数判断count版本耗时约 0.8 秒显式循环版本约 1.0 秒正则版本约 7.5 秒。如果是 10^6 个随机 3 位数字count约 0.3 秒显式循环约 0.25 秒因为提前返回生效正则约 2.1 秒。所以短字符串用显式循环长字符串用count这是一个可以记住的经验法则。对于 C 选手s.find_first_not_of(s[0])通常比手写循环快因为标准库做了优化。但要注意find_first_not_of返回string::npos表示没找到不同字符也就是全是相同字符。这个 API 的名字有点绕用的时候别搞反了。8. 纯位数题背后的通用解题思维纯位数这道题往小了说是一道字符串处理题往大了说它训练的是**“识别问题本质选择合适表示”**的能力。很多人拿到题就想着怎么用整数运算解决但纯位数的本质是“每一位相同”这个性质在字符串表示下是直接可见的在整数表示下反而要拆解。选对数据的表示形式问题就解决了一半。另一个思维点是利用稀疏性。纯位数在整数中极其稀疏这意味着枚举所有纯位数是可行的而枚举所有整数是不可行的。很多看起来复杂的计数、查找问题一旦意识到解空间很小就可以直接暴力。这种“先估计解空间大小再决定算法”的思路在 OJ 里非常实用。最后是边界意识。纯位数题的边界特别多0、负数、前导零、单位数、9 到 11 的跨越、99 到 111 的跨越。每写一个函数我都习惯性地问自己输入是 0 会怎样输入是 9 会怎样输入是 10 会怎样输入是 99 会怎样把这几个问题回答清楚代码基本就稳了。我在实际做这类题的时候最大的体会是不要急着写代码先把纯位数的生成公式和分布规律在纸上推一遍。推完之后你会发现很多原本以为要循环的东西其实有闭式解很多原本以为要判断的东西其实可以直接构造。这种“先数学后代码”的习惯让我在 OJ 上少走了很多弯路。如果你也在刷题不妨试试这个方法拿到题先花五分钟想数学性质再花五分钟写代码往往比直接写代码再调半天要快。