最近刷题碰到一道很有意思的题目叫《来自异国的客人》分值100分题目后面还特意标注了“Java JS Python C”四种语言。乍看名字还以为是什么文化背景题结果点进去才发现内核就是一道非常经典的进制转换题。题面大体是一位异国客人习惯用 k 进制记数你给他一个十进制整数 n要你算出这个数在他熟悉的 k 进制写法里某个指定数字 m 出现了几次。说白了就是“十进制转 k 进制再数一数目标数字出现多少次”。我第一次看到这道题时脑子里冒出的第一个想法是会不会涉及什么国家文化、数字忌讳后来静下心把样例一推发现完全不是那么回事。出题人故意用“异国客人”这个场景把算法包了一层实际上就是想考察三件事进制转换的基本功、循环取余的熟练度、以及面对边界条件时的细心程度。这篇文章我会把四种语言的解法都拆开讲一遍顺便把我自己在实际调试中踩过的坑也列出来希望能帮到正在刷题、准备机考或者面试的朋友。1. 题目到底在考什么一场披着故事外衣的进制转换1.1 先还原一下题目的真实面貌我没法把原题一字不差地贴出来毕竟是别人的测评题目但核心信息非常固定就三个输入一个输出输入十进制整数 n目标进制 k要统计的数字 m输出n 转换成 k 进制后数字 m 出现的次数举个例子假设输入n 10 k 2 m 0十进制的 10 转换成二进制是1010其中数字0出现了 2 次所以输出应该是2。这种题目本身不难但它很有代表性。因为它把“进制转换”这个最基础的知识点包装成了一道有剧情、有分值的编程题。你要是被“异国客人”这个设定带跑了真的会浪费时间想什么“客人国家用的是几进制”“他喜欢哪个数字”其实这些都是干扰信息。1.2 为什么这道题值 100 分很多刷题平台会把题目按分值和难度分级100分的题通常属于“中等偏简单”但也绝不是白给。我个人的理解是这道题能拿满分的人不少但能稳定满分的人不多。为什么因为它藏了几个一眼看不出来的边界条件。比如说n 0这种情况。很多人一看到 while 循环就默认 n 一定大于 0结果n0时循环一次都不执行直接返回 0。但 0 的 k 进制表示就是0如果 m 也是 0那答案应该是 1。这一下就能筛掉一批粗心的人。再比如说m会不会大于等于k如果 m 是 7k 是 2那 2 进制里根本不可能出现数字 7答案必然是 0。如果程序里没有提前判断就会白白循环一遍而且结果还是 0虽然碰巧对了但逻辑上不严谨。所以说这 100 分考的不是你会不会写while循环而是你能不能把所有边角情况都考虑进去。1.3 适合谁来参考这篇拆解如果你正在准备机考、校招笔试、或者单纯想巩固基础算法这篇内容都很合适。我会把四种语言的代码都贴出来并且逐行解释。你不需要多聪明只要跟着思路走一遍然后自己动手敲一遍基本就能把这 100 分稳稳拿住。之后同类题比如“求某进制下各位数字之和”“判断某进制下是否包含特定数字”都可以用一个模板套进去。2. 核心思路除 k 取余法以及它为什么不会错2.1 进制转换的数学原理十进制转 k 进制最经典的方法就是除 k 取余法。你拿 n 除以 k得到的余数就是 k 进制表示里的最低位然后把商继续除以 k得到的余数是下一位一直循环到商为 0 为止。这里面的数学逻辑其实很朴素。十进制数 n 可以写成n q1 * k r1其中 r1 是 n 除以 k 的余数q1 是商。r1 的范围一定是 0 到 k-1正好对应 k 进制最低位上的数字。接着对 q1 做同样的操作q1 q2 * k r2r2 就是第二低位的数字。重复这个过程直到某一步商为 0。最后把所有余数逆序排列就是完整的 k 进制表示。举个例子把十进制 13 转成二进制13 ÷ 2 6 余 1最低位是 16 ÷ 2 3 余 0第二位是 03 ÷ 2 1 余 1第三位是 11 ÷ 2 0 余 1最高位是 1把余数从下往上排得到1101这就是 13 的二进制表示。验证一下1×8 1×4 0×2 1×1 13完全正确。2.2 边转换边统计比“先转完再数”更省事这道题要求统计某个数字 m 出现的次数。有两种实现路线第一种先把 n 完整转换成 k 进制得到一个字符串然后遍历这个字符串去数 m。这种方法直观但要多开辟一份字符串空间而且在不同语言里还要处理字符和数字之间的转换。第二种在循环取余的过程中每得到一个余数 digit就立即判断它是不是等于 m是就计数加一。这种方法空间复杂度是 O(1)代码也更短。我强烈推荐第二种做法。因为它复用了一个本来就存在的循环没有任何额外开销。你只需要在 while 循环里加一个 if 判断就行。下面是这个思路的伪代码if n 0: return 1 if m 0 else 0 count 0 while n 0: digit n % k if digit m: count count 1 n n / k # 注意这里是整除 return count这个模板适用于所有语言后续只要照着语法改一改就行。2.3 复杂度分析时间复杂度是 O(log_k n)。因为 n 每循环一次就除以 k循环次数就是 n 在 k 进制下的位数。比如十进制 100 转二进制大概要循环 7 次因为 2^7 128。这个复杂度对于日常输入来说完全够快哪怕 n 是 10 亿也就循环 30 多次。空间复杂度是 O(1)因为我们只用了几个临时变量没有存整个转换结果。这一点在 C 语言里尤其重要因为如果先转成字符串你就得提前开一个足够大的字符数组还得处理数组越界问题。3. 四种语言逐个击破Java JS Python C3.1 Java 实现Java 版本我写得很直白就用一个 count 变量累加完全不需要引入字符串处理。很多 Java 新手喜欢先转成字符串再用indexOf或者charAt去数其实完全没必要反而容易踩字符转数字的坑。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int k sc.nextInt(); int m sc.nextInt(); System.out.println(countDigit(n, k, m)); } public static int countDigit(int n, int k, int m) { // 如果 m 不在 k 进制的合法数字范围内直接返回 0 if (m 0 || m k) { return 0; } // n 0 时k 进制表示就是 0需要单独处理 if (n 0) { return m 0 ? 1 : 0; } int count 0; while (n 0) { int digit n % k; if (digit m) { count; } n / k; } return count; } }这里面有两点值得解释。第一m k的提前判断不是可有可无的它能让逻辑更严谨。第二n 0必须放在 while 循环前面处理否则循环不执行答案就会是 0而正确答案应该是当 m 为 0 时输出 1。如果你担心 n 特别大可以把int换成long方法签名也改成long n。在 Java 里用long做除法和取余没有任何问题只是在读入时要用nextLong()。3.2 JavaScript 实现JavaScript 版本同样建议手动实现进制转换。虽然 JS 内置了toString(radix)方法可以很方便地把数字转成任意进制字符串但它有两个问题第一toString得到的是字符串你仍然得遍历字符串去数字符底层还是得多做一层第二toString(2)这样的调用在数字很大时可能会有精度溢出问题因为 JS 的 Number 是浮点数超过Number.MAX_SAFE_INTEGER就不精确了。所以老老实实写循环反而最稳。function countDigit(n, k, m) { // 输入合法性检查 if (m 0 || m k) { return 0; } if (n 0) { return m 0 ? 1 : 0; } let count 0; while (n 0) { const digit n % k; if (digit m) { count; } // 注意这里必须用 Math.floor确保是整数除法 n Math.floor(n / k); } return count; } // 测试 console.log(countDigit(10, 2, 0)); // 2JS 新手最容易犯的错误是直接写n n / k。在 JS 里/运算符做的是浮点数除法比如10 / 2得到 5这没问题但9 / 2会得到 4.5。如果你不Math.floor下一轮17 % 2之类的结果就会全乱掉。所以务必写成Math.floor(n / k)。如果你真的很喜欢toString那我也给一个参考写法function countDigitWithToString(n, k, m) { if (n 0) { return m 0 ? 1 : 0; } const s n.toString(k); let count 0; for (const ch of s) { // 将字符转成数字注意处理 a-f 这类字母 const digit parseInt(ch, k); if (digit m) { count; } } return count; }这个写法在 k 小于等于 10 时能正常工作但如果 k 大于 10就会遇到字母。比如十六进制里a代表 10parseInt(a, 16)会得到 10但你要统计的 m 如果是 10逻辑上仍然成立。只是这种写法多了一层字符解析性能不如手动取余。3.3 Python 实现Python 的写法是最干净的因为它语法简洁而且整数除法//和取余%的语义非常明确。尤其要注意Python 3 里/是浮点除法//才是整除一定要用//。def count_digit(n: int, k: int, m: int) - int: # 如果 m 不可能是 k 进制中的数字直接返回 0 if m 0 or m k: return 0 # n 0 的特殊处理 if n 0: return 1 if m 0 else 0 count 0 while n 0: digit n % k if digit m: count 1 n // k return count if __name__ __main__: print(count_digit(10, 2, 0)) # 2Python 里还可以用divmod一次性同时得到商和余数让代码更紧凑def count_digit_divmod(n: int, k: int, m: int) - int: if m 0 or m k: return 0 if n 0: return 1 if m 0 else 0 count 0 while n: n, digit divmod(n, k) if digit m: count 1 return countdivmod(n, k)返回一个元组第一个是整除后的商第二个是余数。把n重新赋值为商digit保存余数一行代码完成两件事。不过这个写法对不熟的读者可能有点绕建议在面试中还是用%和//更直观。Python 还有一个优势就是它原生支持大整数不会像 C/Java 那样担心int溢出。所以即使 n 给到 10^18这个函数照样能算出正确结果。3.4 C 语言实现C 语言是这个题目的“原教旨”解法。因为进制转换本来就是计算机底层最常做的事情用 C 写反而最顺手。C 的整数除法/本身就是向零取整所以不用担心n n / k会变成小数。#include stdio.h int countDigit(int n, int k, int m) { if (m 0 || m k) { return 0; } if (n 0) { return m 0 ? 1 : 0; } int count 0; while (n 0) { int digit n % k; if (digit m) { count; } n / k; } return count; } int main() { int n, k, m; scanf(%d %d %d, n, k, m); printf(%d\n, countDigit(n, k, m)); return 0; }这里没什么花哨的技巧唯一要提醒的是变量类型。如果 n 的范围可能超过int的最大值约 21 亿建议把int改成long long对应的scanf和printf也要改成%lld。例如long long countDigit(long long n, int k, int m) { ... }C 语言不像 Java 或 Python 那样有字符串的便利方法但这道题根本不需要转换成字符串直接用余数比较数字大小即可。这也再次说明了“边转换边统计”的思路有多省事。3.5 四种语言横向对比语言核心代码量主要易错点推荐场景Java中输入输出模板稍长int 可能溢出企业应用开发、机考主流语言JavaScript短/是浮点除法忘记Math.floor会导致死循环前端岗笔试、算法练习Python最短忘记用//整除想当然用内置函数处理带前缀的字符串快速验证思路、算法学习C短数据范围控制scanf/printf 格式符底层原理学习、竞赛基础其实四种语言的核心逻辑一模一样差别只在于语法表达。这就是为什么我建议刷题时同一道题用不同语言各写一遍能帮你把语言特性记得更牢固。4. 边界情况与隐藏陷阱这些坑我帮你们踩过了4.1 边界情况速查表下面这个表是我整理出来的常见边界情况基本覆盖了这道题 80% 的隐藏失分点。输入情况正确答案常见错误n0, k2, m010因为 while 循环没执行n0, k2, m101误认为 0 的二进制包含 1n5, k2, m30死循环忘记 m 不在 k 进制中n100, k10, m021100 的十进制里有 2 个 0n1, k2, m110二进制 1 中恰好有 1 个 1n255, k16, m1510十六进制 FF 中的 F 代表 15第 5 行看起来简单但确实有人会在 n1 的时候把答案写成 0因为循环只执行一次而他们把条件写成了digit m n ! 1这种多余判断。第 6 行比较特殊。如果 k16m15那么 n255 转十六进制是FF每一位都是 15所以答案应该是 2。如果你用的是字符串遍历方案要注意parseInt(F, 16)的结果确实是 15而不是 0。当然大部分题目里 m 都是 0-9k 也不超过 10这个例子主要是提醒大家进制扩展后的处理逻辑。4.2 为什么 n0 是最大的坑我特地把它单独拎出来说因为网上的题解里十个有八个会忘记处理 n0。很多人一看到n % k就默认 n 是正整数结果样例全是正数自测也全过等交上去发现某个隐藏用例挂了。0 在任何进制下都写作0。所以如果 m0答案是 1如果 m 不等于 0答案是 0最简单的处理方式就是在函数开头单独判断if (n 0) { return m 0 ? 1 : 0; }这行代码你可以在所有语言里都写上。没坏处还能防止后面循环直接跳过。4.3 m 的合法性判断我遇到不少人在拿到题目后没仔细看数据范围直接开始写循环。假如 m 大于等于 k比如 k2, m3那么 while 循环里永远不可能出现 digit 3但程序会老老实实地把整个循环跑完然后返回 0。虽然结果碰巧对但万一 m 是个负数或者在某些特殊进制下 m 的表示涉及字母就会出麻烦。稳妥的做法是在开头加一句if (m 0 || m k) { return 0; }别小看这行代码它能让你的逻辑闭环并且向阅卷人传递一个信号你注意到了数字范围这个关键约束。4.4 语言层面的数据溢出问题这道题如果输入范围只是 10^9 以内用 int 完全够。但有些机考题目会悄悄把数据范围拉大尤其是 Python 玩家往往容易忽略其他语言的溢出问题。C 语言int最大约 21 亿有符号 32 位如果 n 可能超过 10^9建议直接用long long宁可多占 4 个字节也别冒险。Javaint同样有 21 亿上限读入时可以用long但Scanner.nextLong()和nextInt()别用混了。JavaScriptJS 的 Number 是双精度浮点数超过2^53 - 1就不安全了。如果题目说 n 可以达到 10^18JS 需要借助BigInt类型写成BigInt(n)然后所有除法、取余都要换用 BigInt 的方法这就复杂多了。好在大多数考 JS 的场景数据范围不会那么变态。Python自带大整数无限位不用管溢出这是 Python 在这道题里最大的优势。4.5 内置进制转换方法的隐藏坑Python 的bin(n)会返回0b1010这种带前缀的字符串oct(n)返回0o...hex(n)返回0x...。如果你直接拿bin(n)去数 0前缀里的0b里的 0 也会被数进去结果就会多 1。JavaScript 的n.toString(2)没有前缀但得到的是字符串你要数 0 就得遍历字符串而且如果 m 是数字 10你还得先把字符a转成数字 10多一层麻烦。C 语言没有内置进制转换函数一切都要自己写所以反而不会踩这种坑。Java 的Integer.toString(n, k)可以转成指定进制字符串但同样返回字符串需要遍历字符。所以我的最终建议是在笔试或机考中手动实现除 k 取余法不要依赖内置的进制转换方法。内置方法看着方便一旦涉及统计反而会让你多处理很多边角情况。5. 从这道题出发一个通用模板和它的变体5.1 把核心逻辑抽成函数这道题的价值不在于背代码而在于你能掌握“进制转换 逐位处理”这个万能模板。下面这个模板适用于所有语言func countDigit(n, k, m): if m 0 or m k: return 0 if n 0: return (m 0) ? 1 : 0 count 0 while n 0: digit n % k if digit m: count 1 n n / k # 整除 return count只要把n、k、m换成别的变量名就能套用到很多相似题目上。比如“给定 n 和 k求 n 在 k 进制下各位数字之和”“求 n 在 k 进制下最高位是什么”“判断 n 在 k 进制下是否包含某个数字”。5.2 三个典型变体变体一直接求 k 进制下各位数字之和。int digitSum(int n, int k) { if (n 0) { return 0; } int sum 0; while (n 0) { sum n % k; n / k; } return sum; }变体二求 k 进制表示的最高位数字。这需要先算出有多少位或者用对数估算但最简单的做法是先循环一遍求出所有位存到数组里最后一个余数就是最高位。变体三判断 n 在 k 进制下是不是回文数。比如十进制 121 转二进制是1111001不是回文但十进制 5 转二进制是101是回文。这类题同样只需要在循环里把每位数字收集起来最后前后比较。所以你看一道“来自异国的客人”真正训练的是你处理进制的底层能力背景故事再花哨核心永远不变。5.3 自己动手做一次完整测试不管用哪种语言我建议你写完代码后至少跑下面这 5 组测试用例全对才说明这题你真的拿稳了。n10, k2, m0 - 2 n0, k2, m0 - 1 n0, k2, m1 - 0 n255, k16, m15 - 2 n100, k10, m0 - 2如果最后一组你觉得奇怪解释一下100 在十进制下是三位数100其中数字 0 出现了 2 次所以输出 2。很多人在这个用例上会错写成 1因为他们只考虑了末尾的 0忘了十位上的 0。6. 实操心得与答题策略6.1 机考/面试时如何稳拿这 100 分我在实际机考中总结了一套固定流程拿到这种题先不读故事直接做三件事第一在草稿纸上写下输入输出和示例数据。把题面里的样例手动算一遍确保自己理解正确。第二判断数据范围。如果 n 可能是 0先写特殊处理如果 m 可能越界先写合法性判断如果 n 很大选long或BigInt。第三写一个最朴素的循环版本不要一上来想优化。这种 100 分的题能用 O(log_k n) 的时间解出来已经满分了不需要什么奇技淫巧。按照这个流程我基本可以在 5 分钟内写完并调试完毕。剩下时间可以用来检查其他题。6.2 四种语言的调试差异这道题在四种语言里的调试体验差别很大我说一下自己的体感。C 语言最容易出问题的是格式符写错。scanf里写%d却传入long long的地址轻则读入错乱重则段错误。所以我在 C 里用到long long时会非常刻意地检查scanf和printf的格式符。Java 的调试麻烦主要在代码结构。你总不能把方法写在类外面所以我会先在本地写好一个完整的Main类结构然后专注于方法体逻辑。JavaScript 最经典的坑是浮点数除法我在本地跑的时候习惯在这个位置加一行console.log(n)如果发现出现小数就知道忘记Math.floor了。Python 的调试最舒服因为报错信息直观而且//和%的优先级很清晰。唯一要留意的是别把//写成/否则循环会退化成浮点数除法导致 n 永远减不到 0最后形成死循环。6.3 从这道题能学到什么很多同学刷题喜欢“广撒网”今天做链表明天做二叉树后天做动态规划结果每样都只懂个皮毛。像这种 100 分的简单题反而是吃透语言细节的好素材。用四种语言各写一遍你会不自觉地思考为什么 Python 写起来这么快为什么 C 没有字符串也能解为什么 Java 的int会有上限这些问题比题目本身更能提升你的工程能力。我个人刷题的习惯是每遇到一道值得做的题就会在本地建一个文件夹用solution.c、Solution.java、solution.js、solution.py四个文件分别保存同一份逻辑。几个月后再回看这些代码对比各语言的差异那种收获不是刷几道难题能比的。6.4 一个小技巧把 m 的判断写在最前面最后再分享一个个人小习惯。我会在countDigit函数的第一行就先判断m的合法性而不是等循环结束再处理。这不是为了性能而是为了让自己在读代码时一眼就能确认边界条件已经处理完。写这类基础题代码顺序很重要边界条件先处理主逻辑放中间这样不管你一个月后回来看还是交给其他人 review都不会觉得混乱。而且这个习惯在面试白板编程时特别加分。面试官如果看到你第一行就处理了m k和n 0一般会认为你考虑问题比较全面哪怕后面代码有小瑕疵印象分也会高不少。以上总结一下我对“来自异国的客人”这道题的所有经验。题目本身不难但它是一面很好的镜子能照出你对进制转换、边界判断和多语言语法的熟悉程度。如果你在机考或面试里碰到它希望这篇文章能帮你稳拿满分。 
长河君 · 2026/9/30 8:31:20 · 阅读 1.2k 《来自异国的客人》题解：进制转换与数字统计的四种语言实现
最近刷题碰到一道很有意思的题目叫《来自异国的客人》分值100分题目后面还特意标注了“Java JS Python C”四种语言。乍看名字还以为是什么文化背景题结果点进去才发现内核就是一道非常经典的进制转换题。题面大体是一位异国客人习惯用 k 进制记数你给他一个十进制整数 n要你算出这个数在他熟悉的 k 进制写法里某个指定数字 m 出现了几次。说白了就是“十进制转 k 进制再数一数目标数字出现多少次”。我第一次看到这道题时脑子里冒出的第一个想法是会不会涉及什么国家文化、数字忌讳后来静下心把样例一推发现完全不是那么回事。出题人故意用“异国客人”这个场景把算法包了一层实际上就是想考察三件事进制转换的基本功、循环取余的熟练度、以及面对边界条件时的细心程度。这篇文章我会把四种语言的解法都拆开讲一遍顺便把我自己在实际调试中踩过的坑也列出来希望能帮到正在刷题、准备机考或者面试的朋友。1. 题目到底在考什么一场披着故事外衣的进制转换1.1 先还原一下题目的真实面貌我没法把原题一字不差地贴出来毕竟是别人的测评题目但核心信息非常固定就三个输入一个输出输入十进制整数 n目标进制 k要统计的数字 m输出n 转换成 k 进制后数字 m 出现的次数举个例子假设输入n 10 k 2 m 0十进制的 10 转换成二进制是1010其中数字0出现了 2 次所以输出应该是2。这种题目本身不难但它很有代表性。因为它把“进制转换”这个最基础的知识点包装成了一道有剧情、有分值的编程题。你要是被“异国客人”这个设定带跑了真的会浪费时间想什么“客人国家用的是几进制”“他喜欢哪个数字”其实这些都是干扰信息。1.2 为什么这道题值 100 分很多刷题平台会把题目按分值和难度分级100分的题通常属于“中等偏简单”但也绝不是白给。我个人的理解是这道题能拿满分的人不少但能稳定满分的人不多。为什么因为它藏了几个一眼看不出来的边界条件。比如说n 0这种情况。很多人一看到 while 循环就默认 n 一定大于 0结果n0时循环一次都不执行直接返回 0。但 0 的 k 进制表示就是0如果 m 也是 0那答案应该是 1。这一下就能筛掉一批粗心的人。再比如说m会不会大于等于k如果 m 是 7k 是 2那 2 进制里根本不可能出现数字 7答案必然是 0。如果程序里没有提前判断就会白白循环一遍而且结果还是 0虽然碰巧对了但逻辑上不严谨。所以说这 100 分考的不是你会不会写while循环而是你能不能把所有边角情况都考虑进去。1.3 适合谁来参考这篇拆解如果你正在准备机考、校招笔试、或者单纯想巩固基础算法这篇内容都很合适。我会把四种语言的代码都贴出来并且逐行解释。你不需要多聪明只要跟着思路走一遍然后自己动手敲一遍基本就能把这 100 分稳稳拿住。之后同类题比如“求某进制下各位数字之和”“判断某进制下是否包含特定数字”都可以用一个模板套进去。2. 核心思路除 k 取余法以及它为什么不会错2.1 进制转换的数学原理十进制转 k 进制最经典的方法就是除 k 取余法。你拿 n 除以 k得到的余数就是 k 进制表示里的最低位然后把商继续除以 k得到的余数是下一位一直循环到商为 0 为止。这里面的数学逻辑其实很朴素。十进制数 n 可以写成n q1 * k r1其中 r1 是 n 除以 k 的余数q1 是商。r1 的范围一定是 0 到 k-1正好对应 k 进制最低位上的数字。接着对 q1 做同样的操作q1 q2 * k r2r2 就是第二低位的数字。重复这个过程直到某一步商为 0。最后把所有余数逆序排列就是完整的 k 进制表示。举个例子把十进制 13 转成二进制13 ÷ 2 6 余 1最低位是 16 ÷ 2 3 余 0第二位是 03 ÷ 2 1 余 1第三位是 11 ÷ 2 0 余 1最高位是 1把余数从下往上排得到1101这就是 13 的二进制表示。验证一下1×8 1×4 0×2 1×1 13完全正确。2.2 边转换边统计比“先转完再数”更省事这道题要求统计某个数字 m 出现的次数。有两种实现路线第一种先把 n 完整转换成 k 进制得到一个字符串然后遍历这个字符串去数 m。这种方法直观但要多开辟一份字符串空间而且在不同语言里还要处理字符和数字之间的转换。第二种在循环取余的过程中每得到一个余数 digit就立即判断它是不是等于 m是就计数加一。这种方法空间复杂度是 O(1)代码也更短。我强烈推荐第二种做法。因为它复用了一个本来就存在的循环没有任何额外开销。你只需要在 while 循环里加一个 if 判断就行。下面是这个思路的伪代码if n 0: return 1 if m 0 else 0 count 0 while n 0: digit n % k if digit m: count count 1 n n / k # 注意这里是整除 return count这个模板适用于所有语言后续只要照着语法改一改就行。2.3 复杂度分析时间复杂度是 O(log_k n)。因为 n 每循环一次就除以 k循环次数就是 n 在 k 进制下的位数。比如十进制 100 转二进制大概要循环 7 次因为 2^7 128。这个复杂度对于日常输入来说完全够快哪怕 n 是 10 亿也就循环 30 多次。空间复杂度是 O(1)因为我们只用了几个临时变量没有存整个转换结果。这一点在 C 语言里尤其重要因为如果先转成字符串你就得提前开一个足够大的字符数组还得处理数组越界问题。3. 四种语言逐个击破Java JS Python C3.1 Java 实现Java 版本我写得很直白就用一个 count 变量累加完全不需要引入字符串处理。很多 Java 新手喜欢先转成字符串再用indexOf或者charAt去数其实完全没必要反而容易踩字符转数字的坑。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int k sc.nextInt(); int m sc.nextInt(); System.out.println(countDigit(n, k, m)); } public static int countDigit(int n, int k, int m) { // 如果 m 不在 k 进制的合法数字范围内直接返回 0 if (m 0 || m k) { return 0; } // n 0 时k 进制表示就是 0需要单独处理 if (n 0) { return m 0 ? 1 : 0; } int count 0; while (n 0) { int digit n % k; if (digit m) { count; } n / k; } return count; } }这里面有两点值得解释。第一m k的提前判断不是可有可无的它能让逻辑更严谨。第二n 0必须放在 while 循环前面处理否则循环不执行答案就会是 0而正确答案应该是当 m 为 0 时输出 1。如果你担心 n 特别大可以把int换成long方法签名也改成long n。在 Java 里用long做除法和取余没有任何问题只是在读入时要用nextLong()。3.2 JavaScript 实现JavaScript 版本同样建议手动实现进制转换。虽然 JS 内置了toString(radix)方法可以很方便地把数字转成任意进制字符串但它有两个问题第一toString得到的是字符串你仍然得遍历字符串去数字符底层还是得多做一层第二toString(2)这样的调用在数字很大时可能会有精度溢出问题因为 JS 的 Number 是浮点数超过Number.MAX_SAFE_INTEGER就不精确了。所以老老实实写循环反而最稳。function countDigit(n, k, m) { // 输入合法性检查 if (m 0 || m k) { return 0; } if (n 0) { return m 0 ? 1 : 0; } let count 0; while (n 0) { const digit n % k; if (digit m) { count; } // 注意这里必须用 Math.floor确保是整数除法 n Math.floor(n / k); } return count; } // 测试 console.log(countDigit(10, 2, 0)); // 2JS 新手最容易犯的错误是直接写n n / k。在 JS 里/运算符做的是浮点数除法比如10 / 2得到 5这没问题但9 / 2会得到 4.5。如果你不Math.floor下一轮17 % 2之类的结果就会全乱掉。所以务必写成Math.floor(n / k)。如果你真的很喜欢toString那我也给一个参考写法function countDigitWithToString(n, k, m) { if (n 0) { return m 0 ? 1 : 0; } const s n.toString(k); let count 0; for (const ch of s) { // 将字符转成数字注意处理 a-f 这类字母 const digit parseInt(ch, k); if (digit m) { count; } } return count; }这个写法在 k 小于等于 10 时能正常工作但如果 k 大于 10就会遇到字母。比如十六进制里a代表 10parseInt(a, 16)会得到 10但你要统计的 m 如果是 10逻辑上仍然成立。只是这种写法多了一层字符解析性能不如手动取余。3.3 Python 实现Python 的写法是最干净的因为它语法简洁而且整数除法//和取余%的语义非常明确。尤其要注意Python 3 里/是浮点除法//才是整除一定要用//。def count_digit(n: int, k: int, m: int) - int: # 如果 m 不可能是 k 进制中的数字直接返回 0 if m 0 or m k: return 0 # n 0 的特殊处理 if n 0: return 1 if m 0 else 0 count 0 while n 0: digit n % k if digit m: count 1 n // k return count if __name__ __main__: print(count_digit(10, 2, 0)) # 2Python 里还可以用divmod一次性同时得到商和余数让代码更紧凑def count_digit_divmod(n: int, k: int, m: int) - int: if m 0 or m k: return 0 if n 0: return 1 if m 0 else 0 count 0 while n: n, digit divmod(n, k) if digit m: count 1 return countdivmod(n, k)返回一个元组第一个是整除后的商第二个是余数。把n重新赋值为商digit保存余数一行代码完成两件事。不过这个写法对不熟的读者可能有点绕建议在面试中还是用%和//更直观。Python 还有一个优势就是它原生支持大整数不会像 C/Java 那样担心int溢出。所以即使 n 给到 10^18这个函数照样能算出正确结果。3.4 C 语言实现C 语言是这个题目的“原教旨”解法。因为进制转换本来就是计算机底层最常做的事情用 C 写反而最顺手。C 的整数除法/本身就是向零取整所以不用担心n n / k会变成小数。#include stdio.h int countDigit(int n, int k, int m) { if (m 0 || m k) { return 0; } if (n 0) { return m 0 ? 1 : 0; } int count 0; while (n 0) { int digit n % k; if (digit m) { count; } n / k; } return count; } int main() { int n, k, m; scanf(%d %d %d, n, k, m); printf(%d\n, countDigit(n, k, m)); return 0; }这里没什么花哨的技巧唯一要提醒的是变量类型。如果 n 的范围可能超过int的最大值约 21 亿建议把int改成long long对应的scanf和printf也要改成%lld。例如long long countDigit(long long n, int k, int m) { ... }C 语言不像 Java 或 Python 那样有字符串的便利方法但这道题根本不需要转换成字符串直接用余数比较数字大小即可。这也再次说明了“边转换边统计”的思路有多省事。3.5 四种语言横向对比语言核心代码量主要易错点推荐场景Java中输入输出模板稍长int 可能溢出企业应用开发、机考主流语言JavaScript短/是浮点除法忘记Math.floor会导致死循环前端岗笔试、算法练习Python最短忘记用//整除想当然用内置函数处理带前缀的字符串快速验证思路、算法学习C短数据范围控制scanf/printf 格式符底层原理学习、竞赛基础其实四种语言的核心逻辑一模一样差别只在于语法表达。这就是为什么我建议刷题时同一道题用不同语言各写一遍能帮你把语言特性记得更牢固。4. 边界情况与隐藏陷阱这些坑我帮你们踩过了4.1 边界情况速查表下面这个表是我整理出来的常见边界情况基本覆盖了这道题 80% 的隐藏失分点。输入情况正确答案常见错误n0, k2, m010因为 while 循环没执行n0, k2, m101误认为 0 的二进制包含 1n5, k2, m30死循环忘记 m 不在 k 进制中n100, k10, m021100 的十进制里有 2 个 0n1, k2, m110二进制 1 中恰好有 1 个 1n255, k16, m1510十六进制 FF 中的 F 代表 15第 5 行看起来简单但确实有人会在 n1 的时候把答案写成 0因为循环只执行一次而他们把条件写成了digit m n ! 1这种多余判断。第 6 行比较特殊。如果 k16m15那么 n255 转十六进制是FF每一位都是 15所以答案应该是 2。如果你用的是字符串遍历方案要注意parseInt(F, 16)的结果确实是 15而不是 0。当然大部分题目里 m 都是 0-9k 也不超过 10这个例子主要是提醒大家进制扩展后的处理逻辑。4.2 为什么 n0 是最大的坑我特地把它单独拎出来说因为网上的题解里十个有八个会忘记处理 n0。很多人一看到n % k就默认 n 是正整数结果样例全是正数自测也全过等交上去发现某个隐藏用例挂了。0 在任何进制下都写作0。所以如果 m0答案是 1如果 m 不等于 0答案是 0最简单的处理方式就是在函数开头单独判断if (n 0) { return m 0 ? 1 : 0; }这行代码你可以在所有语言里都写上。没坏处还能防止后面循环直接跳过。4.3 m 的合法性判断我遇到不少人在拿到题目后没仔细看数据范围直接开始写循环。假如 m 大于等于 k比如 k2, m3那么 while 循环里永远不可能出现 digit 3但程序会老老实实地把整个循环跑完然后返回 0。虽然结果碰巧对但万一 m 是个负数或者在某些特殊进制下 m 的表示涉及字母就会出麻烦。稳妥的做法是在开头加一句if (m 0 || m k) { return 0; }别小看这行代码它能让你的逻辑闭环并且向阅卷人传递一个信号你注意到了数字范围这个关键约束。4.4 语言层面的数据溢出问题这道题如果输入范围只是 10^9 以内用 int 完全够。但有些机考题目会悄悄把数据范围拉大尤其是 Python 玩家往往容易忽略其他语言的溢出问题。C 语言int最大约 21 亿有符号 32 位如果 n 可能超过 10^9建议直接用long long宁可多占 4 个字节也别冒险。Javaint同样有 21 亿上限读入时可以用long但Scanner.nextLong()和nextInt()别用混了。JavaScriptJS 的 Number 是双精度浮点数超过2^53 - 1就不安全了。如果题目说 n 可以达到 10^18JS 需要借助BigInt类型写成BigInt(n)然后所有除法、取余都要换用 BigInt 的方法这就复杂多了。好在大多数考 JS 的场景数据范围不会那么变态。Python自带大整数无限位不用管溢出这是 Python 在这道题里最大的优势。4.5 内置进制转换方法的隐藏坑Python 的bin(n)会返回0b1010这种带前缀的字符串oct(n)返回0o...hex(n)返回0x...。如果你直接拿bin(n)去数 0前缀里的0b里的 0 也会被数进去结果就会多 1。JavaScript 的n.toString(2)没有前缀但得到的是字符串你要数 0 就得遍历字符串而且如果 m 是数字 10你还得先把字符a转成数字 10多一层麻烦。C 语言没有内置进制转换函数一切都要自己写所以反而不会踩这种坑。Java 的Integer.toString(n, k)可以转成指定进制字符串但同样返回字符串需要遍历字符。所以我的最终建议是在笔试或机考中手动实现除 k 取余法不要依赖内置的进制转换方法。内置方法看着方便一旦涉及统计反而会让你多处理很多边角情况。5. 从这道题出发一个通用模板和它的变体5.1 把核心逻辑抽成函数这道题的价值不在于背代码而在于你能掌握“进制转换 逐位处理”这个万能模板。下面这个模板适用于所有语言func countDigit(n, k, m): if m 0 or m k: return 0 if n 0: return (m 0) ? 1 : 0 count 0 while n 0: digit n % k if digit m: count 1 n n / k # 整除 return count只要把n、k、m换成别的变量名就能套用到很多相似题目上。比如“给定 n 和 k求 n 在 k 进制下各位数字之和”“求 n 在 k 进制下最高位是什么”“判断 n 在 k 进制下是否包含某个数字”。5.2 三个典型变体变体一直接求 k 进制下各位数字之和。int digitSum(int n, int k) { if (n 0) { return 0; } int sum 0; while (n 0) { sum n % k; n / k; } return sum; }变体二求 k 进制表示的最高位数字。这需要先算出有多少位或者用对数估算但最简单的做法是先循环一遍求出所有位存到数组里最后一个余数就是最高位。变体三判断 n 在 k 进制下是不是回文数。比如十进制 121 转二进制是1111001不是回文但十进制 5 转二进制是101是回文。这类题同样只需要在循环里把每位数字收集起来最后前后比较。所以你看一道“来自异国的客人”真正训练的是你处理进制的底层能力背景故事再花哨核心永远不变。5.3 自己动手做一次完整测试不管用哪种语言我建议你写完代码后至少跑下面这 5 组测试用例全对才说明这题你真的拿稳了。n10, k2, m0 - 2 n0, k2, m0 - 1 n0, k2, m1 - 0 n255, k16, m15 - 2 n100, k10, m0 - 2如果最后一组你觉得奇怪解释一下100 在十进制下是三位数100其中数字 0 出现了 2 次所以输出 2。很多人在这个用例上会错写成 1因为他们只考虑了末尾的 0忘了十位上的 0。6. 实操心得与答题策略6.1 机考/面试时如何稳拿这 100 分我在实际机考中总结了一套固定流程拿到这种题先不读故事直接做三件事第一在草稿纸上写下输入输出和示例数据。把题面里的样例手动算一遍确保自己理解正确。第二判断数据范围。如果 n 可能是 0先写特殊处理如果 m 可能越界先写合法性判断如果 n 很大选long或BigInt。第三写一个最朴素的循环版本不要一上来想优化。这种 100 分的题能用 O(log_k n) 的时间解出来已经满分了不需要什么奇技淫巧。按照这个流程我基本可以在 5 分钟内写完并调试完毕。剩下时间可以用来检查其他题。6.2 四种语言的调试差异这道题在四种语言里的调试体验差别很大我说一下自己的体感。C 语言最容易出问题的是格式符写错。scanf里写%d却传入long long的地址轻则读入错乱重则段错误。所以我在 C 里用到long long时会非常刻意地检查scanf和printf的格式符。Java 的调试麻烦主要在代码结构。你总不能把方法写在类外面所以我会先在本地写好一个完整的Main类结构然后专注于方法体逻辑。JavaScript 最经典的坑是浮点数除法我在本地跑的时候习惯在这个位置加一行console.log(n)如果发现出现小数就知道忘记Math.floor了。Python 的调试最舒服因为报错信息直观而且//和%的优先级很清晰。唯一要留意的是别把//写成/否则循环会退化成浮点数除法导致 n 永远减不到 0最后形成死循环。6.3 从这道题能学到什么很多同学刷题喜欢“广撒网”今天做链表明天做二叉树后天做动态规划结果每样都只懂个皮毛。像这种 100 分的简单题反而是吃透语言细节的好素材。用四种语言各写一遍你会不自觉地思考为什么 Python 写起来这么快为什么 C 没有字符串也能解为什么 Java 的int会有上限这些问题比题目本身更能提升你的工程能力。我个人刷题的习惯是每遇到一道值得做的题就会在本地建一个文件夹用solution.c、Solution.java、solution.js、solution.py四个文件分别保存同一份逻辑。几个月后再回看这些代码对比各语言的差异那种收获不是刷几道难题能比的。6.4 一个小技巧把 m 的判断写在最前面最后再分享一个个人小习惯。我会在countDigit函数的第一行就先判断m的合法性而不是等循环结束再处理。这不是为了性能而是为了让自己在读代码时一眼就能确认边界条件已经处理完。写这类基础题代码顺序很重要边界条件先处理主逻辑放中间这样不管你一个月后回来看还是交给其他人 review都不会觉得混乱。而且这个习惯在面试白板编程时特别加分。面试官如果看到你第一行就处理了m k和n 0一般会认为你考虑问题比较全面哪怕后面代码有小瑕疵印象分也会高不少。以上总结一下我对“来自异国的客人”这道题的所有经验。题目本身不难但它是一面很好的镜子能照出你对进制转换、边界判断和多语言语法的熟悉程度。如果你在机考或面试里碰到它希望这篇文章能帮你稳拿满分。