C语言实现LeetCode 970：暴力枚举与去重的边界艺术

1. 题目拆解Powerful Integers 到底在考什么1.1 题面与示例LeetCode 970 这道题名字叫 Powerful Integers题意其实非常直白给定三个整数x、y和bound要找出所有满足下面条件的“强大整数”nn x^i y^j其中i 0j 0并且n bound最后把所有这些不重复的整数返回。举个例子x 2y 3bound 10。我们手动推一遍i0, j01 1 2i0, j11 3 4i0, j21 9 10i1, j02 1 3i1, j12 3 5i1, j22 9 11超了i2, j04 1 5重复i2, j14 3 7i2, j24 9 13超了i3, j08 1 9i3, j18 3 11超了所以结果是[2, 3, 4, 5, 7, 9, 10]顺序没有要求去重就行。看起来很简单对吧但很多人第一次写这个题会掉进一个非常隐蔽的坑以为 i 和 j 都可以无限往上加。实际上由于bound的限制x^i本身不能超过bound - 1否则加上最小的y^j 1也超了。这个认知一旦建立后面的实现就顺了。1.2 数据范围决定算法这道题的限制是1 x, y 1000 bound 10^6。这几个数字放在一起其实已经把算法难度限定死了如果x 2那么x^i是指数增长的2^20已经超过10^6所以i最多到 20 左右。如果x 1那么1^i永远等于 1i取多少都一样。这意味着所有可能的幂组合数量是非常有限的。满打满算i和j各枚举几十个值两层循环也就几千次。这题明摆着不需要什么高级算法暴力枚举 去重就是正解。但是“暴力”这两个字在 C 语言里有个特殊含义C 没有现成的集合类型。Python 里一个set就搞定了Java 里一个HashSet也搞定了C 语言得自己想办法。不过别慌这个题的数据范围小到可以用一个数组当哈希表用也可以排序去重方法多得很。1.3 C 语言版本和别的语言版本的本质差异LeetCode 的 C 语言函数签名一般是这样的int* powerfulIntegers(int x, int y, int bound, int* returnSize)注意最后这个returnSize它是一个输出参数你必须把返回数组的实际长度写进去。这和 Python 直接返回 list 不一样C 语言的内存管理是显式的你得自己 malloc 一块内存然后在函数结束前把地址返回。很多从 Python、JavaScript 转过来刷题的人第一次写 C 版本会懵为什么函数返回的是指针为什么还要传一个int*进去其实这就是 C 语言的常态——数据长度不能靠返回值携带只能靠参数带出来。这个题用 C 写核心就三件事枚举所有合法的i和j算出x^i y^j。去重。把结果填到动态数组里设置*returnSize。2. 核心细节幂的生成、去重与边界2.1 先把所有可能的 x^i 和 y^j 算出来一个常见的错误写法是在双重循环里直接调用pow()函数for (int i 0; i 100; i) { for (int j 0; j 100; j) { int val (int)pow(x, i) (int)pow(y, j); if (val bound) { // ... } } }这样写有两个问题。第一i 100这个上限拍脑袋定的万一x 22^20已经超过10^6后面全是无用功万一x 1pow(1, i)一直是 1循环跑到 100 次纯粹浪费时间。第二pow()返回的是double涉及浮点转换在某些边界情况下会有精度问题虽然这个题数字不大但养成好习惯没错。我常用的做法是先把幂单独算出来存成两个数组int powX[64]; int powY[64];为什么是 64因为bound 10^6指数一路乘下去很快就能超过。64 个坑位绝对够用哪怕底数是 22^20就到 1048576 了连 64 都用不满。填表的逻辑也很简单int lenX 0; int cur 1; while (cur bound) { powX[lenX] cur; if (x 1) break; // 1 的任意次方都是 1填一次就够了 cur * x; }这里的cur bound是关键判断如果cur已经大于等于bound了那cur y^j bound 1 bound肯定超。同理y那边也这么做。这样的好处是循环次数完全由数据决定而不是靠感觉估一个上限。注意这里我填的是cur bound而不是cur bound。因为x^i y^j至少是cur 1如果cur bound那加个 1 就超了所以cur本身必须小于bound才有意义。2.2 去重用数组模拟哈希还是排序去重去重是 C 语言实现这道题最“烦人”的部分。LeetCode 对返回顺序没有要求这给了我们很大的自由度。方案一固定大小数组当哈希表。因为bound 10^6所以结果一定是在[0, bound]这个区间里。我们可以直接开一个bool seen[bound 1]初始化为false每算出一个合法的值val就检查seen[val]bool *seen calloc(bound 1, sizeof(bool)); // ... if (!seen[val]) { seen[val] true; // 放入结果数组 }这个方案的时间复杂度是O(枚举次数)常数极小基本是教科书级的“用空间换时间”。唯一的顾虑是bound如果极大比如10^8内存会爆但本题bound 10^6开一个bool数组也就是 1MB 左右完全没问题。方案二生成 排序去重。第 970 题的所有组合数量很少排序去重也能轻松过。先不管三七二十一把所有合法值都放进一个临时数组然后qsort最后扫描一遍跳过重复的。qsort(arr, count, sizeof(int), cmp); int j 0; for (int i 0; i count; i) { if (i 0 arr[i] arr[i - 1]) continue; result[j] arr[i]; }这个方案胜在通用不管bound多大都不怕将来遇到类似的题也能用同一个套路。我个人推荐方案一因为这道题的数据范围特殊哈希数组的开销低到可以忽略代码逻辑也更直白。面试的时候如果你能主动解释“我为什么敢开一个 bound1 大小的数组”会加不少印象分。2.3 关键边界x1 和 y1 的坑这是这道题真正的“送命题”。很多人考虑到了bound却忽略了x 1或者y 1。当x 1时1^i永远是 1。如果你在枚举i的时候没有做特殊处理直接while循环里不断乘cur * x那cur会永远停在 1循环就死循环了。所以必须加一个判断如果底数是 1幂数组里只放一个 1然后立刻 break。更极端的情况是x 1且y 1。此时x^i y^j 2永远成立。如果bound 2答案就是[2]如果bound 2答案就是空数组。很多人在这种 case 上栽跟头就是因为忘记判断底数为 1 的情况。再想深一层x 1时x^i虽然恒等于 1但i到底取哪些值实际上因为结果只依赖于x^i 1所以i只需要枚举 0 这个值就够了。如果不去管i 0的情况也只会得到相同的结果所以从数学上就可以放心地只取一次。2.4 溢出与 bound 的取舍C 语言里int在 LeetCode 的评测环境通常是 32 位最大值是2147483647。虽然bound只有10^6但枚举过程中cur * x会不会溢出比如cur 590493^10x 100相乘得到5904900还没溢出但如果x 99cur在接近10^6的时候再乘一次可能直接到九千万级别仍然不溢出。理论上枚举的数量很小似乎不会越界。但为了稳妥我习惯在while循环里加一道保险while (cur bound cur INT_MAX / x) { powX[lenX] cur; cur * x; }cur INT_MAX / x这个判断等价于cur * x INT_MAX先判断再相乘避免乘法溢出后产生未定义行为。这道题实际用不上但写代码的人要有这个意识。3. 实操完整 C 代码与逐段走读3.1 完整代码哈希数组方案下面是我自己写的一版直接可以在 LeetCode 上跑通int* powerfulIntegers(int x, int y, int bound, int* returnSize) { // 1. 生成 x 的所有幂 int powX[64]; int lenX 0; int curX 1; while (curX bound) { powX[lenX] curX; if (x 1) break; curX * x; } // 2. 生成 y 的所有幂 int powY[64]; int lenY 0; int curY 1; while (curY bound) { powY[lenY] curY; if (y 1) break; curY * y; } // 3. 去重哈希表 bool *seen (bool*)calloc(bound 1, sizeof(bool)); int *result (int*)malloc(sizeof(int) * (bound 1)); int resLen 0; // 4. 双重枚举 for (int i 0; i lenX; i) { for (int j 0; j lenY; j) { int val powX[i] powY[j]; if (val bound) break; // 因为 powY 是递增的后面更大 if (!seen[val]) { seen[val] true; result[resLen] val; } } } *returnSize resLen; free(seen); return result; }这里有个细节result数组的大小开的是bound 1因为理论上每个整数都可能是合法值最多不可能超过bound 1个。最坏情况是[0, bound]全部收集到但我们实际上只会收集 bound的正整数。虽然有一点点浪费但安全。3.2 分段解释第一步生成powX这段代码是为整个方案奠基的。while (curX bound)意味着我们只关心小于bound的幂因为x^i y^j x^i 1如果x^i bound直接就没戏了。第二步同理生成powY。这里有个优化点因为powY数组是按递增顺序排列的所以内层循环里一旦发现powX[i] powY[j] bound后面所有j都会更大直接break掉。这个优化在x和y都大于 1 的时候效果明显能省掉很多无效的加法计算。第三步用calloc初始化为false。calloc比malloc memset写起来省事语义也更清晰。注意我最后free(seen)但是没有 free(result)因为result是函数的返回值要交还给 LeetCode 的评测逻辑去释放。第四步双重循环里val bound直接break是依赖powY的单调性。但如果你把两层循环的顺序换一下也就是内层遍历powX外层遍历powY那就不能在内层break了得continue或者break对应不同的数组。写代码前先在纸上想清楚哪一层是外层别随手就写。3.3 复杂度分析时间复杂度O(lenX * lenY bound)。其中lenX和lenY最多是log_2(10^6)左右因为底数最小是 2所以两个长度最多也就 20 上下。两层循环满打满算 400 次迭代。bound 1的calloc是需要初始化内存的也是O(bound)但bound只有 1e6某次测试用例无非就是跑几百万次字节清零毫秒级。空间复杂度O(bound)主要花在seen数组上。如果你介意这 1MB 的空间也可以换成排序去重方案空间降到O(lenX * lenY)但时间复杂度多一个O(n log n)。这道题真的不用纠结空间换时间是最优解。3.4 另一种写法直接枚举所有 i、j有同学看完上面代码会问既然lenX和lenY这么小我不生成数组直接双重循环里用累乘来枚举行不行当然行但要注意累乘器需要单独维护int curI 1; for (int i 0; i lenX; i) { int curJ 1; for (int j 0; j lenY; j) { int val curI curJ; if (val bound) { // 处理 val } if (y 1) break; curJ * y; } if (x 1) break; curI * x; }这个写法省了两个数组看起来更“省”。但我实际写代码的时候还是偏爱提前生成数组原因有两个边界判断更集中。底数是否为 1、幂是否已达 bound全集中在一个 while 循环里不会和枚举逻辑混在一起。调试友好。lenX和lenY可以直接打印出来能直观看到枚举规模而嵌套循环里一旦写错累乘顺序排查起来头疼。4. 测试与本地调试4.1 针对 x1 / y1 的边界测试我自己在本地写测试的时候会先列一组“变态用例”xybound期望结果2310{2,3,4,5,7,9,10}115{2}1210{2,3,5,9}2110{2,3,5,9}352{}111{}拿第二行说x1, y1, bound5所有x^i y^j都等于 2所以答案只有一个 2。如果你的代码把i枚举出 1、2、3... 那就会不断往结果里塞重复的 2虽然靠去重还能兜住但白白浪费算力而且一不小心就会死循环。再拿第三行验证x1, y2, bound10。x^i永远是 1y^j是 1、2、4、8所以结果是 2、3、5、9和表里对上了。4.2 针对 bound0 的边界测试bound 0时x^0 y^0 1 1 2 0所以答案应该是空数组。我的代码里while (curX bound)一开始1 0就不成立lenX 0双重循环直接不执行返回一个长度为 0 的数组。这里要注意returnSize必须赋值为 0result可以是malloc出来的空数组也可以返回NULL。LeetCode 的判题系统一般两种都接受但我习惯统一malloc一块内存再返回避免某些测试代码对NULL指针做free时出问题。当然返回 NULL 且 returnSize0 在很多场景下也是合法的只是个人习惯不同。4.3 内存和性能验证LeetCode 的 C 语言内存限制对于这题来说非常宽裕。如果用calloc(bound 1, 1)最坏情况bound 10^6就是差不多 1MB。如果用calloc(bound 1, sizeof(bool))bool通常占 1 字节也是 1MB。完全不用担心。真正值得验证的是内层 break 到底能省多少时间。我写了一个简单的计时程序用x 2, y 2, bound 1000000跑。因为2^19 5242882^20 1048576 bound所以lenX lenY 19。如果不加 break内层每一轮都判断val bound后continue总共 361 次加法。加了 break 之后实际执行的次数大约是lenX * (lenY / 2 1)左右能省小一半。虽然绝对值不大但这是一个好习惯枚举循环中能利用单调性剪枝就尽量剪。5. 常见错误与排查实录5.1 死循环x1 时 cur 永远不前进这是出现频率最高的 bug。x 1时curX 1curX * x之后还是 1lenX不断累加curX永远小于bound循环跑不到头。解决办法就一行if (x 1) break;放在while循环体末尾。我在前面代码里就是这样的。面试时如果被问到这里千万别支支吾吾直接说“底数为 1 时只需要一个幂值因为 1 的任意次方都等于 1”。另一个容易忽略的地方是x -1题目约束是1 x, y 100所以不可能为负数。但如果你在扩展思考时自己改题目x -1就会在 0、1 之间反复横跳那是另一个故事了不用在这题里纠结。5.2 returnSize 忘赋值C 语言 LeetCode 题里returnSize忘赋值是个超级常见的 WAWrong Answer原因。尤其是从 Python 转过来的人习惯了 Python 自动返回长度总以为returnSize只是摆设。正确做法是函数结束前一定写清楚*returnSize resLen;别等到free(seen)之后再赋值万一中间逻辑出问题提前 returnreturnSize就可能是个随机值。5.3 重复元素没有去干净有些人用了seen数组但把seen的范围开小了。比如bool *seen calloc(bound, sizeof(bool));然后判断if (!seen[val])而val恰好等于bound时就会越界。虽然 C 语言不会立刻报错但这种“越界读”属于未定义行为可能在特殊测试用例下崩溃。正确做法是calloc(bound 1, sizeof(bool))把索引范围覆盖到 0 到 bound。同理result数组我也建议开bound 1别为了省那点内存开resLen个因为循环过程中不知道最终会有多少个合法值。5.4 排序去重方案的细节坑如果选了排序去重qsort的比较函数要写对。直接比较 int 大小常规写法是int cmp(const void *a, const void *b) { return *(int*)a - *(int*)b; }但这里有个隐患如果两个数差值很大比如INT_MAX - (-INT_MAX)会溢出。实际上本题目数值都小于bound 10^6不会溢出但更稳妥的写法是int cmp(const void *a, const void *b) { int x *(int*)a; int y *(int*)b; return (x y) - (x y); }这个写法避免了减法溢出是工程实践中比较推荐的做法。刷题可以不在意但如果是团队代码 review这个细节会被拿出来说。5.5 返回顺序问题LeetCode 明确说 “Return the result as any order”所以顺序无所谓。但如果你套用了某些模板习惯性把结果倒序输出也不算错。真正要小心的是有些变种题会要求按升序返回到时候就得在结尾加个qsort或者改用递增枚举的方式。我建议写完这题后顺手把排序去重方案也写一遍这样可以加深对两种解法差异的记忆。6. 从这道题延伸出去6.1 类似题型970 是一道非常典型的“枚举 去重”题。和它同类的还有 LeetCode 204 计算质数、202 快乐数、263 丑数等区别在于这些题的枚举逻辑更复杂但底层的“用一个容器记录已出现元素”的思路是通用的。尤其是“快乐数”那道题核心就是判断循环是否进入死循环要记录已经出现过的数。如果你在 970 里掌握了用数组模拟哈希表的技巧那到 202 题就会很顺手。6.2 用数组模拟哈希表的通用套路很多场景下C 语言里真正好用的哈希表是uthash这种第三方库但 LeetCode 不让用。好在刷题场景里大部分题的值域是有限且可预估的可以直接用数组。判断依据是集合中可能出现的最大值是否能在内存里开下。值域小于10^6直接开bool数组超快。值域在百万到千万级可以开bool数组但要注意内存消耗和评测机限制。值域极大且稀疏只能用uthash或自己实现链式哈希。970 这种题是教科书级别的“开数组”场景因为它把bound限制死了。你甚至可以更进一步用位图来压缩空间每 8 个 bool 用一个 char 的位表示但这是优化没必要为这道题用。6.3 面试中的演进问题面试官如果拿着 970 当热身很可能往外扩展“如果bound变成10^9你还能开数组吗” 这时候就要切换到排序去重法或者改用更紧凑的哈希结构。“如果x和y不一定是整数而是浮点数呢” 这就变成了更开放的数学题牵扯到精度比较已经偏离原题了。“如果允许负数幂怎么办” 那就掉进数学分析的兔子洞了比如x^-1 y^-1会产生分数结果集合会变成无限集还是有限集要分情况讨论。这几个扩展里第一个最值得认真思考。因为10^9的bool数组大约是 1GB在评测机上几乎是不可行的。但枚举组合数依然很少因为log_2(10^9) ≈ 30两层循环也就 900 次。排序去重方案在这种场景下依然游刃有余。我在实际面试中遇到过类似的追问当时没反应过来“数组哈希”失效这件事硬是纠结了几分钟才切换到排序法。后来总结了一句话能用数组就用数组数组开不下就排序排序不行再上哈希表。这个优先级在刷题和面试里都很实用。7. 一点个人体会这道题代码量不大但信息密度很高。我第一次写的时候就是折在x 1的死循环上那时候在本地终端里眼睁睁看着程序跑满几秒不结束才意识到cur根本没往前走。后来养成了一个习惯凡是枚举指数、阶乘、幂这类递增序列先想清楚终止条件是什么再想清楚每次迭代变量会不会变。另外说句题外话很多刷题攻略喜欢一上来就教“哈希集合”但 C 语言版最朴素的解法反而能逼着你理解去重的本质你要判断的是一个整数之前是否出现过这个判断本身只有两种结果那么一块连续的标志区就是最自然的模型。等你看惯了这种写法再去学uthash、布隆过滤器这些进阶方案会顺畅很多。最后给大家一个调试小技巧本地测完用例别急着提交把lenX和lenY打印出来看看。如果是2和3这两个底数lenX应该大约是 17 左右2^16 655362^17 1310723^11 1771473^12 531441和bound有关。看到这种数字基本就能确认幂生成没问题如果lenX打印出来是 1 位数那很可能while条件写反了。970 这道题算不上难题但它是 C 语言刷题者绕不过去的一块试金石。能把幂生成、边界处理、去重、动态数组这四件事在一道题里理清楚后面再碰到类似的“暴力枚举 去重”题型基本就是降维打击。