1. 问题引入当“幸运数字”遇上“区间和”最近在牛客网上刷题又碰到了那道经典的“幸运数字II”。说实话第一次看到这个题目名字我还以为是什么玄学或者数学找规律题。但仔细一读题发现它其实是一个披着“幸运”外衣的、非常考验思维转换和算法效率的区间处理问题。题目大意是我们定义一种“幸运数字”只由数字4和7组成。然后给定一个区间[L, R]我们需要找出这个区间内所有“下一个幸运数字”的和。这里的“下一个幸运数字”定义是关键对于区间内的任意一个数x它的“下一个幸运数字”是大于等于x的最小幸运数字。所以我们的任务不是简单地统计区间里有多少个幸运数字而是要把区间[L, R]中每一个数对应的“下一个幸运数字”找出来然后求和。举个例子如果区间是[1, 7]数字1、2、3的下一个幸运数字是4。数字4的下一个幸运数字是4。数字5、6的下一个幸运数字是7。数字7的下一个幸运数字是7。 那么总和就是4*3 4 7*2 7 12 4 14 7 37。暴力法的思路最直接从L到R遍历每个数i然后写一个循环去找大于等于i的最小幸运数字累加。这个思路清晰易懂但一旦L和R的范围给到像1到10^9这样的量级时间复杂度就是O((R-L1) * 寻找幸运数字的代价)显然是无法接受的必然超时。所以这道题的核心挑战在于如何避免对区间内每一个数进行独立的、耗时的查询而是找到一种能够批量、高效处理整个区间的方法。这需要我们跳出“逐个数字处理”的惯性思维从“区间贡献”的角度来重新审视问题。2. 核心思路转换从“点查询”到“区间覆盖”暴力法之所以慢是因为它把问题看作无数个独立的“点查询”。我们需要一个思维跃迁把所有的幸运数字看成一系列“挡板”或者“服务站”而区间[L, R]内的普通数字则是需要被这些“服务站”服务的对象。具体来说我们首先生成所有在可能范围内至少要覆盖到R的幸运数字。因为幸运数字只由4和7组成我们可以用递归或队列的方式生成比如4, 7, 44, 47, 74, 77, 444, 447... 我们把这些生成好的幸运数字放在一个数组里并且为了后续处理方便通常会在数组的开头加一个很小的数比如0在结尾加一个很大的数比如一个远超R的幸运数字或者Long.MAX_VALUE形成一个“幸运数字序列”。我们假设这个序列是luckys [a0, a1, a2, ..., ak]其中a0 a1 a2 ... ak并且a0可能小于Lak肯定大于R。现在关键的一步来了。考虑任意两个相邻的幸运数字luckys[i]和luckys[i1]。对于开区间(luckys[i], luckys[i1])内的所有整数注意不包括左端点luckys[i]本身它们的“下一个幸运数字”是谁答案是统一的都是luckys[i1]。因为luckys[i1]是第一个大于luckys[i]的幸运数字那么在(luckys[i], luckys[i1])这个区间内的数大于等于它们的最小幸运数字自然就是luckys[i1]。举个例子幸运数字序列里有..., 4, 7, 44, ...。那么对于区间(4, 7)也就是数字5和6它们的下一个幸运数字都是7。对于区间(7, 44)也就是数字8到43它们的下一个幸运数字都是44。这样一来我们就把整个数轴用幸运数字切割成了一段一段的区间。对于每一段区间(luckys[i], luckys[i1])区间内所有数对总和的贡献是固定的区间内的整数个数 * luckys[i1]。我们的目标区间[L, R]可能会横跨多个这样的“幸运区间段”。因此解题思路就清晰了生成足够多的幸运数字形成一个序列。定位找到L和R在这个幸运数字序列中“所处”的区间段。分段计算将[L, R]这个区间按照幸运数字的切分点分解成若干个连续的子区间其中每个子区间都完整地落在某个(luckys[i], luckys[i1])内或者端点恰好是某个幸运数字。求和对于每一个分解出来的子区间计算其整数个数乘以它对应的“下一个幸运数字”即该子区间右侧的幸运数字luckys[i1]最后将所有子区间的贡献相加。这个思路成功地将一个需要对10^9量级个点进行查询的问题转化为了一个只需要处理O(K)个区间段的问题其中K是幸运数字的个数。在R 10^9的限制下位数不超过10位的、只由4和7组成的数字数量是有限的2^1 2^2 ... 2^10 2046个完全在可接受范围内。效率得到了质的提升。3. 关键实现细节与算法步骤拆解理解了核心思想我们来看看如何用代码一步步实现。我会以Java为例进行说明其他语言逻辑相通。3.1 生成所有幸运数字首先我们需要生成所有可能用到的幸运数字。一个常见的方法是使用BFS广度优先搜索或DFS深度优先搜索。这里用DFS递归生成更直观。/** * 生成所有不超过上限的、只由4和7组成的数字幸运数字 * param limit 上限通常取R的最大可能值这里我们可以直接生成到10^10量级以确保覆盖 * param current 当前生成的数字 * param luckys 用于存储结果的列表 */ private void generateLuckyNumbers(long current, long limit, ListLong luckys) { if (current limit) { return; } if (current ! 0) { // 避免把0加进去不过我们后面会排序0不影响 luckys.add(current); } // 在当前数字末尾分别加上4和7生成新的数字 generateLuckyNumbers(current * 10 4, limit, luckys); generateLuckyNumbers(current * 10 7, limit, luckys); }在调用时我们可以设定一个足够大的limit比如10_000_000_000L100亿这远大于题目可能的R (10^9)确保能覆盖所有需要的幸运数字。生成后务必对列表进行排序因为递归生成的顺序不一定是严格递增的。同时为了方便后续的区间处理我们通常在排序后的列表头部插入一个很小的数如0在尾部插入一个很大的数如 Long.MAX_VALUE 或一个极大的幸运数字。这样luckys.get(i)和luckys.get(i1)就构成了一个完整的区间覆盖。ListLong list new ArrayList(); generateLuckyNumbers(0, 10_000_000_000L, list); Collections.sort(list); list.add(0, 0L); // 在索引0处插入0 list.add(Long.MAX_VALUE); // 在末尾插入一个极大值 // 现在list看起来像 [0, 4, 7, 44, 47, ..., Long.MAX_VALUE]3.2 定位与区间分解这是整个算法最精妙也最容易出错的部分。我们需要把[L, R]分解成若干个落在(luckys[i], luckys[i1])内的子区间。我们可以用两个指针i和j在幸运数字序列上滑动同时维护一个current变量表示当前待处理的起点。初始化找到第一个大于等于L的幸运数字的索引。更准确地说是找到这样一个位置idx使得luckys[idx] L luckys[idx1]。那么区间[L, R]的起点L就落在(luckys[idx], luckys[idx1]]这个半开半闭区间内。我们设current L。循环分解只要current R就继续循环。确定current所在的区间段。假设current在(luckys[i], luckys[i1]]内。那么从current开始直到min(R, luckys[i1])为止这个子区间[current, min(R, luckys[i1])]内的所有数它们的“下一个幸运数字”都是luckys[i1]。计算这个子区间的贡献(min(R, luckys[i1]) - current 1) * luckys[i1]并累加到总和中。更新current为min(R, luckys[i1]) 1即移动到下一个待处理的起点。如果current恰好等于luckys[i1] 1那么它就进入了下一个区间段(luckys[i1], luckys[i2])。这个逻辑确保了[L, R]被完整地、不重不漏地覆盖。3.3 代码实现与注释将上述步骤整合以下是完整的Java题解代码import java.util.*; public class Main { // 存储所有幸运数字的列表 private static ListLong luckyList new ArrayList(); public static void main(String[] args) { Scanner sc new Scanner(System.in); long L sc.nextLong(); long R sc.nextLong(); // 1. 生成幸运数字 generateLuckys(0L, 10_000_000_000L); // 生成到100亿足够覆盖10^9 Collections.sort(luckyList); // 插入边界值方便处理 luckyList.add(0, 0L); luckyList.add(Long.MAX_VALUE); long sum 0L; long current L; // 当前要处理的起点 // 2. 遍历幸运数字列表进行区间分解和计算 // 从第一个大于0的幸运数字开始找L所在的区间 for (int i 0; i luckyList.size() - 1; i) { long left luckyList.get(i); long right luckyList.get(i 1); // 如果当前区间 [left, right) 与 [current, R] 有交集 // 即 current right 且 current R // 并且交集部分是从 current 开始 if (current right current R) { // 计算交集区间的右端点 long segmentEnd Math.min(R, right - 1); // 注意区间是(left, right)所以右端点是right-1 // 计算这个子区间的长度 long length segmentEnd - current 1; // 这个子区间内所有数的下一个幸运数字都是 right sum length * right; // 更新current到下一个区间的起点 current segmentEnd 1; } // 如果current已经超过R提前结束 if (current R) { break; } } System.out.println(sum); sc.close(); } /** * DFS生成幸运数字 * param num 当前数字 * param limit 上限 */ private static void generateLuckys(long num, long limit) { if (num limit) return; if (num ! 0) { luckyList.add(num); } generateLuckys(num * 10 4, limit); generateLuckys(num * 10 7, limit); } }几点关键解释区间表示在代码中我将幸运数字luckys[i]和luckys[i1]构成的区间理解为(luckys[i], luckys[i1])即左开右开。这意味着数字luckys[i]本身不属于这个区间它的“下一个幸运数字”是它自己。而在计算时luckys[i]需要被单独处理。在上面的循环中right-1就是为了获取这个开区间的最大整数。单独处理端点上述循环逻辑已经隐含处理了端点情况。当current正好等于某个幸运数字luckys[i]时因为我们的区间是(left, right)其中left luckys[i-1],right luckys[i]此时current(luckys[i]) 并不小于right所以不会进入if (current right)分支。那么luckys[i]什么时候被处理呢它会在i增加后作为下一个区间的左端点left被考虑吗不luckys[i]应该被算作它自己。更清晰的写法是在循环中如果current正好等于某个luckys[i]那么它单独贡献luckys[i]然后current。为了逻辑统一另一种更清晰的实现方式是直接使用闭区间[luckys[i]1, luckys[i1]]来表示“下一个幸运数字是luckys[i1]”的区间而luckys[i]自身单独处理。这取决于个人的区间定义习惯但核心思想不变。效率生成幸运数字是O(2^10)量级分解区间是O(K)量级K为幸运数字个数约2000因此总时间复杂度对L, R高达10^9是常数级非常高效。4. 易错点分析与调试技巧这道题思路清晰后实现起来并不复杂但仍有几个“坑”容易让初学者栽跟头。1. 数据类型与溢出题目中L和R的范围是1 L R 10^9。单个幸运数字最大可能接近10^10比如7777777777。在计算区间贡献长度 * 幸运数字时长度最大可以是10^9幸运数字最大可以是10^10乘积就是10^19这远远超过了int甚至long的表示范围long最大值约9.22e18。因此必须使用long类型来存储所有变量包括循环中的索引i如果用它来计算区间长度也可能需要转为long进行乘法运算否则可能发生溢出导致结果错误。2. 区间边界处理这是最大的难点。如前所述如何定义“幸运数字区间”直接影响代码逻辑。方案A推荐将数轴划分为这样的区间(-∞, 4],(4, 7],(7, 44],(44, 47], ...。这意味着对于区间(prevLucky, currentLucky]其中的数x满足prevLucky x currentLucky它们的下一个幸运数字是currentLucky。这样幸运数字本身落在了区间的右端点处理起来比较方便。初始化时prevLucky可以设为0。方案B划分为[4, 4],(4, 7],(7, 44], ...。这样每个幸运数字单独成一个区间。逻辑上更清晰但循环判断条件会稍多。无论哪种方案务必在纸上用一个小例子如L1, R10走一遍流程验证你的区间划分和累加逻辑是否正确。特别是当L或R本身就是幸运数字时。3. 幸运数字的生成范围虽然R 10^9但“下一个幸运数字”可能大于R。例如R999,999,999它的下一个幸运数字可能是1,000,000,000量级的。所以生成幸运数字时上限要设得足够大。通常生成到10^10100亿是安全且足够的。生成太少会导致程序在寻找大于R的幸运数字时找不到从而出错。4. 二分查找的运用在上面的实现中我们使用了一个for循环来遍历幸运数字列表。实际上我们可以用二分查找Collections.binarySearch快速定位L和R在幸运数字列表中的位置然后只处理中间涉及的那些区间这样效率更高。但对于K2000这个数量级线性遍历也完全无压力代码更易读。调试技巧首先测试小范围数据比如[1, 20]手动计算结果与程序输出对比。重点测试边界情况L和R相等且是幸运数字如[7,7]。L和R相等不是幸运数字如[8,8]。L是幸运数字R不是如[4, 6]。L不是幸运数字R是如[5, 7]。L和R跨越多個幸运数字区间如[1, 100]。打印中间变量。在循环中打印出current,left,right,segmentEnd,length和每次累加的sum可以非常直观地看到区间是如何被分解和计算的便于定位逻辑错误。5. 算法扩展与同类问题思考解决了“幸运数字II”我们掌握了“区间批量处理”和“用关键点分割区间”的核心思想。这个思想可以推广到许多类似问题。变体1上一个幸运数字如果问题改为求区间[L, R]内每个数的“上一个幸运数字”小于等于该数的最大幸运数字的和思路完全一样。只需要将区间定义为[luckys[i], luckys[i1])那么这个区间内所有数的“上一个幸运数字”就是luckys[i]。变体2幸运数字的个数如果问题改为统计区间内幸运数字的个数那就更简单了。生成幸运数字列表后使用两次二分查找找到第一个大于等于L的幸运数字索引idxL和第一个大于R的幸运数字索引idxR那么idxR - idxL就是结果。变体3多维或多属性关键点有时“关键点”不是单一的数字而是具有某种属性的对象。例如给定一系列“服务站点”每个站点有位置和权重求区间内每个点到其最近服务站点的权重和。这时我们可以先对所有服务站点排序然后同样用它们将数轴分段在每一段内所有点都对应同一个“最近服务站点”。问题就化归为计算每个区间段的贡献。思想总结 这类问题的通用解决模式是识别关键点找出那些能改变“目标函数”取值的点如本题的幸运数字。排序与分段将这些关键点排序它们将整个定义域如数轴分割成若干个连续区间。区间内统一处理在每个区间内部“目标函数”的行为是统一的如本题的“下一个幸运数字”是常数因此可以批量计算。处理查询区间将查询区间[L, R]与这些固定区间求交分解为若干个子区间分别计算后求和。这种“化点为段”、“批量处理”的思想是优化许多区间查询问题的利器其核心在于发现问题的“分段常数”性质。下次再遇到类似“区间内每个数对应某个函数值求和”的问题时不妨先思考一下这个函数值的变化是不是由一些离散的关键点决定的如果是恭喜你你已经找到了高效解题的钥匙。
