1. 项目概述与核心价值最近在技术社区和求职圈里华为ODOutsourcing Dispatcher的机试题目热度一直很高。我注意到很多朋友在准备时面对算法题尤其是那些涉及数字处理和条件筛选的题目常常感到无从下手。今天我们就来深度拆解一道非常典型的题目“从整数区间查找不含‘101’的数”。这道题看似简单只是一个字符串匹配问题但它实际上是一个绝佳的切入点能帮助我们理解算法思维在不同编程语言C/Java/Python/JavaScript中的具体实现差异以及如何针对不同场景进行性能优化。这道题的核心是给定一个整数区间[L, R]你需要找出这个区间内所有在二进制表示中不包含连续子串“101”的数字。例如数字5的二进制是“101”它就包含“101”因此需要被排除。而数字4的二进制是“100”则不包含。这个问题直接考察了面试者对整数与二进制的转换、字符串搜索或位运算、循环与条件判断等基础知识的掌握以及代码的正确性、健壮性和效率。对于准备华为OD或其他大厂机试的朋友来说吃透这道题能举一反三应对一系列类似的“数字特征过滤”问题。2. 问题深度解析与算法设计思路2.1 问题重述与边界条件确认首先我们必须把问题理解透彻。题目输入通常是两个整数L和R代表区间的左右闭端点。输出是所有满足条件的整数或者有时是满足条件的整数个数。核心需求对于区间[L, R]内的每一个整数num将其转换为二进制字符串如bin(num)检查这个字符串中是否包含子串“101”。如果不包含则num是符合条件的目标数字。关键边界与细节区间包含性题目一般明确是闭区间[L, R]即包含L和R本身。循环时务必注意。输入范围L和R的大小关系未定但通常L R。然而一个健壮的程序应该能处理L R的情况直接返回空结果。二进制表示格式不同语言的内置转换函数得到的二进制字符串可能带有前缀如“0b”。我们需要的是纯二进制数字部分用于进行子串搜索。性能考量当区间非常大时例如L1, R10^6直接遍历并转换每个数字进行字符串搜索可能会成为性能瓶颈。我们需要思考更优的解法。2.2 核心算法思路暴力法与优化方向最直观的方法是暴力遍历法初始化一个空列表result用于存放结果。对于i从L循环到R包含 a. 将整数i转换为二进制字符串binStr。 b. 在binStr中查找子串“101”。 c. 如果未找到则将i加入result。返回result。这个方法的时间复杂度是O(N * M)其中 N 是区间长度 (R-L1)M 是数字二进制表示的平均长度约 log₂R。对于一般机试限制R在10^6量级这个方法通常是可行的但绝非最优。优化思路位运算替代字符串转换与搜索字符串转换和搜索开销较大。我们可以利用位运算直接检查一个整数的二进制位中是否存在模式101即十进制数5。对于一个数x模式101可以出现在任何连续三个比特位上。我们可以通过循环右移并用掩码0b111十进制7来截取最低三位判断其是否等于0b101十进制5。这避免了字符串操作速度更快。数位DP动态规划如果区间范围巨大例如[1, 10^18]暴力法不可行。此时需要使用数位DP。这是一种用于解决“在区间[L, R]内满足某种与数位相关性质的数字个数”的高效算法。其核心思想是“记忆化搜索”按位决策并记录状态如当前位、前一位的值、是否已经匹配到101等。由于本题主要面向机试且通常数据范围不会极端大数位DP的实现较为复杂我们将在后续章节作为进阶内容探讨。对于华为OD机试掌握高效的暴力法使用位运算并能够清晰实现通常就足够了。下面我们将分别用四种语言实现基础解法和位运算优化解法。3. 多语言实现详解C/Java/Python/JavaScript在这一部分我将提供每种语言两种版本的代码版本A基础字符串法和版本B位运算法并详细解释其中的关键点、语言特性以及注意事项。3.1 C 实现C 以其高性能著称在处理大量整数运算时优势明显。版本A使用std::bitset或std::string#include iostream #include vector #include string #include algorithm std::vectorint findNumbersWithout101(int L, int R) { std::vectorint result; // 处理无效区间 if (L R) return result; for (int num L; num R; num) { // 方法1: 使用 std::bitset (固定宽度对于大数可能需要调整模板参数) // std::bitset32 bits(num); // 假设int为32位 // std::string binStr bits.to_string(); // 需要去除前导零但查找“101”时前导零不影响 // 方法2: 使用循环手动转换更通用 std::string binStr; int temp num; if (temp 0) binStr 0; while (temp 0) { binStr (temp % 2 0 ? 0 : 1) binStr; temp / 2; } // 在二进制字符串中查找子串“101” if (binStr.find(101) std::string::npos) { result.push_back(num); } } return result; } int main() { int L 1, R 20; std::vectorint res findNumbersWithout101(L, R); std::cout Numbers in [ L , R ] without 101 in binary:\n; for (int num : res) { std::cout num ; } std::cout std::endl; return 0; }C注意事项std::bitset需要指定位数对于未知大小的整数不够灵活。手动转换虽然代码多几行但更可控。字符串拼接“0” binStr在循环中效率较低因为涉及频繁的内存分配。对于性能要求高的场景可以先计算二进制长度预分配字符串空间然后从后向前填充。std::string::find返回std::string::npos表示未找到这是判断的关键。版本B使用位运算推荐#include iostream #include vector bool contains101Binary(int num) { // 当数字小于5二进制101时不可能包含101模式 if (num 5) return false; // 5的二进制是101 // 检查num的二进制表示中是否存在连续的101 // 我们不断右移并检查最低3位 while (num 5) { // 当num小于5时其二进制位数不足3位无需再检查 // 取最低三位 if ((num 0b111) 0b101) { // (num 7) 5 return true; } num 1; // 右移一位检查下一个三位组 } return false; } std::vectorint findNumbersWithout101_Bit(int L, int R) { std::vectorint result; if (L R) return result; for (int num L; num R; num) { if (!contains101Binary(num)) { result.push_back(num); } } return result; } // main函数同上关键技巧位运算中(num 7) 5是核心。7的二进制是111作为掩码可以取出num的最低三位。然后判断这三位是否等于5二进制101。循环中num 1相当于查看以每一个比特位作为最低位的连续三位。3.2 Java 实现Java 拥有丰富的标准库字符串处理方便但也要注意自动装箱和循环的性能。版本A使用Integer.toBinaryString()import java.util.ArrayList; import java.util.List; public class HuaweiOD101 { public static ListInteger findNumbersWithout101(int L, int R) { ListInteger result new ArrayList(); if (L R) { return result; } for (int num L; num R; num) { String binStr Integer.toBinaryString(num); // 使用String的contains方法判断 if (!binStr.contains(101)) { result.add(num); } } return result; } public static void main(String[] args) { int L 1, R 20; ListInteger res findNumbersWithout101(L, R); System.out.println(Numbers in [ L , R ] without 101 in binary:); for (int num : res) { System.out.print(num ); } System.out.println(); } }Java注意事项Integer.toBinaryString()非常方便它返回无前导零的二进制字符串正好符合我们的需求。String.contains()方法内部也是调用的indexOf用于判断子串是否存在代码简洁。在循环中result.add(num)涉及自动装箱int转Integer在极端性能场景下可考虑使用IntStream或数组但对于机试ArrayList足矣。版本B使用位运算public class HuaweiOD101Bit { public static boolean contains101Binary(int num) { if (num 5) return false; int n num; while (n 5) { if ((n 0b111) 0b101) { // 或 (n 7) 5 return true; } n 1; } return false; } public static ListInteger findNumbersWithout101_Bit(int L, int R) { ListInteger result new ArrayList(); if (L R) return result; for (int num L; num R; num) { if (!contains101Binary(num)) { result.add(num); } } return result; } // main方法同上 }实操心得在Java中位运算符的优先级需要留意。(n 7) 5中的括号是必须的因为的优先级低于。写代码时如果不确定就加上括号提高可读性和准确性。3.3 Python 实现Python 代码简洁表达力强是快速实现算法的好选择。版本A使用bin()和in操作符def find_numbers_without_101(L: int, R: int): 返回区间[L, R]内二进制表示不含101的整数列表 if L R: return [] result [] for num in range(L, R 1): # 注意range右边界不包含所以要R1 # bin(num) 返回如 0b101 的字符串我们取101部分 bin_str bin(num)[2:] if 101 not in bin_str: result.append(num) return result if __name__ __main__: L, R 1, 20 res find_numbers_without_101(L, R) print(fNumbers in [{L}, {R}] without 101 in binary:) print(res)Python注意事项bin(num)生成带有‘0b’前缀的字符串用切片[2:]去除。‘101’ not in bin_str是Pythonic的写法非常直观。range(L, R1)确保了闭区间遍历。这是Python循环的一个小坑点务必记住range是左闭右开。版本B使用位运算def contains_101_binary(num: int) - bool: 使用位运算判断整数num的二进制是否包含101 if num 5: return False n num while n 5: # 检查最低三位是否为101 (即十进制5) if n 0b111 0b101: # 等价于 n 7 5 return True n 1 # 右移一位 return False def find_numbers_without_101_bit(L: int, R: int): if L R: return [] result [] for num in range(L, R 1): if not contains_101_binary(num): result.append(num) return result # 测试代码 if __name__ __main__: import time L, R 1, 100000 start time.time() res_bit find_numbers_without_101_bit(L, R) time_bit time.time() - start print(fBit method found {len(res_bit)} numbers in {time_bit:.4f} seconds) # 可以对比字符串方法的耗时性能对比对于[1, 100000]这样的区间位运算方法通常比字符串方法快数倍。因为位运算完全是CPU的算术和逻辑操作而字符串方法涉及对象的创建、内存分配和更复杂的搜索算法。3.4 JavaScript 实现JavaScript 在浏览器和Node.js环境中都很常见需要注意它的数字是双精度浮点数但位运算只作用于32位有符号整数。版本A使用toString(2)和includes()function findNumbersWithout101(L, R) { if (L R) return []; const result []; for (let num L; num R; num) { // 将数字转换为二进制字符串无前缀 const binStr num.toString(2); // 检查是否包含子串“101” if (!binStr.includes(101)) { result.push(num); } } return result; } // 测试 const L 1, R 20; const res findNumbersWithout101(L, R); console.log(Numbers in [${L}, ${R}] without 101 in binary:); console.log(res.join( ));JavaScript注意事项Number.prototype.toString(2)是转换为二进制字符串的标准方法。String.prototype.includes()方法用于判断是否包含子串比indexOf() ! -1更语义化。JavaScript的数组是动态的push操作很方便。版本B使用位运算function contains101Binary(num) { if (num 5) return false; let n num; // JavaScript位运算会将操作数转换为32位有符号整数 while (n 5) { if ((n 0b111) 0b101) { // 使用严格相等 return true; } n 1; // 有符号右移 } return false; } function findNumbersWithout101Bit(L, R) { if (L R) return []; const result []; for (let num L; num R; num) { if (!contains101Binary(num)) { result.push(num); } } return result; } // 性能测试 const L2 1, R2 100000; console.time(BitMethod); const resBit findNumbersWithout101Bit(L2, R2); console.timeEnd(BitMethod); console.log(Found ${resBit.length} numbers using bit method.);重要提示JavaScript的位运算符,有一个关键特性它们会将操作数转换为32位有符号整数运算后再转换回标准JavaScript数值64位双精度浮点数。这意味着对于超过32位整数范围约±21亿的数字位运算会丢失精度。不过在绝大多数机试题目的数据范围内这都不是问题。如果题目明确数字会非常大则需要使用BigInt及其对应的位运算对BigInt同样有效。4. 性能优化与进阶算法探讨4.1 位运算法的性能优势分析我们通过一个简单的实验来对比两种方法的性能。以Python为例测试区间[1, 200000]。import time def test_performance(): L, R 1, 200000 # 测试字符串方法 start time.time() res_str find_numbers_without_101(L, R) time_str time.time() - start # 测试位运算方法 start time.time() res_bit find_numbers_without_101_bit(L, R) time_bit time.time() - start print(fString method: {time_str:.4f} seconds, found {len(res_str)} numbers.) print(fBit method: {time_bit:.4f} seconds, found {len(res_bit)} numbers.) print(fBit method is {time_str/time_bit:.2f}x faster.) # 验证结果一致性 assert res_str res_bit, Results mismatch! if __name__ __main__: test_performance()在我的测试环境中位运算方法通常比字符串方法快3到5倍。原因在于避免对象创建字符串方法每次循环都需要创建一个新的字符串对象bin(num)[2:]而位运算只在原始整数上操作。操作成本低CPU执行一次位与和右移指令的成本远低于在内存中构建一个字符串并进行子串搜索。早期终止位运算函数contains101Binary中一旦发现101模式就立即返回true并且当数字小于5时直接返回false有不错的剪枝效果。4.2 数位DP动态规划解法思路当题目区间变成[1, 10^18]时遍历法显然会超时。这时就需要数位DP。数位DP是一种用于解决“区间内满足某数位条件数字个数”的通用、高效方法。问题转化求[L, R]内不包含二进制101的数字个数可以转化为求[0, R]的个数减去[0, L-1]的个数。DP状态设计 我们定义一个记忆化搜索函数dfs(pos, pre1, pre2, isLimit, isNum)pos: 当前正在处理二进制数字的第几位从最高位向最低位。pre1: 上一位的数字0或1。pre2: 上上位的数字0或1。我们需要pre2,pre1和当前位来判断是否形成了101。isLimit: 当前位是否受到上界R的二进制表示的限制。如果受限当前位最大只能取到上界对应位的值否则可以取到1。isNum: 是否已经开始了数字的构造即是否跳过了前导零。对于二进制通常第一位就是有效位这个参数有时可以简化。状态转移 从高位向低位枚举当前位cur可以填的数字0或1受isLimit约束。如果isNum为真且pre2 1 and pre1 0 and cur 1说明形成了101这条路径非法跳过。否则递归进入下一位更新pre2 pre1,pre1 cur并根据是否达到上界更新isLimit。记忆化 使用一个多维数组dp[pos][pre1][pre2][isLimit]来存储计算结果避免重复计算。注意isLimit为真时状态是与具体上界绑定的不能直接复用所以通常只记忆化isLimit为假的状态。由于数位DP实现代码较长且是进阶内容这里不展开具体代码但理解这个思路对于解决大数据范围的同类问题至关重要。在华为OD机试中如果遇到极端数据范围面试官可能会期待你提出数位DP的思路即使不要求完整实现。5. 常见问题与调试技巧实录在实际编写和调试这类题目的代码时我踩过不少坑也总结了一些经验。5.1 高频错误与排查清单问题现象可能原因解决方案结果漏掉了一些明显符合条件的数字如4。1. 循环边界错误使用了开区间。2. 二进制字符串转换时包含了前缀如‘0b’导致搜索出错。1. 检查循环条件确保是for (num L; num R; num)。2. 打印中间变量binStr确认其格式正确如Python用bin(num)[2:]。结果中包含了明显不符合条件的数字如5。子串搜索逻辑错误。例如误用了find()的返回值判断C中find()返回npos表示未找到。仔细检查条件判断语句。C:if (binStr.find(“101”) string::npos) Java/Python/JS:if (!binStr.contains(“101”))或if (“101” not in binStr)。程序在输入较大时运行非常慢或超时。使用了低效的字符串方法且区间很大。换用位运算方法。如果数据范围极大10^10需要考虑数位DP算法。位运算版本结果错误对于某些小数字。1. 位运算函数中循环条件或掩码使用错误。2. 忽略了数字小于5的情况。1. 单步调试或打印中间值。例如对于数字5检查(5 7) 5是否成立以及循环是否正确执行。2. 确保函数开头有if (num 5) return false;。JavaScript版本对大数2^31处理出错。JavaScript的位运算基于32位有符号整数超出范围会精度丢失。使用BigInt类型。将输入转换为BigInt并使用BigInt的位运算符,。注意BigInt字面量以n结尾如5n。5.2 调试与验证技巧构造小型测试集不要一上来就用大区间测试。先用一个小的、手工可验证的区间比如[1, 10]。列出所有数字及其二进制1(1), 2(10), 3(11), 4(100), 5(101), 6(110), 7(111), 8(1000), 9(1001), 10(1010)。肉眼判断不含“101”的数字1, 2, 3, 4, 6, 7, 8, 9。5和10包含“101”运行你的程序看输出是否一致。打印关键中间变量在怀疑的地方插入打印语句。例如在循环内打印num,binStr, 以及contains101Binary(num)的返回值。这对于验证位运算逻辑特别有效。边界条件测试L R且这个数字就是5二进制101。应该返回空列表。L R。应该返回空列表或进行友好提示。L 0。0的二进制是“0”不包含“101”应该被包含在结果中。输入负数题目通常规定是正整数区间但可以思考如果扩展二进制补码表示会更复杂通常机试不考。性能Profiling对于大数据集使用语言提供的性能分析工具如Python的time模块JavaScript的console.time来对比不同方法的耗时确保优化有效。5.3 机试实战心得优先实现一个正确解在机试的紧张环境下首要目标是写出一个逻辑正确、能通过样例的代码。字符串方法虽然慢但思路直观不易出错可以作为“保底”实现。注释清晰即使时间紧也尽量写一些关键注释解释算法步骤和复杂逻辑。这有助于阅卷人理解你的思路。考虑异常输入即使题目说明输入有效也建议加上对L R的判断这体现了代码的健壮性。时间与空间复杂度分析在代码开头或注释中简单写上复杂度分析是加分项。例如“时间复杂度O((R-L1) * logR)空间复杂度O(K)用于存储结果K为结果数量。”如果时间允许提及优化即使你只实现了基础解法也可以在注释中说明“对于更大数据范围可以采用位运算进行优化或将问题转化为数位DP模型将时间复杂度降为O(logR)。” 这展示了你的知识深度。这道“查找不含101的数”的题目就像一把钥匙打开了处理数字位特征问题的大门。掌握从暴力到优化再到高阶算法的思维路径远比死记硬背代码更有价值。在实际开发中这种根据数据规模和场景选择最合适解法的能力才是工程师的核心竞争力。
华为OD机试算法精解：二进制不含101数字的查找与多语言实现
1. 项目概述与核心价值最近在技术社区和求职圈里华为ODOutsourcing Dispatcher的机试题目热度一直很高。我注意到很多朋友在准备时面对算法题尤其是那些涉及数字处理和条件筛选的题目常常感到无从下手。今天我们就来深度拆解一道非常典型的题目“从整数区间查找不含‘101’的数”。这道题看似简单只是一个字符串匹配问题但它实际上是一个绝佳的切入点能帮助我们理解算法思维在不同编程语言C/Java/Python/JavaScript中的具体实现差异以及如何针对不同场景进行性能优化。这道题的核心是给定一个整数区间[L, R]你需要找出这个区间内所有在二进制表示中不包含连续子串“101”的数字。例如数字5的二进制是“101”它就包含“101”因此需要被排除。而数字4的二进制是“100”则不包含。这个问题直接考察了面试者对整数与二进制的转换、字符串搜索或位运算、循环与条件判断等基础知识的掌握以及代码的正确性、健壮性和效率。对于准备华为OD或其他大厂机试的朋友来说吃透这道题能举一反三应对一系列类似的“数字特征过滤”问题。2. 问题深度解析与算法设计思路2.1 问题重述与边界条件确认首先我们必须把问题理解透彻。题目输入通常是两个整数L和R代表区间的左右闭端点。输出是所有满足条件的整数或者有时是满足条件的整数个数。核心需求对于区间[L, R]内的每一个整数num将其转换为二进制字符串如bin(num)检查这个字符串中是否包含子串“101”。如果不包含则num是符合条件的目标数字。关键边界与细节区间包含性题目一般明确是闭区间[L, R]即包含L和R本身。循环时务必注意。输入范围L和R的大小关系未定但通常L R。然而一个健壮的程序应该能处理L R的情况直接返回空结果。二进制表示格式不同语言的内置转换函数得到的二进制字符串可能带有前缀如“0b”。我们需要的是纯二进制数字部分用于进行子串搜索。性能考量当区间非常大时例如L1, R10^6直接遍历并转换每个数字进行字符串搜索可能会成为性能瓶颈。我们需要思考更优的解法。2.2 核心算法思路暴力法与优化方向最直观的方法是暴力遍历法初始化一个空列表result用于存放结果。对于i从L循环到R包含 a. 将整数i转换为二进制字符串binStr。 b. 在binStr中查找子串“101”。 c. 如果未找到则将i加入result。返回result。这个方法的时间复杂度是O(N * M)其中 N 是区间长度 (R-L1)M 是数字二进制表示的平均长度约 log₂R。对于一般机试限制R在10^6量级这个方法通常是可行的但绝非最优。优化思路位运算替代字符串转换与搜索字符串转换和搜索开销较大。我们可以利用位运算直接检查一个整数的二进制位中是否存在模式101即十进制数5。对于一个数x模式101可以出现在任何连续三个比特位上。我们可以通过循环右移并用掩码0b111十进制7来截取最低三位判断其是否等于0b101十进制5。这避免了字符串操作速度更快。数位DP动态规划如果区间范围巨大例如[1, 10^18]暴力法不可行。此时需要使用数位DP。这是一种用于解决“在区间[L, R]内满足某种与数位相关性质的数字个数”的高效算法。其核心思想是“记忆化搜索”按位决策并记录状态如当前位、前一位的值、是否已经匹配到101等。由于本题主要面向机试且通常数据范围不会极端大数位DP的实现较为复杂我们将在后续章节作为进阶内容探讨。对于华为OD机试掌握高效的暴力法使用位运算并能够清晰实现通常就足够了。下面我们将分别用四种语言实现基础解法和位运算优化解法。3. 多语言实现详解C/Java/Python/JavaScript在这一部分我将提供每种语言两种版本的代码版本A基础字符串法和版本B位运算法并详细解释其中的关键点、语言特性以及注意事项。3.1 C 实现C 以其高性能著称在处理大量整数运算时优势明显。版本A使用std::bitset或std::string#include iostream #include vector #include string #include algorithm std::vectorint findNumbersWithout101(int L, int R) { std::vectorint result; // 处理无效区间 if (L R) return result; for (int num L; num R; num) { // 方法1: 使用 std::bitset (固定宽度对于大数可能需要调整模板参数) // std::bitset32 bits(num); // 假设int为32位 // std::string binStr bits.to_string(); // 需要去除前导零但查找“101”时前导零不影响 // 方法2: 使用循环手动转换更通用 std::string binStr; int temp num; if (temp 0) binStr 0; while (temp 0) { binStr (temp % 2 0 ? 0 : 1) binStr; temp / 2; } // 在二进制字符串中查找子串“101” if (binStr.find(101) std::string::npos) { result.push_back(num); } } return result; } int main() { int L 1, R 20; std::vectorint res findNumbersWithout101(L, R); std::cout Numbers in [ L , R ] without 101 in binary:\n; for (int num : res) { std::cout num ; } std::cout std::endl; return 0; }C注意事项std::bitset需要指定位数对于未知大小的整数不够灵活。手动转换虽然代码多几行但更可控。字符串拼接“0” binStr在循环中效率较低因为涉及频繁的内存分配。对于性能要求高的场景可以先计算二进制长度预分配字符串空间然后从后向前填充。std::string::find返回std::string::npos表示未找到这是判断的关键。版本B使用位运算推荐#include iostream #include vector bool contains101Binary(int num) { // 当数字小于5二进制101时不可能包含101模式 if (num 5) return false; // 5的二进制是101 // 检查num的二进制表示中是否存在连续的101 // 我们不断右移并检查最低3位 while (num 5) { // 当num小于5时其二进制位数不足3位无需再检查 // 取最低三位 if ((num 0b111) 0b101) { // (num 7) 5 return true; } num 1; // 右移一位检查下一个三位组 } return false; } std::vectorint findNumbersWithout101_Bit(int L, int R) { std::vectorint result; if (L R) return result; for (int num L; num R; num) { if (!contains101Binary(num)) { result.push_back(num); } } return result; } // main函数同上关键技巧位运算中(num 7) 5是核心。7的二进制是111作为掩码可以取出num的最低三位。然后判断这三位是否等于5二进制101。循环中num 1相当于查看以每一个比特位作为最低位的连续三位。3.2 Java 实现Java 拥有丰富的标准库字符串处理方便但也要注意自动装箱和循环的性能。版本A使用Integer.toBinaryString()import java.util.ArrayList; import java.util.List; public class HuaweiOD101 { public static ListInteger findNumbersWithout101(int L, int R) { ListInteger result new ArrayList(); if (L R) { return result; } for (int num L; num R; num) { String binStr Integer.toBinaryString(num); // 使用String的contains方法判断 if (!binStr.contains(101)) { result.add(num); } } return result; } public static void main(String[] args) { int L 1, R 20; ListInteger res findNumbersWithout101(L, R); System.out.println(Numbers in [ L , R ] without 101 in binary:); for (int num : res) { System.out.print(num ); } System.out.println(); } }Java注意事项Integer.toBinaryString()非常方便它返回无前导零的二进制字符串正好符合我们的需求。String.contains()方法内部也是调用的indexOf用于判断子串是否存在代码简洁。在循环中result.add(num)涉及自动装箱int转Integer在极端性能场景下可考虑使用IntStream或数组但对于机试ArrayList足矣。版本B使用位运算public class HuaweiOD101Bit { public static boolean contains101Binary(int num) { if (num 5) return false; int n num; while (n 5) { if ((n 0b111) 0b101) { // 或 (n 7) 5 return true; } n 1; } return false; } public static ListInteger findNumbersWithout101_Bit(int L, int R) { ListInteger result new ArrayList(); if (L R) return result; for (int num L; num R; num) { if (!contains101Binary(num)) { result.add(num); } } return result; } // main方法同上 }实操心得在Java中位运算符的优先级需要留意。(n 7) 5中的括号是必须的因为的优先级低于。写代码时如果不确定就加上括号提高可读性和准确性。3.3 Python 实现Python 代码简洁表达力强是快速实现算法的好选择。版本A使用bin()和in操作符def find_numbers_without_101(L: int, R: int): 返回区间[L, R]内二进制表示不含101的整数列表 if L R: return [] result [] for num in range(L, R 1): # 注意range右边界不包含所以要R1 # bin(num) 返回如 0b101 的字符串我们取101部分 bin_str bin(num)[2:] if 101 not in bin_str: result.append(num) return result if __name__ __main__: L, R 1, 20 res find_numbers_without_101(L, R) print(fNumbers in [{L}, {R}] without 101 in binary:) print(res)Python注意事项bin(num)生成带有‘0b’前缀的字符串用切片[2:]去除。‘101’ not in bin_str是Pythonic的写法非常直观。range(L, R1)确保了闭区间遍历。这是Python循环的一个小坑点务必记住range是左闭右开。版本B使用位运算def contains_101_binary(num: int) - bool: 使用位运算判断整数num的二进制是否包含101 if num 5: return False n num while n 5: # 检查最低三位是否为101 (即十进制5) if n 0b111 0b101: # 等价于 n 7 5 return True n 1 # 右移一位 return False def find_numbers_without_101_bit(L: int, R: int): if L R: return [] result [] for num in range(L, R 1): if not contains_101_binary(num): result.append(num) return result # 测试代码 if __name__ __main__: import time L, R 1, 100000 start time.time() res_bit find_numbers_without_101_bit(L, R) time_bit time.time() - start print(fBit method found {len(res_bit)} numbers in {time_bit:.4f} seconds) # 可以对比字符串方法的耗时性能对比对于[1, 100000]这样的区间位运算方法通常比字符串方法快数倍。因为位运算完全是CPU的算术和逻辑操作而字符串方法涉及对象的创建、内存分配和更复杂的搜索算法。3.4 JavaScript 实现JavaScript 在浏览器和Node.js环境中都很常见需要注意它的数字是双精度浮点数但位运算只作用于32位有符号整数。版本A使用toString(2)和includes()function findNumbersWithout101(L, R) { if (L R) return []; const result []; for (let num L; num R; num) { // 将数字转换为二进制字符串无前缀 const binStr num.toString(2); // 检查是否包含子串“101” if (!binStr.includes(101)) { result.push(num); } } return result; } // 测试 const L 1, R 20; const res findNumbersWithout101(L, R); console.log(Numbers in [${L}, ${R}] without 101 in binary:); console.log(res.join( ));JavaScript注意事项Number.prototype.toString(2)是转换为二进制字符串的标准方法。String.prototype.includes()方法用于判断是否包含子串比indexOf() ! -1更语义化。JavaScript的数组是动态的push操作很方便。版本B使用位运算function contains101Binary(num) { if (num 5) return false; let n num; // JavaScript位运算会将操作数转换为32位有符号整数 while (n 5) { if ((n 0b111) 0b101) { // 使用严格相等 return true; } n 1; // 有符号右移 } return false; } function findNumbersWithout101Bit(L, R) { if (L R) return []; const result []; for (let num L; num R; num) { if (!contains101Binary(num)) { result.push(num); } } return result; } // 性能测试 const L2 1, R2 100000; console.time(BitMethod); const resBit findNumbersWithout101Bit(L2, R2); console.timeEnd(BitMethod); console.log(Found ${resBit.length} numbers using bit method.);重要提示JavaScript的位运算符,有一个关键特性它们会将操作数转换为32位有符号整数运算后再转换回标准JavaScript数值64位双精度浮点数。这意味着对于超过32位整数范围约±21亿的数字位运算会丢失精度。不过在绝大多数机试题目的数据范围内这都不是问题。如果题目明确数字会非常大则需要使用BigInt及其对应的位运算对BigInt同样有效。4. 性能优化与进阶算法探讨4.1 位运算法的性能优势分析我们通过一个简单的实验来对比两种方法的性能。以Python为例测试区间[1, 200000]。import time def test_performance(): L, R 1, 200000 # 测试字符串方法 start time.time() res_str find_numbers_without_101(L, R) time_str time.time() - start # 测试位运算方法 start time.time() res_bit find_numbers_without_101_bit(L, R) time_bit time.time() - start print(fString method: {time_str:.4f} seconds, found {len(res_str)} numbers.) print(fBit method: {time_bit:.4f} seconds, found {len(res_bit)} numbers.) print(fBit method is {time_str/time_bit:.2f}x faster.) # 验证结果一致性 assert res_str res_bit, Results mismatch! if __name__ __main__: test_performance()在我的测试环境中位运算方法通常比字符串方法快3到5倍。原因在于避免对象创建字符串方法每次循环都需要创建一个新的字符串对象bin(num)[2:]而位运算只在原始整数上操作。操作成本低CPU执行一次位与和右移指令的成本远低于在内存中构建一个字符串并进行子串搜索。早期终止位运算函数contains101Binary中一旦发现101模式就立即返回true并且当数字小于5时直接返回false有不错的剪枝效果。4.2 数位DP动态规划解法思路当题目区间变成[1, 10^18]时遍历法显然会超时。这时就需要数位DP。数位DP是一种用于解决“区间内满足某数位条件数字个数”的通用、高效方法。问题转化求[L, R]内不包含二进制101的数字个数可以转化为求[0, R]的个数减去[0, L-1]的个数。DP状态设计 我们定义一个记忆化搜索函数dfs(pos, pre1, pre2, isLimit, isNum)pos: 当前正在处理二进制数字的第几位从最高位向最低位。pre1: 上一位的数字0或1。pre2: 上上位的数字0或1。我们需要pre2,pre1和当前位来判断是否形成了101。isLimit: 当前位是否受到上界R的二进制表示的限制。如果受限当前位最大只能取到上界对应位的值否则可以取到1。isNum: 是否已经开始了数字的构造即是否跳过了前导零。对于二进制通常第一位就是有效位这个参数有时可以简化。状态转移 从高位向低位枚举当前位cur可以填的数字0或1受isLimit约束。如果isNum为真且pre2 1 and pre1 0 and cur 1说明形成了101这条路径非法跳过。否则递归进入下一位更新pre2 pre1,pre1 cur并根据是否达到上界更新isLimit。记忆化 使用一个多维数组dp[pos][pre1][pre2][isLimit]来存储计算结果避免重复计算。注意isLimit为真时状态是与具体上界绑定的不能直接复用所以通常只记忆化isLimit为假的状态。由于数位DP实现代码较长且是进阶内容这里不展开具体代码但理解这个思路对于解决大数据范围的同类问题至关重要。在华为OD机试中如果遇到极端数据范围面试官可能会期待你提出数位DP的思路即使不要求完整实现。5. 常见问题与调试技巧实录在实际编写和调试这类题目的代码时我踩过不少坑也总结了一些经验。5.1 高频错误与排查清单问题现象可能原因解决方案结果漏掉了一些明显符合条件的数字如4。1. 循环边界错误使用了开区间。2. 二进制字符串转换时包含了前缀如‘0b’导致搜索出错。1. 检查循环条件确保是for (num L; num R; num)。2. 打印中间变量binStr确认其格式正确如Python用bin(num)[2:]。结果中包含了明显不符合条件的数字如5。子串搜索逻辑错误。例如误用了find()的返回值判断C中find()返回npos表示未找到。仔细检查条件判断语句。C:if (binStr.find(“101”) string::npos) Java/Python/JS:if (!binStr.contains(“101”))或if (“101” not in binStr)。程序在输入较大时运行非常慢或超时。使用了低效的字符串方法且区间很大。换用位运算方法。如果数据范围极大10^10需要考虑数位DP算法。位运算版本结果错误对于某些小数字。1. 位运算函数中循环条件或掩码使用错误。2. 忽略了数字小于5的情况。1. 单步调试或打印中间值。例如对于数字5检查(5 7) 5是否成立以及循环是否正确执行。2. 确保函数开头有if (num 5) return false;。JavaScript版本对大数2^31处理出错。JavaScript的位运算基于32位有符号整数超出范围会精度丢失。使用BigInt类型。将输入转换为BigInt并使用BigInt的位运算符,。注意BigInt字面量以n结尾如5n。5.2 调试与验证技巧构造小型测试集不要一上来就用大区间测试。先用一个小的、手工可验证的区间比如[1, 10]。列出所有数字及其二进制1(1), 2(10), 3(11), 4(100), 5(101), 6(110), 7(111), 8(1000), 9(1001), 10(1010)。肉眼判断不含“101”的数字1, 2, 3, 4, 6, 7, 8, 9。5和10包含“101”运行你的程序看输出是否一致。打印关键中间变量在怀疑的地方插入打印语句。例如在循环内打印num,binStr, 以及contains101Binary(num)的返回值。这对于验证位运算逻辑特别有效。边界条件测试L R且这个数字就是5二进制101。应该返回空列表。L R。应该返回空列表或进行友好提示。L 0。0的二进制是“0”不包含“101”应该被包含在结果中。输入负数题目通常规定是正整数区间但可以思考如果扩展二进制补码表示会更复杂通常机试不考。性能Profiling对于大数据集使用语言提供的性能分析工具如Python的time模块JavaScript的console.time来对比不同方法的耗时确保优化有效。5.3 机试实战心得优先实现一个正确解在机试的紧张环境下首要目标是写出一个逻辑正确、能通过样例的代码。字符串方法虽然慢但思路直观不易出错可以作为“保底”实现。注释清晰即使时间紧也尽量写一些关键注释解释算法步骤和复杂逻辑。这有助于阅卷人理解你的思路。考虑异常输入即使题目说明输入有效也建议加上对L R的判断这体现了代码的健壮性。时间与空间复杂度分析在代码开头或注释中简单写上复杂度分析是加分项。例如“时间复杂度O((R-L1) * logR)空间复杂度O(K)用于存储结果K为结果数量。”如果时间允许提及优化即使你只实现了基础解法也可以在注释中说明“对于更大数据范围可以采用位运算进行优化或将问题转化为数位DP模型将时间复杂度降为O(logR)。” 这展示了你的知识深度。这道“查找不含101的数”的题目就像一把钥匙打开了处理数字位特征问题的大门。掌握从暴力到优化再到高阶算法的思维路径远比死记硬背代码更有价值。在实际开发中这种根据数据规模和场景选择最合适解法的能力才是工程师的核心竞争力。
