1. 这道题到底在考什么第一次看到“Radix”这个词很多人会以为是考进制转换的模板题心想“不就是把十进制转成其他进制嘛有什么难的”。我当初也是这么想的结果提交之后一堆测试点过不去才发现这题真正的坑根本不在进制转换本身而在于如何在一个极大的搜索空间里高效地找到那个唯一的解。这道题的核心场景是这样的给你两个数告诉你其中一个是另一个在某个未知进制下的表示让你求这个未知进制是多少。如果存在多个可能的进制输出最小的那个如果不存在输出“Impossible”。听起来很简单对吧但问题在于这个未知进制的范围可能非常大暴力枚举一定会超时。我后来复盘了一下这道题实际上考察的是三个能力的组合进制转换的边界处理、二分查找的设计、以及大数溢出的判断。任何一个环节出问题都会导致部分测试点挂掉。而且这道题的测试数据设计得非常刁钻几乎把你能想到的所有边界情况都覆盖了。适合谁来参考这篇内容呢如果你正在刷算法题尤其是准备一些编程能力测试这道题绝对值得反复琢磨。即使你不刷题这篇内容里关于二分查找边界设计和溢出处理的思路在实际工程中处理数值范围搜索、配置参数调优等场景时同样适用。2. 核心思路拆解与方案选型2.1 为什么不能暴力枚举最直观的想法是从最小的可能进制开始一个一个往上试直到找到匹配的进制。但问题是这个进制的上界可能非常大。假设已知的那个数在十进制下是 10^18 级别那未知进制可能达到 10^18 甚至更大。暴力枚举的时间复杂度是 O(n)其中 n 是进制范围这在任何在线评测系统里都不可能通过。所以我们需要一种更高效的搜索方式。这里的关键洞察是对于一个固定的数字字符串它在不同进制下表示的十进制值是单调递增的。也就是说进制越大转换出来的十进制值就越大。这个单调性就是二分查找的基础。2.2 二分查找的上下界怎么定二分查找最难的部分从来不是二分本身而是上下界的确定。这道题尤其如此。下界的确定未知进制至少要比这个数中出现过的最大数字大 1。比如一个数里出现了字符 ‘a’那它至少是 11 进制因为 ‘a’ 代表 10。如果只出现了 ‘0’ 到 ‘9’那最小进制就是最大数字加 1。这个逻辑很直观如果一个数是 11 进制那每一位最大只能是 10不可能出现 11 这个数字。上界的确定这是很多人容易搞错的地方。上界不能随便设一个很大的数因为如果设得太大二分过程中计算转换值时会溢出如果设得太小可能覆盖不到正确答案。一个常用的策略是上界取已知数的十进制值和下界中的较大值。为什么因为如果未知进制大于已知数的十进制值那未知数转换出来的值一定大于已知数除非未知数只有一位而我们要找的是相等的情况所以上界不需要超过已知数的十进制值。但这里有个特殊情况如果未知数只有一位那它在任何进制下的值都是一样的。比如未知数是 “5”那不管进制是多少它的值都是 5。这种情况下只要已知数也等于 5那最小合法进制就是答案。2.3 溢出问题怎么处理在二分查找的过程中我们需要把未知数从当前进制转换成十进制然后和已知数比较。但问题是如果进制很大转换出来的十进制值可能超出 64 位整数的范围导致溢出。溢出之后值可能变成负数或者一个很小的正数这会让比较结果完全错误。处理溢出的常见做法有两种一种是用更大的数据类型比如某些语言支持的大整数另一种是在计算过程中提前判断是否已经超过了已知数。第二种方法更通用也更高效。具体来说在逐位转换的过程中如果当前累积的值已经大于已知数就可以直接返回一个“过大”的标志不需要继续算下去。3. 核心细节与实操要点3.1 进制转换的正确写法进制转换看起来简单但细节很多。假设我们要把字符串 s 从进制 radix 转换成十进制基本逻辑是def to_decimal(s, radix): result 0 for ch in s: if ch.isdigit(): digit ord(ch) - ord(0) else: digit ord(ch) - ord(a) 10 result result * radix digit return result这段代码本身没问题但问题在于result * radix digit这一步可能会溢出。在 Python 里不用担心因为 Python 的整数是任意精度的。但如果你用 C 或 Java就需要特别处理。一个实用的技巧是在每次乘法之前先判断result是否已经大于(已知数 - digit) / radix。如果大于说明下一步一定会超过已知数直接返回一个标记值即可。注意这个判断条件里的除法是整数除法需要小心边界。更安全的写法是用乘法判断如果result (target - digit) / radix则溢出。但除法可能引入精度问题所以更好的方式是直接判断result * radix digit target但这又回到了溢出问题。折中方案是用result (target - digit) // radix在 Python 里这样写是安全的。3.2 二分查找的边界更新二分查找的模板有很多种但这道题推荐使用“左闭右闭”的写法因为这样最容易处理边界lo min_radix hi max(min_radix, target_decimal) while lo hi: mid (lo hi) // 2 val to_decimal(unknown, mid) if val target_decimal: # 找到答案但可能还有更小的进制 hi mid - 1 elif val target_decimal: lo mid 1 else: hi mid - 1注意这里找到答案后不是直接返回而是继续往左找因为题目要求输出最小的进制。这个细节很多人会忽略导致输出不是最小的那个。3.3 特殊情况的处理这道题有几个特殊情况需要单独处理情况一未知数只有一位。前面提到过这种情况下任何进制下的值都一样。所以只需要判断这一位的值是否等于已知数如果等于输出最小合法进制即这一位的值加 1但如果这一位的值就是已知数那最小进制就是这一位的值加 1但要注意如果这一位的值是 0那最小进制是 2因为进制至少是 2。情况二已知数和未知数相同。比如两个数都是 “10”那最小进制就是 2因为 ‘1’ 和 ‘0’ 都合法。但如果两个数都是 “1”那最小进制是 2。情况三进制下界大于上界。这种情况说明不存在合法进制直接输出 “Impossible”。4. 完整实操流程与代码实现4.1 整体流程设计整个算法的流程可以分成以下几步读入两个字符串和一个 tag以及一个 radix。根据 tag 确定哪个是已知数哪个是未知数。把已知数从给定的 radix 转换成十进制。确定未知数的最小合法进制。确定二分的上界。在上下界之间二分查找找到最小的满足条件的进制。输出结果或 “Impossible”。4.2 关键步骤的代码实现先来看进制转换函数这里用 Python 实现因为 Python 不用担心溢出问题def to_decimal(s, radix): result 0 for ch in s: if 0 ch 9: digit ord(ch) - ord(0) else: digit ord(ch) - ord(a) 10 if digit radix: return -1 # 非法数字 result result * radix digit return result然后是找最小合法进制def find_min_radix(s): max_digit 0 for ch in s: if 0 ch 9: digit ord(ch) - ord(0) else: digit ord(ch) - ord(a) 10 max_digit max(max_digit, digit) return max_digit 1接下来是二分查找的主体def solve(s1, s2, tag, radix): if tag 1: known, unknown s1, s2 else: known, unknown s2, s1 target to_decimal(known, radix) if target 0: return Impossible lo find_min_radix(unknown) hi max(lo, target) ans None while lo hi: mid (lo hi) // 2 val to_decimal(unknown, mid) if val target: ans mid hi mid - 1 elif val target: lo mid 1 else: hi mid - 1 return str(ans) if ans is not None else Impossible4.3 参数选择与边界验证在实际测试中有几个边界值需要特别验证测试场景输入示例期望输出说明未知数只有一位“5” “5” 1 106最小进制是 6已知数为 0“0” “0” 1 102进制至少是 2进制下界大于上界“1” “2” 1 10Impossible不存在合法进制大数情况“zzzzzzzzzz” “zzzzzzzzzz” 1 3636最小进制是 36需要二分查找“1” “10” 1 10210 在 2 进制下是 2提示在验证大数情况时注意 Python 的整数运算虽然不会溢出但计算量可能很大需要确保二分次数在合理范围内。由于上界可能达到 10^18二分次数大约是 60 次左右完全在可接受范围内。5. 常见问题与排查技巧实录5.1 为什么我的二分查找总是死循环死循环通常是因为边界更新写错了。最常见的问题是mid的计算方式导致lo和hi无法正确收敛。比如如果你写的是mid (lo hi) // 2然后更新时写lo mid而不是lo mid 1就可能死循环。解决方法是确保每次更新边界时区间一定会缩小。具体来说如果val target说明mid太小需要增大下界所以lo mid 1如果val target说明mid太大需要减小上界所以hi mid - 1。只有val target时才需要特殊处理继续往左找。5.2 为什么有些测试点输出不是最小进制这是因为找到答案后直接返回了没有继续往左搜索。题目要求输出最小的进制所以在找到第一个满足条件的进制后还需要继续在左半区间搜索直到找到最小的那个。我当初就是在这里栽了跟头提交了好几次都是部分正确。后来加了一行hi mid - 1就过了。5.3 溢出问题怎么排查如果你用的是 C 或 Java溢出是最常见的问题。排查方法是在进制转换函数里加一个判断如果当前累积值已经大于已知数就直接返回一个特殊值比如 -1 或者一个很大的数然后在二分比较时把这个特殊值当作“过大”处理。在 Python 里虽然不会溢出但计算量可能很大。如果发现程序运行超时可以检查一下二分上界是否设得太大。上界不需要超过已知数的十进制值因为如果进制大于已知数的十进制值未知数转换出来的值一定大于已知数除非未知数只有一位。5.4 常见问题速查表问题现象可能原因解决方法部分测试点超时二分上界设得太大上界取max(下界, 已知数十进制值)输出不是最小进制找到答案后直接返回继续往左搜索hi mid - 1结果错误或负数整数溢出在转换过程中提前判断是否超过已知数未知数只有一位时出错没有单独处理单独判断这一位的值是否等于已知数进制下界计算错误没有考虑最大数字下界 最大数字 1最小为 2注意如果已知数是 “0”那它的十进制值就是 0此时上界应该取max(下界, 0)也就是下界本身。这种情况下二分区间只有一个值直接判断即可。6. 进阶优化与经验总结6.1 如何进一步优化性能虽然二分查找已经把时间复杂度降到了 O(log N)但在某些极端情况下进制转换本身的开销也不小。如果未知数很长比如 10 位以上每次转换都需要遍历整个字符串二分的总开销就是 O(L log N)其中 L 是字符串长度。一个优化思路是在转换过程中提前终止。如果当前累积值已经大于已知数就不需要继续计算后面的位了。这个优化在进制很大的时候特别有效因为前几位就可能超过已知数。另一个优化是如果未知数的长度大于已知数的长度那在大多数情况下可以直接判断为 “Impossible”除非未知数只有一位。因为一个更长的数在相同进制下一定更大除非进制很小。但这个优化需要小心处理因为进制很小的时候长数也可能等于短数。6.2 我在实际调试中的几点体会第一不要相信自己的直觉。我一开始觉得上界取 10^18 就够了结果发现有些测试点的答案比这个还大。后来改成取已知数的十进制值才全部通过。第二边界情况一定要单独测试。这道题的测试数据里有很多边界情况比如未知数只有一位、已知数为 0、进制下界等于上界等等。这些情况如果不单独处理很容易出错。第三Python 虽然方便但要注意性能。Python 的任意精度整数虽然不会溢出但大数运算的速度比固定精度整数慢很多。如果发现超时可以尝试用一些技巧减少大数运算的次数。6.3 这道题对实际工作的启发这道题表面上是算法题但背后的思路在实际工作中很有用。比如在配置参数调优时我们经常需要在一个范围内搜索最优参数而目标函数往往是单调的。这时候二分查找就是最有效的工具。另外溢出处理也是实际工程中常见的问题。在处理金融数据、科学计算等场景时数值范围可能超出常规数据类型的表示范围提前判断和处理溢出是保证程序正确性的关键。最后再分享一个小技巧在写二分查找时可以先用小数据量暴力验证一遍确认逻辑正确后再改成二分。这样能快速定位问题是出在二分逻辑上还是其他部分。我在调试这道题时就是这么做的先用暴力枚举跑了一遍小数据确认进制转换和边界处理没问题后再改成二分一次就过了。