周赛的第一道题绝大多数时候就是送分题这道题也完全没有例外。题目名字很直白叫“连接非零数字并乘以其数字和”翻译成人话就是给你一个正整数 n先把 n 里所有非零的数字按原顺序拼接成一个新数字再把这个新数字乘上 n 的各位数字之和返回最终结果。举个例子n 103非零数字是 1 和 3拼起来得到 13数字和是 1 0 3 4那答案就是 13 × 4 52。别小看这道题它同时考了数位拆解、字符串拼接、进位构造、整数溢出四个基本功正好可以做一次很扎实的复盘。不管是刚开始刷算法的新手还是常年混周赛的老手这道题都值得花几分钟把实现细节看全因为后面带 “II” 的同类题很可能会在同样的思路上加码。1. 题目理解与核心思路1.1 拆成三个独立步骤题目给的描述再短落到代码上也逃不出三个动作取出每一位数字、过滤掉 0 并拼接、计算数字和并做乘法。第一步是数位拆解。这步几乎没有任何算法含量但实现方式会影响你后面踩不踩坑。取数位有两种常规姿势一种是转成字符串逐位取另一种是用 while 循环配合取余和整除。两种我都推荐试一试因为虽然字符串写法看起来简单但纯数值写法更能锻炼位运算级别的直觉。第二步是“连接非零数字”。这句话要分两层理解非零意思是跳过数字 0连接意思是保持原有的从左到右的顺序。比如 n 10023取出的数字序列是 1、0、0、2、3过滤掉两个 0 之后是 1、2、3按原顺序连接就是 123。这里最容易出错的地方是“顺序”后文我会专门展开说。第三步是“乘以其数字和”。数字和就是所有位数值累加0 本身加不加都没影响所以实际上第三步和第二步的过滤条件互不相干你只需要老老实实把所有位的数字累加起来就行。三步各干各的最后返回第二步的拼接结果乘以第三步的和这个流程理清之后整道题就已经解决了一半。1.2 为什么周赛要用这类题打头阵参加过周赛的人都知道Q1 的核心目的从来不是刁难你而是让你热手。很多人在真正的难题上不是不会做而是前五分钟进入不了状态手生、思路乱、连出错都出得莫名其妙。这种直白到几乎不需要建模的题目就是给你一个快速进入状态的缓冲带同时也考察最基础的内功能不能把一句话描述准确翻译成循环和变量。另外一面这类题虽然简单却会稳定筛掉一部分粗心的人。倒序没反转、数字和忘重置、int 溢出、空结果没有特判这些问题在简单题里几乎比难题里还容易出现。因为人一旦觉得题目简单警惕性就会下降。所以把 Q1 当作基本功检验场比把它当作“白送分”要更踏实。1.3 复杂度与数据范围先想清楚这道题的输入是一个整数 n在常规约束下n 的正整数范围一般是 32 位有符号整数也就是从 1 到约 21 亿。即便是更大的 64 位范围十进制位数也就是 18 位左右。逐位处理意味着时间复杂度是 O(d)d 表示十进制位数最多几十次循环跑起来完全无压力空间复杂度同样是 O(d)。这里真正需要提前想清楚的是乘积的规模。假设 n 的位数是 k过滤掉 0 后拼接出来的数字最大可能是所有位上都是 9例如 99999此时拼接结果本身就有 k 位。再乘以数字和数字和最大也不超过 9k。当 k 10 时乘积大约是 9,999,999,999 × 90已经远远超过 32 位 int 的约 21.47 亿上限。所以在 C 和 Java 里面如果返回值用 int 或者中间结果用 int一旦测试点给出接近上限的数就会直接翻车。结论是中间变量至少用 long 或者 long long最后返回时再按题目要求的类型转换。1.4 手动算样例建立自测依据我习惯在写代码之前先拿题目样例或者自己造的简单数把计算过程完整推一遍这样写完代码就能立刻对照而不是盲目提交再等反馈。拿 n 105 举例拆位得到 1、0、5非零数字是 1 和 5连接成 15数字和 1 0 5 6乘积 15 × 6 90。再拿 n 2304 举例拆位 2、3、0、4非零数字 2、3、4 连接成 234数字和 2 3 0 4 9乘积 234 × 9 2106。还可以拿一个带多个零的数比如 98010拆位 9、8、0、1、0非零数字 9、8、1 连接成 981数字和 9 8 0 1 0 18乘积 981 × 18 17658。这三种用例正好覆盖了“含一个 0”“不含 0”“含多个 0”三种情况。代码写完以后把这几个数套进去逐行跑一遍任何顺序错误都会当场暴露。2. 核心细节与实现选型2.1 用字符串提取还是用除以 10 提取先讲字符串方案。将 n 转成字符串后每一位都是字符遍历字符串就能按从左到右的天然顺序拿到所有数字。做拼接时直接把非零字符追加到结果字符串后面做累加时用当前字符减字符 ‘0’ 转成数值。这个方案最大的优势是没有顺序陷阱写起来非常线性基本不可能出错。再讲数值方案。经典写法是 while (n 0) { digit n % 10; n / 10; }每次取出当前最低位然后砍掉最低位。问题在于这种写法拿到的是从右往左的数位顺序。比如 n 105第一次取到 5第二次取到 0第三次取到 1顺序正好是反的。如果你在拼接时直接用 concat concat * 10 digit最后会拼出 501 而不是 15。两种方案对比起来字符串方案适合快速解题数值方案适合练手或者为“禁止字符串”的变形题做准备。我见过不少高手在 C 里直接走 while 取余然后用一个数组暂存再 reverse 一下逻辑也很快。但如果你是在周赛现场只想求稳字符串方案是性价比最高的选择。2.2 拼接新数字的两种构造方式假设过滤后的数字序列已经确定接下来怎么“拼成新数字”也有两种理解方式。第一种是字符串拼接。把每个非零数字当作字符或字符串接在后面最后一次性转成整数。这种写法符合直觉但是要额外承担一次字符串转整数的开销。考虑到位数很少这个开销完全可以忽略。唯一需要注意的是转整数的函数在不同语言里名字不同Java 是 Long.parseLongC 是 stollPython 直接用 int()。第二种是数值构造。维护一个 t初始为 0每遇到一个非零数字 digit就执行 t t * 10 digit。比如前面提到的 1、2、3执行过程是 t 0 * 10 1 1t 1 * 10 2 12t 12 * 10 3 123。这种写法本质上是把“进位拼接”拆成乘 10 加个位比赛中最常用因为不需要字符串和整数的来回转换性能也更好。我个人的建议Python 里用字符串拼接最清晰Java 和 C 里如果追求简洁可以直接用字符串想练细节可以用数值构造。只要保证不对 0 做拼接两种方式结果完全一样。2.3 数字和里的 0 要不要处理这里有个很多人纠结半天的点题目说“非零数字”那我算数字和的时候是不是也要把 0 跳过其实完全不需要。通俗点说数学里任何数加上 0 都不变。数字和是把所有位值相加包含的 0 位贡献为 0跳过 0 再求和结果和所有位一起求和的答案一模一样。所以你在遍历时只需要把所有 digit 都累加进 sum 即可。如果你顺手加了一个 if (digit ! 0) 再累加也不算错但是会让代码多出一个毫无意义的分支反而不如直接加来得清楚。真正需要区分“是否非零”的地方只有拼接这一步因为拼接的时候如果某一位是 0你不拼它才符合题意如果拼了它就会凭空多出前导 0 或中间 0拼接结果就直接错了。2.4 返回值类型与整数溢出这题看起来人畜无害但溢出问题真实存在而且专门坑那种“用了 int 还自信满满”的人。最直观的例子是 n 2147483647也就是 int 的最大值。这个数本身没有 0非零拼接后还是 2147483647数字和是 2 1 4 7 4 8 3 6 4 7 46乘积约 98.8 亿远超 21.47 亿的 int 上限。要是 n 更大一点比如 9999999999拼接结果是 9999999999数字和是 90乘积接近 9000 亿。虽然这个数已经超出 int 输入范围但足以说明运算规模可以很大。所以凡是 Java、C 这类有固定位宽的语言中间量一律用 long 或 long long。Python 的整数是无限精度的不用考虑这个但这不代表你可以忽略这个概念因为其他语言里的坑你在团队协作或者面试里还会再遇到。3. 完整实现与提交过程3.1 最直观的 Python 实现讲完细节直接上代码。Python 版本用字符串方案代码量最短也最容易照着写。def connect_non_zero_and_multiply(n: int) - int: if n 0: return 0 s str(n) concat digit_sum 0 for ch in s: d int(ch) digit_sum d if d ! 0: concat ch if not concat: return 0 return int(concat) * digit_sum逐行说明先特判 0避免后面出现空字符串转换报错。随后遍历字符串d 是当前位数累加进 digit_sum如果 d 非零就把原字符接在 concat 尾部。这里接 ch 而不是接 str(d)是因为非零字符和数字字符在 ASCII 体系里严格对应直接沿用原字符既快又不容易错。最后如果所有位都是 0比如输入 n 0 已在前面被拦住但代码里依然保留了对空字符串的保护保证不会 int(concat) 抛异常。实测跑前面三个用例105 → 902304 → 210698010 → 17658全部正确。3.2 Java 实现用 long 兜底Java 版本里同样用字符串方案但是把中间结果和最后乘积都设置成 long能够直接避开溢出问题。public long connectNonZeroAndMultiply(int n) { if (n 0) { return 0; } String s Integer.toString(n); StringBuilder sb new StringBuilder(); long sum 0; for (char c : s.toCharArray()) { int d c - 0; sum d; if (d ! 0) { sb.append(c); } } if (sb.length() 0) { return 0; } long concat Long.parseLong(sb.toString()); return concat * sum; }这里有个小细节Java 的字符转数字用 c - ‘0’ 是效率最高的写法别用 Character.getNumericValue(c)后者虽然也能用但内部做了很多额外判断在这个场景下没有必要。拼接用 StringBuilder 而不是直接字符串加号是为了避免不必要的 String 对象创建虽然位数短影响不明显但这个习惯值得保持。如果题目要求返回 int可以用 return (int)(concat * sum) 做一次强转。不过前提是你得确认题目给的 n 范围小乘积确实不会超过 int 上限否则强转出来的负数会让提交卡死在测试用例上。3.3 C 实现数值构造省掉字符串开销C 版本我用纯数值方案把取余得到的数位放进 vector再反转最后用乘 10 进位构造拼接结果顺便练习一下最常见的竞赛套路。long long connectNonZeroAndMultiply(int n) { if (n 0) { return 0; } vectorint digits; long long sum 0; while (n 0) { int d n % 10; digits.push_back(d); sum d; n / 10; } reverse(digits.begin(), digits.end()); long long concat 0; for (int d : digits) { if (d ! 0) { concat concat * 10 d; } } return concat * sum; }这段代码里最需要注意的是 reverse 那一行。因为 while 循环取出的是从低位到高位的顺序如果不做反转digits 就是 [5, 0, 1] 这样的逆序结果拼接时就会把 105 拼成 510答案直接错误。反转之后变成 [1, 0, 5]再跳过 0得到序列 [1, 5]数值构造得到 15一切正常。有人会问能不能不存 vector直接在 while 里一边取一边拼答案是不能因为数值构造要求数位从高位开始而取余天然从低位开始顺序对不上。必须先收集再反转或者改用字符串方案。3.4 用边界用例检查逻辑写完代码我习惯手背一套边界用例比直接提交更保险。下面这张表我每次遇到数位题都会走一遍。输入 n非零拼接数字和返回结果备注55525单数位1000111多个连续 0100111222首尾都有 0101011222间隔 012030412341012340零分散在多处9999999999999999998180999999919接近 int 上限0空00边界特判把这些用例一个个跑完如果全部通过说明你的实现至少在基础逻辑上没有问题。特别是 1001 和 1010 这两个用例很容易暴露顺序拼接和 0 过滤的问题。3.5 替换方案全部走取模构造如果你不想用字符串又希望代码更精练可以把字符串方案和数值方案混用一个中间状态先用 while 把数位存进 array再反向遍历构造拼接数。def connect_non_zero_and_multiply(n: int) - int: if n 0: return 0 digits [] s 0 while n 0: d n % 10 digits.append(d) s d n // 10 digits.reverse() t 0 for d in digits: if d ! 0: t t * 10 d return t * s这段代码的核心逻辑和 C 完全相同只是去掉了显式的 reverse改用 Python 列表的 reverse 方法。跑同样的用例结果与字符串版本完全一致。两种写法我都会保留因为遇到后续题目如果限制不允许把数字转字符串你就需要这个纯数值版本来兜底。4. 常见问题与排查技巧实录4.1 顺序反了除以 10 的倒序陷阱这个坑我见过太多次了而且经常出现在自认为代码写得很流畅的人身上。核心原因是 while 循环取数位天然是从右往左而题目要求的是从左往右的原顺序。举一个具体的错误例子n 105数字和计算没问题得到 6。但如果你在 while 循环里一边取位一边拼 concat第一次取到 5concat 5第二次取到 0因为 0 被跳过所以不变第三次取到 1concat 5 * 10 1 51。最后结果 51 × 6 306而正确结果是 15 × 6 90。排查建议所有用到 while 取余的数位题写完以后立刻拿一个带 0 的数字跑一遍例如 105、1009、9090。如果答案和心算对不上第一嫌疑人就是顺序反转问题而不是逻辑分支问题。4.2 字符与数字的条件混写字符串方案里char 类型的 ‘0’ 和 int 类型的 0 完全不是一回事。有人会在遍历字符串时写成 if (ch) 或者 if (ch ! 0)前者会抛出类型不匹配或永远为真的问题后者会无差别跳过所有字符因为正常字符的数值都不等于 0。正确写法是 if (ch ! 0)这里必须是字符字面量的 0。在 Python 里同理ch 是字符串判断条件写 ch ! 0而不是 ch ! 0后者永远不会为真的同时还会被 linter 警告。遇到这个问题时最直接的排查方式是打印出每一位的类型和数值一眼就能看明白。4.3 空拼接字符串时的返回值如果题目允许输入 0或者某位测试点里出现 n 的所有位都是 0 的情况concat 字符串会是空数值构造出的拼接数也会保持 0。在这种边界下乘以数字和 0结果自然是 0。但问题是如果不对空字符串做保护代码里调用 int(concat) 或 Long.parseLong 时会直接抛异常。我见过有人因为少写了这个保护提交后在一个千分之一的边界用例上挂掉非常可惜。所以不管是 Python、Java 还是 C都得在最后加一行如果拼接结果为空直接返回 0。4.4 多组输入下忘记重置变量周赛题目通常给单个函数调用但实际练习平台或者某些笔试题里可能会要求你处理多组输入。这时候最容易出现的问题是你在循环外初始化了 sum 和 concat第一组数据处理完第二组数据又在这个基础上继续累加结果自然全错。正确做法是把 sum 和 concat 的初始化写在每一组输入的处理循环内部保证每一轮都是全新的起点。判断方法很简单把你的代码塞进一个 for 循环里连续跑三组输入如果三组结果都正确说明变量作用域没有污染。4.5 周赛第一题的排查顺序我每次提交简单题前都会按固定顺序自检顺序不对容易漏掉关键点。先把题目给的样例跑一遍再用自己造的边界用例跑一遍然后检查中间变量类型是否会溢出最后才点提交。这个顺序基本不会漏问题。检查顺序要看的点常见失败表现1题目样例是否通过样例就挂通常是题意理解错2构造边界用例跑一遍带 0 的数结果不对顺序或过滤出错3中间量类型是否够大大数用例返回负数或溢出4空结果是否有保护空字符串转整数直接抛异常按照这个顺序走一遍简单题基本能稳定一次过。5. 从这道题往后想一步既然标题带了个罗马数字 I大概率后面还会有同系列题II 通常会在 I 的基础上加一点变化。常见的方向是把单个 n 改成数组里的多个数或者把“乘以其数字和”改成“除以其数字和”又或者要求你在连接时先对非零数字做排序。这些变形题的底层都还是这堂课里练过的几个基本动作数位拆解、过滤、拼接、求和。如果你时间充裕我建议你把字符串方案和纯数值方案各实现一遍然后分别跑同样一组用例。这样做的好处是以后遇到禁止字符串或者需要极致性能的题你能自然切换方案。曾经有人问过我“这么简单的题多写一个版本是不是浪费时间”我的想法恰恰相反同一道题用两种思路去实现是练习“思维切换”最廉价的方式。这个习惯保持下来周赛里遇到更复杂的题目时你会明显感觉到自己换思路的速度比原来快了不少。另外周赛 Q1 还有一个隐藏的价值它往往决定了你整场比赛的心态。能在五分钟内稳稳把这道题写完后面做 Q2 和 Q3 的时候心里会踏实很多如果卡在这道题二十分钟后续压力会成倍放大。所以这类简单题平时就应该练到“闭眼都能写对”的程度。做这类题时我个人的一个小技巧是提交前永远把 n 设成那几个容易出错的特殊值跑一遍多花五秒钟可能就少一整个调试周期。