1. 项目概述从一道华为OD机试题说起最近在准备华为OD机试或者关注算法题的朋友可能都刷到过这道题“在给定区间内不含101的数”。题目本身描述很简洁但背后涉及到的二进制数位处理、区间计数技巧以及如何高效地在不同编程语言中实现都是非常值得深挖的实战考点。这道题不仅是华为OD机试的常客其变体也出现在吉林大学、中科大等高校的夏令营机试中足以见得其作为考察候选人基础算法和思维严谨性的“试金石”地位。简单来说题目要求我们给定一个整数区间[L, R]我们需要统计在这个区间内所有在二进制表示下不包含连续子串“101”的正整数个数。例如数字5的二进制是101它就包含“101”因此需要被排除而数字6的二进制是110它不包含连续的“101”所以是有效的。这个问题初看可能觉得直接遍历区间、逐个数字转换二进制判断就行但一旦区间范围很大比如L1, R10^9这种暴力解法的时间复杂度是O(N * logN)必然会超时。因此核心挑战在于如何设计一个亚线性甚至对数级时间复杂度的算法。本文将从一个资深开发者的视角彻底拆解这道题。我会先带大家理解问题本质然后深入讲解一种高效的通解思路——数位动态规划Digit DP并分别用C、Java、JavaScript和Python四种语言实现。更重要的是我会分享在实现过程中不同语言特性带来的编码差异、常见的“坑点”以及调试技巧。无论你是正在备战华为OD还是想巩固数位DP这一重要算法思想这篇文章都将提供一份可直接“抄作业”的详细指南。2. 问题核心与高效算法选型为什么暴力解法不行我们简单算一笔账。假设区间是[1, 10^9]遍历需要10^9次循环。每次循环需要将数字转为二进制字符串或进行位运算判断转换复杂度约为O(logN)对于10^9这个量级logN约等于30。那么总操作次数粗略为3 * 10^10量级这在任何机试环境通常限制1~2秒下都是不可接受的。因此我们必须寻找更聪明的方法。这道题的本质是一个数位统计问题。我们不再关心每个具体的数而是关心在某个数位范围内满足特定条件二进制不含“101”的数的“形态”有多少种。这立刻让人联想到数位动态规划Digit DP。数位DP是解决此类“区间内满足某条件的数字个数”问题的标准且强大的武器。它的核心思想是将数字看作一个数字串这里是二进制串从高位到低位进行决策利用动态规划记录在某个位置、处于某种状态下的方案数从而避免了对每个数字的独立检查。具体到“不含101”这个条件我们需要在状态设计中捕捉到“当前已匹配到了‘101’模式中的哪一位”。我们可以定义一个状态statestate 0: 当前末尾还没有形成“101”的前缀或者上一个位不是‘1’。state 1: 当前末尾是‘1’即匹配到了“101”的第一个字符‘1’。state 2: 当前末尾是“10”即匹配到了“101”的前两个字符“10”。 当我们在某一位填入‘1’且当前状态为2即前两位是“10”时就形成了完整的“101”此时这个分支就应该被禁止方案数为0。有了这个状态定义我们就可以构建DP记忆化搜索函数dfs(pos, state, isLimit, isNum)。pos: 当前正在处理二进制串的第几位从最高位向最低位处理。state: 上述定义的匹配状态0, 1, 2。isLimit: 布尔值表示当前位是否受到区间上界的限制。例如区间上界R的二进制是1101当我们决策的高位已经和R的高位完全相同时下一位的选择就不能超过R对应位置的值0或1否则就会超过R。isNum: 布尔值表示当前是否已经开始构造数字即是否跳过了前导零。这对于处理数字0和保证我们统计的是正数很重要。函数返回从pos位开始在给定state和限制条件下能构造出的合法数字个数。通过递归搜索所有可能的位置和状态并利用记忆化避免重复计算我们可以将时间复杂度降至O(logR * 3 * 2 * 2)对于R最大为10^9二进制位约30位这个计算量微乎其微。注意这里有一个初学者极易混淆的点。数位DP的“记忆化”必须配合isLimit和isNum这两个参数。只有当!isLimit isNum时当前(pos, state)的结果才可以被缓存memoize。因为isLimittrue意味着后续选择受限于上界R这个结果是针对当前这条特定路径的不能被其他路径复用isNumfalse意味着还在处理前导零状态state可能没有意义因为前导零不参与“101”模式的匹配。忽略这个条件会导致错误计数。3. 核心算法实现与四语言代码解析理解了算法框架接下来我们看具体实现。我将以C、Java、JavaScript和Python四种语言分别实现并重点分析每种语言在实现数位DP时的细微差别和最佳实践。首先我们定义一个公共的解题函数countValidNumbers(L, R)它返回区间[L, R]内不含101的数的个数。我们可以利用数位DP计算[0, X]内合法数的个数f(X)那么答案就是f(R) - f(L-1)。3.1 C 实现详解C以其高效的执行速度和丰富的标准库常作为算法竞赛的首选。实现数位DP时我们通常使用递归记忆化。#include bits/stdc.h using namespace std; class Solution { private: int memo[32][3]; // 记忆化数组pos范围[0,31]state范围[0,2] vectorint digits; // 存储数字X的二进制位从高位到低位 // DFS函数构造从pos位开始当前状态为state是否受上限限制isLimit是否已开始构造数字isNum的合法方案数 int dfs(int pos, int state, bool isLimit, bool isNum) { if (pos digits.size()) { // 递归终点如果已经构造了一个数字isNum为真则算一种方案空数字0不算 return isNum ? 1 : 0; } // 记忆化只有在无限制且已开始构造数字时结果才是通用的可以缓存 if (!isLimit isNum memo[pos][state] ! -1) { return memo[pos][state]; } int res 0; // 计算当前位可以填的上界 int up isLimit ? digits[pos] : 1; // 二进制位只能是0或1 // 尝试填入0或1 for (int d 0; d up; d) { int nextState state; if (isNum || d 1) { // 只有开始构造数字或当前位填1时才更新状态 if (state 0) { nextState (d 1) ? 1 : 0; } else if (state 1) { nextState (d 0) ? 2 : 1; // 前一位是1当前填0则状态变为210 } else { // state 2 if (d 1) { // 形成“101”非法分支跳过 continue; } else { nextState 0; // 填0则破坏“10”序列状态重置 } } } else { // 还在前导零阶段状态保持为0 nextState 0; } // 递归到下一位更新限制条件当前位若达到上限且d等于上限值则下一位继续受限 bool nextLimit isLimit (d up); // 更新是否已开始构造数字如果之前已开始或者当前位填了1跳过了前导零则isNum为真 bool nextIsNum isNum || (d 1); res dfs(pos 1, nextState, nextLimit, nextIsNum); } // 缓存结果 if (!isLimit isNum) { memo[pos][state] res; } return res; } // 辅助函数计算[0, X]范围内合法数的个数 int f(int X) { if (X 0) return 0; memset(memo, -1, sizeof(memo)); // 初始化记忆化数组为-1 digits.clear(); // 将X转换为二进制位列表高位在前 while (X) { digits.push_back(X % 2); X / 2; } reverse(digits.begin(), digits.end()); // 反转得到从高位到低位的顺序 if (digits.empty()) digits.push_back(0); // 处理X为0的情况 // 从最高位开始DFS初始状态未开始构造数字isNumfalse状态为0受上限限制 return dfs(0, 0, true, false); } public: int countValidNumbers(int L, int R) { // 题目要求统计正整数所以L至少为1。我们计算[0,R] - [0,L-1] return f(R) - f(L - 1); } }; // 示例用法 int main() { Solution sol; cout sol.countValidNumbers(1, 10) endl; // 应输出区间[1,10]内不含101的数的个数 return 0; }C实现要点与避坑指南记忆化数组初始化memo数组必须用-1初始化因为方案数可能为0用0初始化会与“未计算”状态冲突。使用memset(memo, -1, sizeof(memo))是最佳实践。二进制转换注意我们通过循环取余和除法得到的是从低位到高位的顺序必须用reverse反转以满足DFS从高位开始处理的需求。状态转移逻辑这是最容易出错的部分。务必注意只有在isNum为真已经开始构造数字或者当前位d1即用‘1’打破了前导零时我们才需要根据state和d更新nextState。否则说明我们还在前导零阶段nextState应保持为0不参与“101”模式的匹配。递归终点当pos digits.size()时我们成功走到了最低位之后此时如果isNum为真说明我们构造了一个有效的数字至少有一个非前导零的位返回1否则说明我们构造的是全零即数字0根据题目要求通常统计正整数返回0。3.2 Java 实现详解Java的实现与C类似但由于Java没有全局数组的便捷初始化且使用类封装代码结构会稍有不同。import java.util.*; public class Solution { private int[][] memo; private ListInteger digits; private int dfs(int pos, int state, boolean isLimit, boolean isNum) { if (pos digits.size()) { return isNum ? 1 : 0; } if (!isLimit isNum memo[pos][state] ! -1) { return memo[pos][state]; } int res 0; int up isLimit ? digits.get(pos) : 1; for (int d 0; d up; d) { int nextState state; if (isNum || d 1) { if (state 0) { nextState (d 1) ? 1 : 0; } else if (state 1) { nextState (d 0) ? 2 : 1; } else { // state 2 if (d 1) { continue; // 形成101跳过 } else { nextState 0; } } } else { nextState 0; } boolean nextLimit isLimit (d up); boolean nextIsNum isNum || (d 1); res dfs(pos 1, nextState, nextLimit, nextIsNum); } if (!isLimit isNum) { memo[pos][state] res; } return res; } private int f(int X) { if (X 0) return 0; // 初始化记忆化数组二进制位数最多32位int范围 memo new int[32][3]; for (int i 0; i 32; i) { Arrays.fill(memo[i], -1); } digits new ArrayList(); // 将X转为二进制列表 int temp X; if (temp 0) { digits.add(0); } else { while (temp 0) { digits.add(temp % 2); temp / 2; } Collections.reverse(digits); } return dfs(0, 0, true, false); } public int countValidNumbers(int L, int R) { return f(R) - f(L - 1); } public static void main(String[] args) { Solution sol new Solution(); System.out.println(sol.countValidNumbers(1, 10)); // 测试 } }Java实现差异与注意点数组初始化Java中二维数组memo需要手动循环初始化使用Arrays.fill(memo[i], -1)。注意memo的大小对于int范围的数二进制位最多32位符号位不算但我们按无符号处理31位足够为保险取32。集合的使用使用ArrayListInteger来存储二进制位。转换后需要Collections.reverse(digits)进行反转。递归函数设计在Java中递归函数通常定义为类的私有方法。由于需要访问和修改memo和digits它们也被设计为成员变量。每次调用f(X)前需要重新初始化memo和digits。整数处理注意处理X0的特殊情况直接向列表中添加一个0。3.3 JavaScript 实现详解JavaScript在浏览器和Node.js环境中运行其函数式特性和闭包在实现数位DP时非常灵活。/** * 统计区间[L, R]内二进制表示不含“101”的正整数个数 * param {number} L - 区间左端点 * param {number} R - 区间右端点 * return {number} */ var countValidNumbers function(L, R) { // 辅助函数计算[0, X]范围内的合法数个数 const f (X) { if (X 0) return 0; // 将X转换为二进制数组字符串形式便于处理但这里我们用数组存数字 const binaryStr X.toString(2); const digits binaryStr.split().map(Number); // 例如5 - 101 - [1,0,1] // 记忆化缓存使用Map嵌套Map键为(pos_state_isLimit_isNum)组合的字符串 // 注意由于isLimit和isNum是布尔值且只有特定组合可缓存这里我们换种方式 // 更清晰的做法使用三维数组 memo[pos][state][isLimit?][isNum?]但维度太多。 // 标准做法只缓存 !isLimit isNum 的情况用一个二维数组即可。 const memo new Array(32); for (let i 0; i 32; i) { memo[i] new Array(3).fill(-1); } const dfs (pos, state, isLimit, isNum) { if (pos digits.length) { return isNum ? 1 : 0; } // 只缓存无限制且已开始构造数字的状态 if (!isLimit isNum memo[pos][state] ! -1) { return memo[pos][state]; } let res 0; const up isLimit ? digits[pos] : 1; for (let d 0; d up; d) { let nextState state; if (isNum || d 1) { if (state 0) { nextState (d 1) ? 1 : 0; } else if (state 1) { nextState (d 0) ? 2 : 1; } else { // state 2 if (d 1) { continue; // 形成101非法 } else { nextState 0; } } } else { nextState 0; } const nextLimit isLimit (d up); const nextIsNum isNum || (d 1); res dfs(pos 1, nextState, nextLimit, nextIsNum); } if (!isLimit isNum) { memo[pos][state] res; } return res; }; return dfs(0, 0, true, false); }; return f(R) - f(L - 1); }; // 测试 console.log(countValidNumbers(1, 10)); // 输出结果JavaScript实现特点与技巧二进制转换利用Number.prototype.toString(2)可以非常方便地将数字转为二进制字符串再通过split().map(Number)转为数字数组。这比手动循环除2取余更简洁。记忆化存储JS中可以用二维数组memo[pos][state]但需要初始化填充-1。注意数组大小pos最大为二进制位数对于Number安全整数范围2^53位数也不会超过64这里预分配32或64均可。闭包的使用dfs函数定义在f函数内部可以自然地访问digits和memo形成了闭包结构清晰。大数注意事项JavaScript的Number是双精度浮点数但整数范围足够大2^53。不过在涉及极大数的位运算时此题未涉及可能需要使用BigInt。本题在华为OD机试范围内使用Number足够。3.4 Python 实现详解Python以其简洁的语法和强大的内置函数在实现数位DP时往往代码量最少可读性很高。from functools import lru_cache class Solution: def countValidNumbers(self, L: int, R: int) - int: def f(X: int) - int: if X 0: return 0 # 将X转换为二进制字符串然后转为整数列表 s bin(X)[2:] # bin(5) - 0b101取[2:] digits list(map(int, s)) # 转为[1,0,1] lru_cache(maxsizeNone) def dfs(pos: int, state: int, is_limit: bool, is_num: bool) - int: if pos len(digits): # 构造完所有位如果是一个有效数字非全前导零则返回1 return 1 if is_num else 0 res 0 # 计算当前位可选择的上界 up int(digits[pos]) if is_limit else 1 # 尝试填入0或1 for d in range(up 1): next_state state if is_num or d 1: if state 0: next_state 1 if d 1 else 0 elif state 1: next_state 2 if d 0 else 1 else: # state 2 if d 1: continue # 形成101非法分支 else: next_state 0 else: # 还在前导零阶段状态保持为0 next_state 0 # 递归到下一位 next_limit is_limit and d up next_is_num is_num or d 1 res dfs(pos 1, next_state, next_limit, next_is_num) return res # Python记忆化技巧由于is_limit和is_num影响缓存有效性我们手动控制参数 # 但lru_cache无法区分 is_limitTrue/False 的不同缓存所以需要调整。 # 标准做法将dfs定义为接收所有参数的函数但只在!is_limit and is_num时希望缓存。 # 一个技巧是将dfs拆分成两个函数或者使用带参的装饰器。这里我们采用另一种常见写法 # 不直接使用lru_cache而是在外层函数f内定义一个内部函数并手动管理一个字典缓存。 # 但为了代码清晰我们展示使用lru_cache并传入所有参数但需注意它可能会缓存一些受限路径的结果。 # 更严谨的做法如下手动缓存 from functools import lru_cache # 我们重新定义一个内部函数使用lru_cache但通过参数化来避免限制问题。 # 实际上对于数位DP一个更干净的做法是在调用dfs时对于is_limitTrue的路径我们不希望它被缓存影响其他路径。 # 因此我们可以将记忆化逻辑内嵌。 memo {} def dfs_inner(pos, state, is_limit, is_num): key (pos, state, is_limit, is_num) if key in memo: return memo[key] if pos len(digits): return 1 if is_num else 0 res 0 up digits[pos] if is_limit else 1 for d in range(up 1): # ... 状态转移逻辑与上面dfs函数内部相同 ... next_state state if is_num or d 1: if state 0: next_state 1 if d 1 else 0 elif state 1: next_state 2 if d 0 else 1 else: if d 1: continue else: next_state 0 else: next_state 0 next_limit is_limit and d up next_is_num is_num or d 1 res dfs_inner(pos 1, next_state, next_limit, next_is_num) # 关键只缓存不受限制且已开始构造数字的状态 if not is_limit and is_num: memo[key] res return res return dfs_inner(0, 0, True, False) return f(R) - f(L - 1) # 测试 sol Solution() print(sol.countValidNumbers(1, 10))Python实现的核心技巧与“坑”二进制转换bin(X)[2:]是最快最简洁的获取二进制字符串的方法再通过list(map(int, s))转为列表。记忆化装饰器lru_cachePython的functools.lru_cache非常方便但直接用它装饰dfs函数会遇到问题。因为dfs的参数包含is_limit和is_num而lru_cache会把所有参数组合都缓存。这会导致is_limitTrue的路径结果被错误地复用到is_limitFalse的路径上或者is_numFalse的状态被错误缓存。这是Python实现数位DP最容易出错的地方正确的缓存策略如上代码所示更安全的做法是使用一个字典memo手动管理缓存。缓存键为(pos, state, is_limit, is_num)但在存储时我们只存储not is_limit and is_num情况下的结果。这是因为只有这种状态下的结果才是“通用”的可以被其他搜索路径复用。递归深度Python默认递归深度有限约1000层。对于此题二进制位数最多几十位远低于限制无需担心。但对于位数极多的题目可能需要设置sys.setrecursionlimit。4. 算法正确性验证与边界测试写完代码不是终点验证其正确性至关重要。我们可以通过暴力解法小范围来验证数位DP算法的正确性。暴力验证思路编写一个辅助函数isValid(x)判断数字x的二进制是否包含“101”。然后遍历区间[L, R]R较小例如10^5统计个数。与我们的DP结果对比。以Python为例def brute_force(L, R): def has101(x): # 将x转为二进制字符串判断是否包含子串“101” return 101 in bin(x)[2:] count 0 for num in range(L, R1): if not has101(num): count 1 return count # 测试几个区间 test_cases [(1, 10), (1, 100), (100, 200)] for L, R in test_cases: dp_result sol.countValidNumbers(L, R) bf_result brute_force(L, R) print(f[{L}, {R}] DP: {dp_result}, BF: {bf_result}, {OK if dp_result bf_result else FAIL})边界条件测试最小区间L1, R1。只有数字1二进制为1不含“101”结果应为1。包含101的区间L4, R6。4(100), 5(101), 6(110)。只有5包含“101”所以结果应为2。大区间L1, R10^6。暴力法会很慢但DP应瞬间出结果。可以对比DP结果与暴力法在可接受时间内对小范围如1到10000的结果确保逻辑正确后再推断大范围。L0的情况题目通常要求正整数但我们的f(0)应该返回0因为0不是正数且其二进制0也不含“101”但根据isNum逻辑f(0)返回0。确保countValidNumbers(0, R)与countValidNumbers(1, R)结果一致如果题目要求正整数。常见错误排查结果偏大通常是因为isNum逻辑处理不当将数字0或全前导零的路径也计入了结果。检查递归终点return isNum ? 1 : 0。结果偏小可能是状态转移时对“前导零”阶段的状态更新有误。确保在!isNum d0时nextState保持为0不进行“101”模式的匹配。缓存导致错误检查缓存条件!isLimit isNum。如果错误地缓存了isLimittrue的状态会导致后续不同上限路径的结果被错误复用。5. 性能分析与优化空间我们实现的数位DP算法已经非常高效。我们来分析一下复杂度时间复杂度状态数约为O(pos * state)其中pos最大为二进制位数m对于R10^9m30state为3。对于每个状态我们需要枚举当前位的选择0或1最多2种。并且由于记忆化的存在每个(pos, state)组合在!isLimit isNum条件下最多计算一次。因此时间复杂度为O(m * 3 * 2) O(m)即O(logR)这是对数级别的极快。空间复杂度主要用于记忆化数组和递归栈。记忆化数组大小为O(m * 3)递归栈深度为O(m)。空间复杂度也是O(logR)。进一步优化思路迭代式数位DP递归记忆化搜索记忆化搜索已经足够清晰和高效。也可以写成自底向上的迭代DP但代码可能更复杂。在面试或机试中递归写法更易于理解和编写。状态压缩本题状态只有3种已经很简单。对于更复杂的状态比如需要记录前k位可以考虑用位运算压缩。预处理DP表如果需要多次查询不同的区间[L, R]我们可以预处理一个通用的DP表然后通过f(R) - f(L-1)计算。我们的算法已经做到了这一点每次f(X)调用是独立的。语言特定优化在C中可以使用constexpr、内联函数在Python中可以使用lru_cache的maxsize参数或尝试用迭代减少函数调用开销。但对于本题规模这些优化带来的提升微乎其微。实操心得调试优先写暴力在实现复杂的数位DP时我强烈建议先写一个暴力验证函数用于小数据范围。每实现一步就用小数据测试对比能快速定位逻辑错误。画状态转移图对于状态state的定义和转移在纸上画一个简单的状态机图会非常有帮助。明确从每个状态在输入0或1时会转移到哪个状态以及哪些转移是非法的。关注前导零这是数位DP最容易出错的地方。始终问自己当前位是前导零吗它应该参与条件判断如“不含101”吗在我们的问题中前导零不参与“101”模式的匹配因此状态保持为0。理解记忆化条件深刻理解为什么只有!isLimit isNum的状态才能缓存这是数位DP的核心精髓之一。isLimit为真意味着当前路径受到原始数字X的位限制这个结果是“特化”的不能用于其他数字。6. 扩展到其他类似问题与总结掌握了“不含101”的数位DP解法你可以轻松解决一系列变体问题它们都可以套用相似的框架不含连续1的个数状态可以简化为state表示上一位是否为1。判断当前位填1时如果state1则非法。不含特定模式例如“不含111”、“不含010”。只需根据模式长度比如k位将state定义为当前匹配到该模式的前几位0到k-1在状态转移时判断是否形成完整模式。含有特定模式的个数求包含“101”的数的个数。可以用总数减去不含“101”的个数也可以修改状态机增加一个“已包含模式”的终止状态一旦进入该状态后续位可以任意填。区间内数字和满足条件的数不仅统计个数还要计算这些数的和、平方和等。这时DP状态需要额外携带一个信息比如当前位之和的模数。最后一点个人体会数位DP看似 intimidating但核心就是“按位决策”“状态记录”“记忆化搜索”。多练习几道题就能掌握其套路。在华为OD或其他机试中遇到区间统计问题先想想能不能转化为数位DP往往能化繁为简。这道“不含101的数”就是一个经典的入门题希望这份超详细的四语言实现解析能帮你彻底搞懂它。在实际编码时建议先用你最熟悉的语言实现并调试通过再尝试用其他语言复现这样可以加深对算法本质的理解而不是死记硬背代码。