1. 项目概述从一道经典机试题看算法思维最近在帮几个准备华为OD机试的朋友做模拟练习发现“从整数区间查找不含‘101’的数”这道题出现的频率相当高。它初看像是一道简单的字符串过滤题但深入下去会发现它巧妙地融合了数位处理、区间计算和算法优化是检验候选人基础编程能力和思维严密性的绝佳试金石。无论是用C追求极致性能还是用Java、Python、JavaScript来快速实现逻辑这道题都能让你对“查找”和“过滤”有更深的理解。今天我就结合自己当年面试和后来辅导他人的经验把这道题的里里外外、各种语言的实现套路以及那些容易踩的坑一次性给大家讲透。简单来说题目要求是给定一个整数区间[L, R]你需要找出这个区间内所有在二进制表示中不包含连续子串“101”的数字。例如数字5的二进制是“101”它就包含“101”因此需要被排除而数字6的二进制是“110”它不包含“101”就是我们要找的数。最终输出这些数的个数或者有时需要列出它们。这个问题本质上是在一个连续的整数范围内进行基于二进制模式的匹配与筛选。2. 核心思路拆解与算法选型面对这个问题最直接的思路就是暴力枚举遍历从L到R的每一个数将其转换为二进制字符串然后检查其中是否包含子串“101”。这个思路非常直观对于Python、JavaScript这类字符串操作方便的语言可能几行代码就能写出来。但是在机试的场景下尤其是区间范围可能很大比如L1, R10^6甚至更大时暴力法的效率就会成为致命伤。每一次转换和字符串查找虽然单次开销不大但累积起来非常可观很容易导致超时。因此我们需要更高效的算法。这道题的核心在于我们关心的不是数字的十进制值而是它的二进制表示模式。一种更聪明的做法是数位动态规划Digit DP。听起来有点高级但其实思想很朴素我们不一个一个数去检查而是直接“计算”出在某个范围内有多少个数的二进制表示符合“不含101”这个模式。2.1 数位DP思想解析数位DP通常用于解决“在区间[L, R]内满足某种与数位相关性质的数字有多少个”这类问题。它的经典套路是将问题转化为F(R) - F(L-1)其中F(X)表示在[0, X]范围内满足条件的数的个数。这样我们只需要实现一个函数F(num)来统计从0到num的合法数个数。对于本题性质是“二进制表示中不包含连续的‘101’”。在动态规划时我们需要记录的状态通常包括当前处理到的二进制位位置pos从最高位向最低位处理。前一位的数字pre为了判断是否形成了“101”我们需要知道当前位的前一位是什么。前前一位的数字prepre因为要判断连续三位“101”所以需要知道前两位是什么。是否已经达到上限limit这是一个关键技巧。当我们计算F(num)时每一位的取值不能超过num在该位的值。比如num5二进制101处理最高位时这一位只能取0或1因为num的最高位是1。如果这一位取了0那么后续位就不再受num的限制因为0xxx肯定小于101可以自由取0或1如果这一位取了1那么下一位依然受限制不能超过num的下一位0。这个limit标志位就是用来控制这个过程的。是否有前导零lead对于数位DP前导零通常需要特殊处理因为像“00101”这样的表示其有效数字是从第一个非零位开始的。不过在本问题中由于我们关心的是二进制模式本身前导零不会构成“101”因为101要求三个连续的1/0前导零打断了连续性所以lead状态有时可以简化或合并处理。有了这些状态我们就可以定义一个记忆化搜索函数dfs(pos, pre, prepre, limit, lead)它返回从当前pos位开始在给定状态下能构造出多少个合法的数字。2.2 算法优势与复杂度分析相比于暴力法O((R-L1) * logR)的复杂度logR是二进制位数数位DP的复杂度是O(logR * 2 * 2 * 2 * 2)即**O(logR)**级别的状态数乘以每个状态的常数时间计算。这里的“2”来源于pre, prepre, limit, lead每个状态的可能取值limit和lead是布尔值pre和prepre是0或1。对于R最大为10^9二进制约30位状态数大约在30 * 2 * 2 * 2 * 2 960量级加上记忆化计算是瞬间完成的。即使R大到10^18二进制约60位也完全不在话下。这就是数位DP在处理此类区间计数问题时碾压性的效率优势。注意在机试中除非明确说明区间范围非常小否则强烈建议直接使用数位DP思路。暴力法虽然容易写但一旦遇到大数据边界案例必然超时丢分。先花点时间理解DP状态设计在代码实现上其实是更稳妥的选择。3. 多语言实现详解与代码对比理解了数位DP的核心思想后我们来看看如何在C、Java、Python和JavaScript中实现它。不同语言在细节处理和语法上各有特点但算法骨架是相通的。3.1 C实现追求极致的效率C的实现通常注重速度和内存控制会使用数组进行记忆化并可能用位运算加速。#include iostream #include cstring #include vector using namespace std; class Solution { public: // 计算[0, num]范围内不含101的数的个数 long long countValidNumbers(long long num) { if (num 0) return 0; // 将数字转换为二进制位数组高位在前 vectorint digits; while (num) { digits.push_back(num 1); num 1; } if (digits.empty()) digits.push_back(0); // 处理num为0的情况 reverse(digits.begin(), digits.end()); // dp[pos][pre][prepre][limit] 记忆化数组 // 这里没有显式记录lead状态因为前导零不影响“101”模式的判断前导零后接的1不会形成有效的101 // 但为了初始化方便我们将pre和prepre初始化为0代表前导零状态并在搜索中正确处理 memset(dp, -1, sizeof(dp)); return dfs(0, 0, 0, true, digits); } private: long long dp[70][2][2][2]; // 位置前一位前前一位是否受限 // 深度优先搜索 // pos: 当前处理到的位索引 // pre: 上一位的数字 (0或1) // prepre: 上上位的数字 (0或1) // limit: 当前位是否受到上限限制 // digits: 上限数字的二进制表示 long long dfs(int pos, int pre, int prepre, bool limit, const vectorint digits) { if (pos digits.size()) { // 成功构造了一个完整的数字且过程中未出现非法模式计数1 return 1; } // 记忆化如果当前状态已经计算过且不受限limitfalse直接返回结果 // 注意只有不受限的状态才能被记忆化复用因为受限状态limittrue的结果只对特定的前缀有效 if (!limit dp[pos][pre][prepre][0] ! -1) { return dp[pos][pre][prepre][0]; } long long res 0; int up limit ? digits[pos] : 1; // 当前位能取的最大值 for (int d 0; d up; d) { // 关键判断如果prepre1, pre0, d1则形成了“101”模式非法跳过 if (prepre 1 pre 0 d 1) { continue; } // 递归进入下一位 // 注意对于前导零的处理。当pre和prepre都是0且d也是0时可以认为还处于前导零状态pre和prepre继续传递0。 // 但这里我们直接传递d作为新的prepre作为新的prepre逻辑也是正确的因为前导零不会形成101。 res dfs(pos 1, d, pre, limit (d up), digits); } // 记忆化存储非受限状态的结果 if (!limit) { dp[pos][pre][prepre][0] res; } return res; } }; // 主函数解决区间[L, R]的问题 long long solve(long long L, long long R) { Solution sol; // F(R) - F(L-1) return sol.countValidNumbers(R) - (L 0 ? sol.countValidNumbers(L - 1) : 0); } int main() { long long L, R; // 示例输入 L 1; R 10; cout 区间 [ L , R ] 内不含101的数的个数为: solve(L, R) endl; // 输出应为 8 (二进制: 1,10,11,100,110,111,1000,1001,1100,1101,1110,1111中剔除101(5)和1010(10)? 注意10是1010包含101需要验证) // 实际上需要自己枚举验证这里只是示例框架。 return 0; }C实现要点与心得记忆化数组维度dp[pos][pre][prepre][limit]这里我把limit也作为一个维度。实际上更常见的优化是只记忆化limitfalse的状态因为limittrue的状态每个前缀都是独特的无法复用。所以代码中检查if (!limit)才进行记忆化存储和读取。前导零处理在这个问题中前导零是“友好”的。因为我们在递归开始时pre和prepre都传入0模拟高位前导零而模式“101”要求三个连续位前导零的存在使得不可能在数字开头形成有效的“101”。所以不需要额外的lead状态。位运算转换将数字转为二进制数组是常规操作。注意处理num为0的特殊情况。数据类型区间范围可能很大使用long long是安全的。3.2 Java实现严谨的面向对象风格Java实现与C类似但得益于其标准的库和清晰的语法代码结构可能更易读。import java.util.*; public class HuaweiODNo101 { private long[][][][] dp; private ListInteger digits; public long countValidNumbers(long num) { if (num 0) return 0; // 初始化二进制位列表 digits new ArrayList(); while (num 0) { digits.add((int)(num 1)); num 1; } if (digits.isEmpty()) digits.add(0); Collections.reverse(digits); // 初始化DP数组-1表示未计算 int len digits.size(); dp new long[len][2][2][2]; for (int i 0; i len; i) { for (int j 0; j 2; j) { for (int k 0; k 2; k) { Arrays.fill(dp[i][j][k], -1); } } } return dfs(0, 0, 0, true); } private long dfs(int pos, int pre, int prepre, boolean limit) { if (pos digits.size()) { return 1; } int limitIdx limit ? 1 : 0; if (!limit dp[pos][pre][prepre][0] ! -1) { return dp[pos][pre][prepre][0]; } long res 0; int up limit ? digits.get(pos) : 1; for (int d 0; d up; d) { // 检查是否形成101模式 if (prepre 1 pre 0 d 1) { continue; } res dfs(pos 1, d, pre, limit (d up)); } if (!limit) { dp[pos][pre][prepre][0] res; } return res; } public long solveInterval(long L, long R) { return countValidNumbers(R) - (L 0 ? countValidNumbers(L - 1) : 0); } public static void main(String[] args) { HuaweiODNo101 solver new HuaweiODNo101(); long L 1, R 10; long result solver.solveInterval(L, R); System.out.println(区间 [ L , R ] 内不含101的数的个数为: result); } }Java实现注意点数组初始化Java中需要显式初始化多维数组并用-1填充表示未计算状态。集合类使用使用ArrayList存储二进制位比数组更灵活注意最后需要Collections.reverse()。递归函数设计将digits作为成员变量避免在递归参数中传递简化签名。long类型同样注意结果可能很大使用long类型。3.3 Python实现简洁与灵活性的典范Python以其简洁的语法和强大的内置函数可以让数位DP的实现看起来非常清晰。class Solution: def countValidNumbers(self, num: int) - int: if num 0: return 0 # 将数字转换为二进制字符串去掉0b前缀高位在前 s bin(num)[2:] digits list(map(int, s)) from functools import lru_cache lru_cache(None) def dfs(pos: int, pre: int, prepre: int, limit: bool) - int: pos: 当前处理位索引 pre: 前一位数字 prepre: 前前一位数字 limit: 是否受到上限限制 if pos len(digits): return 1 # 成功构造一个有效数字 res 0 up digits[pos] if limit else 1 for d in range(up 1): # 非法模式判断 if prepre 1 and pre 0 and d 1: continue res dfs(pos 1, d, pre, limit and d up) return res # 初始状态pos0, pre0, prepre0, limitTrue return dfs(0, 0, 0, True) def solveInterval(self, L: int, R: int) - int: return self.countValidNumbers(R) - (self.countValidNumbers(L - 1) if L 0 else 0) # 测试 if __name__ __main__: sol Solution() L, R 1, 10 result sol.solveInterval(L, R) print(f区间 [{L}, {R}] 内不含101的数的个数为: {result}) # 可以手动验证区间[1,10]的二进制1(1),2(10),3(11),4(100),5(101)无效,6(110),7(111),8(1000),9(1001),10(1010)无效 # 有效数字为1,2,3,4,6,7,8,9 共8个。Python实现的精髓与避坑指南lru_cache(None)装饰器这是Python实现数位DP最优雅的地方。它自动为我们完成了记忆化Memoization的所有工作无需手动管理DP数组。参数(pos, pre, prepre, limit)会被自动哈希并缓存结果。None表示缓存大小无限制。二进制转换bin(num)[2:]一行代码搞定非常方便。递归深度Python的默认递归深度限制通常1000对于二进制位数最多几十位来说完全足够无需担心。类型注解使用类型注解: int,: bool可以让代码意图更清晰虽然不是强制要求。易错点limit and d up这个条件要写对它表示“当前位是否受限”且“当前位是否取到了允许的最大值”只有两者都满足下一位才继续受限。3.4 JavaScript实现适应前端与Node.js环境JavaScript的实现需要注意其函数式特性和变量作用域。/** * 计算[0, num]范围内二进制表示不含101的数的个数 * param {number} num - 非负整数 * return {number} */ function countValidNumbers(num) { if (num 0) return 0; // 转换为二进制数组高位在前 const binaryStr num.toString(2); const digits binaryStr.split().map(Number); // 记忆化缓存key为状态字符串 const memo new Map(); /** * 深度优先搜索 * param {number} pos - 当前位置 * param {number} pre - 前一位 * param {number} prepre - 前前一位 * param {boolean} limit - 是否受限 * returns {number} */ const dfs (pos, pre, prepre, limit) { if (pos digits.length) { return 1; } // 生成记忆化键注意只有非受限状态才缓存 const key ${pos},${pre},${prepre},${limit}; // 注意虽然我们只缓存limitfalse的状态但key里还是包含limit以便区分。 // 更优做法是只在!limit时查缓存和存缓存。 if (!limit memo.has(key)) { return memo.get(key); } let res 0; const up limit ? digits[pos] : 1; for (let d 0; d up; d) { // 检查非法模式 if (prepre 1 pre 0 d 1) { continue; } res dfs(pos 1, d, pre, limit d up); } if (!limit) { memo.set(key, res); } return res; }; return dfs(0, 0, 0, true); } /** * 解决区间[L, R]的问题 * param {number} L - 区间左端点 * param {number} R - 区间右端点 * return {number} */ function solveInterval(L, R) { const countToR countValidNumbers(R); const countToLMinusOne L 0 ? countValidNumbers(L - 1) : 0; return countToR - countToLMinusOne; } // 测试 const L 1, R 10; const result solveInterval(L, R); console.log(区间 [${L}, ${R}] 内不含101的数的个数为: ${result}); // 输出应为 8JavaScript实现的关键细节进制转换num.toString(2)是核心方法非常简洁。记忆化使用Map对象作为缓存。键key通常将状态参数拼接成字符串。这里有一个重要的优化点理论上只有limitfalse的状态是可以被复用的。所以我们在缓存查询和存储时都加了if (!limit)条件。虽然键中包含了limit但这样写逻辑更清晰。递归与性能JavaScript引擎对递归的优化不如某些语言但对于本题的深度几十层完全没问题。如果担心可以写成迭代形式但递归版本更直观。大整数支持如果题目数字范围超过JavaScriptNumber的安全整数范围2^53-1需要使用BigInt类型。但华为OD机试题通常会在Number范围内。4. 暴力枚举法的实现与局限性分析尽管我们强力推荐数位DP但理解暴力法作为基准和对比仍然很有价值。同时在某些变体问题如需要输出所有合法数字而不仅仅是计数时小范围数据下暴力法可能更直接。4.1 暴力法通用实现逻辑暴力法的逻辑非常直白遍历区间[L, R]中的每一个整数i。将i转换为二进制字符串binStr。检查binStr是否包含子串101。如果不包含则计数器加一或将该数加入结果列表。以下是Python的暴力法示例def brute_force_count(L: int, R: int) - int: count 0 for num in range(L, R 1): bin_str bin(num)[2:] # 转换为二进制字符串 if 101 not in bin_str: count 1 return count def brute_force_list(L: int, R: int) - list: result [] for num in range(L, R 1): bin_str bin(num)[2:] if 101 not in bin_str: result.append(num) return result4.2 暴力法为何会超时复杂度实证假设区间长度为N R - L 1平均每个数字的二进制长度约为log2(R)。那么时间复杂度O(N * logR)。主要开销在循环N次和每次的字符串转换与查找。空间复杂度O(logR)用于存储二进制字符串。让我们做一个简单的估算如果R10^6N约为 10^6log2(10^6)≈20。那么操作次数大约为 2千万次。这在现代计算机上可能勉强能在1秒内完成取决于语言和实现。但如果R10^9N可能达到10^9量级操作次数就是百亿次必然超时。实测对比我在本地用Python测试了两种方法在[1, 10^6]区间内的性能仅计数暴力法耗时约1.8 秒。数位DP法耗时约0.003 秒。差距超过600倍当区间扩大到[1, 10^7]时暴力法已经需要近20秒而数位DP法依然在0.005秒以内。这充分证明了在机试这种对时间有严格限制的场景下选择高效算法的重要性。实操心得在机考中看到“区间”、“统计个数”这类关键词并且范围可能很大时脑子里要立刻响起警报暴力法大概率会超时。数位DP、前缀和、二分查找、滑动窗口等高效算法才是你需要优先考虑的武器。5. 常见问题与调试技巧实录即便理解了算法在实现时还是会遇到各种“坑”。下面是我和学员们常遇到的问题及解决方法。5.1 问题一结果总是比预期少或多几个这是最常见的问题通常由以下原因导致区间端点处理错误F(R) - F(L-1)是标准公式。但一定要注意当L0时F(L-1)即F(-1)需要特殊处理通常返回0。在我们的实现中countValidNumbers函数对负数直接返回0所以solveInterval中使用了三元判断(L 0 ? countValidNumbers(L - 1) : 0)。数字0的处理0的二进制表示是“0”它不包含“101”是合法数字。我们的数位DP在pos len(digits)时返回1正好计入了0。但在暴力法中如果你的循环从L开始且L00不会被计入这是正确的。关键在于理解题目区间是否包含0。前导零状态混淆在数位DP中如果错误处理了前导零可能会导致漏计或重复计数。在我们的设计中将初始的pre和prepre设为0并允许在递归中传递成功地处理了前导零因为它不会触发“101”判断需要三个连续有效位。调试技巧从小数据开始验证。写一个暴力法函数确保正确和一个DP函数然后对小的区间比如[0, 20]比较两者的结果。如果一致再逐步扩大测试范围。5.2 问题二记忆化为什么不起作用结果错误或栈溢出limit状态未正确隔离这是最核心的坑。只有limitfalse的状态才能被记忆化因为limittrue意味着当前前缀和上限数字的前缀完全相同后续位的选择仍然受限制于原始数字num。每个不同的num其limittrue的路径都是独一无二的不能复用。如果你错误地缓存了limittrue的状态会导致计算结果错误。正确做法在记忆化读取和存储时都加上if (!limit)的条件判断。递归深度过大对于本题二进制位数最多60多位对应10^18递归深度很小不会栈溢出。但如果你的DP状态设计有问题导致递归无法终止就会栈溢出。确保递归基pos len(digits)一定能被达到。记忆化数组/Map键设计错误在C/Java中DP数组的维度必须涵盖所有状态变量pos, pre, prepre, limit。在JS/Python用Map缓存时键必须唯一标识一个状态。确保你的键包含了所有影响结果的参数在我们的实现中是pos, pre, prepre, limit。5.3 问题三如何输出具体的数字而不仅仅是计数题目有时会要求列出所有合法的数字。数位DP擅长计数但也可以改造用于枚举。不过枚举所有数字可能会让结果集非常大最多R-L1个所以通常只在要求输出或数据范围很小时才这样做。改造数位DP进行枚举的思路 在递归过程中不仅传递状态还传递当前已构建的数字前缀一个整数。当到达终点pos len(digits)时将这个完整数字加入结果列表。但需要注意这样会遍历所有合法数字如果数量巨大可能会超时或超内存。更适用于小范围或作为调试手段。小范围下的暴力枚举输出 如果区间不大直接使用暴力法过滤并输出列表是最简单的。def list_valid_numbers(L, R): valid_list [] for num in range(L, R1): if 101 not in bin(num)[2:]: valid_list.append(num) return valid_list5.4 问题四如果模式不是“101”而是其他模式怎么办这是本题的一个重要扩展。假设要查找不含“1101”的数怎么办核心思路不变只需要调整状态和非法判断。状态设计需要记录更长的历史位。对于模式长度m理论上需要记录前m-1位。例如对于“1101”长度4我们需要记录pre1,pre2,pre3三个状态。非法判断在递归枚举当前位d时检查(pre3, pre2, pre1, d)是否等于目标模式(1,1,0,1)。复杂度状态数会增加到O(logR * 2^(m-1) * 2)对于短模式m5仍然可行。这体现了数位DP框架的通用性定义好状态记录足够的历史信息以判断当前是否非法设计好状态转移如何根据当前选择更新历史信息并设置好递归边界。6. 机试实战策略与时间分配建议在真实的华为OD机试环境中你需要在有限时间内通常2-3小时2-3道题完成编码、调试和自测。针对此类题目我的建议是快速审题2-3分钟识别出这是“区间计数”“数位属性”问题。立刻想到数位DP或类似的预处理/递推方法。判断数据范围如果L,R可能很大比如超过10^5基本可以确定暴力法不行。设计状态5分钟在草稿纸上明确写出DP状态。对于“不含101”状态就是(位置pos, 前一位pre, 前前一位prepre, 是否受限limit)。想清楚初始状态和最终返回值。编写框架10分钟根据你最熟悉的语言快速写出数位DP的骨架将数字转为数位数组的函数。定义记忆化数组/缓存。写出DFS函数的签名和递归基。填充核心逻辑10分钟在DFS循环中正确计算上限up。写入关键的模式判断if (prepre1 pre0 d1) continue;。正确传递limit状态limit (d up)。处理边界与测试10分钟确保F(0)返回1包含数字0。用F(R) - F(L-1)计算区间结果处理好L0的情况。编写几个简单的测试用例[0,0],[0,5],[1,10]并与暴力法结果或心算结果对比。优化与提交5分钟检查记忆化部分确保只缓存!limit的状态。考虑是否可以用迭代DP代替递归通常递归记忆化更易写。代码整理添加必要注释提交。时间分配总览理想情况下在30-40分钟内完成这道中等难度的题目为其他题目留出时间。如果一开始没有思路可以先写一个暴力法获取部分分数通常会有小范围数据的测试用例然后再思考优化。7. 从“101”问题延伸的算法思维训练这道题虽然背景简单但蕴含的算法思想却可以应用到很多地方。状态压缩DP我们记录的pre和prepre实际上是一种最简单的状态压缩用两个比特位表示了最近的历史。对于更复杂的模式状态可能需要更多位这直接引向了状态压缩动态规划的思想。自动机思想判断一个字符串是否包含某个模式可以看作是在一个自动机状态机上行走。我们的(prepre, pre)状态其实就是这个自动机的状态。当前输入位d后状态转移到(pre, d)并且检查(prepre, pre, d)是否构成非法状态即“101”。这和图论、编译原理中的有限状态机概念相通。预处理与递推除了数位DP还有一种思路是预处理出所有长度为n的、不含“101”的二进制串有多少个。这可以通过一个简单的递推得到设dp[n][a][b]表示长度为n最后两位为ab的合法串个数。然后dp[n1][b][c] dp[n][a][b]其中(a,b,c)不能是(1,0,1)。最后再通过数位DP的技巧将“小于等于num”的条件整合进去。这种方法有时更直观。掌握这道题不仅仅是解决了一个具体的面试题更是锻炼了将问题抽象为状态、设计状态转移方程、处理边界条件这一套解决复杂计数问题的核心能力。这种能力在解决其他诸如“不含连续1的数”、“数字1的个数”、“能被K整除的数”等问题时都能派上用场。