LeetCode 869. Reordered Power of 2 题解Go 实现与字符频次判定法【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 869 题「Reordered Power of 2重排数字后是否能为 2 的幂」展开完整继承并深入讲解 LeetCode-Go 仓库中该题的标准解法先将数字重排转化为字符串字符频次是否相同的判定问题再结合数据范围枚举所有位长不超过 N 的 2 的幂进行匹配。读完后你将掌握用 Go 统计字符频次比较排列等价性的通用套路、通过位运算i 1迭代 2 的幂的写法以及如何利用仓库内的单元测试验证解法正确性。题目描述给定一个正整数N我们可以按任何顺序包括原始顺序重排它的每一位数字但重排后数字的前导位不能为 0。如果存在一种重排方式使得重排得到的数字是2 的幂返回true否则返回false。示例 1输入1 输出true示例 2输入10 输出false示例 3输入16 输出true示例 4输入24 输出false示例 5输入46 输出true约束条件1 N 10^9题目大意给定正整数N我们按任何顺序包括原始顺序将数字重新排序注意其前导数字不能为零。如果可以通过上述方式得到 2 的幂返回true否则返回false。简单来说这道题判断的是N的十进制表示经过任意排列后是否存在某个排列恰好落在2 的幂这个特殊集合中。解题思路核心一把重排转化为字符频次比较将整数每个位上的所有排列看成字符串那么题目就转换成判断这些字符串是否与某个 2 的幂的字符串一致。两个由相同字符集构成的字符串只要任意排列后能相等那么它们各自的字符出现频次必然完全相同。反过来也成立频次完全相同意味着可以互相重排得到。因此比较两个数是否是彼此的排列等价于比较它们的十进制字符串中每个数字字符09出现的次数是否一致。这就是本解法的判定基石。仓库中的实现 869. Reordered Power of 2.go 用isSame函数完成这一比较统计t候选 2 的幂中字符频次再遍历sN的字符串逐字符抵消最终map为空即判定频次一致。值得一提的是题目要求前导位不能为 0而频次相等天然保证了两数位数相同因此前导 0 问题在这一比较框架下不会产生错误匹配例如10与1位数不同绝不会被判为相等。核心二利用数据范围枚举 2 的幂此题数据量比较小在[1, 10^9]这个区间内2 的幂只有 30 个从2^0 1到2^29 5368709122^30 1073741824已超出上限。所以最终需要参与比对的字符串就是这 30 几个。仓库解法没有打表而是采用更一般的做法从i 1开始不断执行i i 1等价于i * 2依次生成所有 2 的幂逐一与N的字符串比较。循环终止条件是当前 2 的幂的位数已经超过N的位数——此时位数不可能再相等枚举自然结束。这种写法不依赖硬编码的幂表即使数据范围更大、位长更长代码也能直接复用通过。代码实现完整代码如下与仓库 869. Reordered Power of 2.go 保持一致package leetcode import fmt func reorderedPowerOf2(n int) bool { sample, i : fmt.Sprintf(%v, n), 1 for len(fmt.Sprintf(%v, i)) len(sample) { t : fmt.Sprintf(%v, i) if len(t) len(sample) isSame(t, sample) { return true } i i 1 } return false } func isSame(t, s string) bool { m : make(map[rune]int) for _, v : range t { m[v] } for _, v : range s { m[v]-- if m[v] 0 { return false } if m[v] 0 { delete(m, v) } } return len(m) 0 }逐段讲解主函数reorderedPowerOf2sample : fmt.Sprintf(%v, n)先把输入整数N转成十进制字符串作为比对基准。这里用%v格式化整数效果等同strconv.Itoa。i : 1从最小的 2 的幂2^0 1开始枚举。循环条件len(fmt.Sprintf(%v, i)) len(sample)只要当前幂的位数不超过N的位数就继续。由于幂随i单调增大、位数单调不减一旦位数超过N后续所有幂位数都更大不可能再与N重排相等循环可以安全终止。当len(t) len(sample)时说明位数一致才调用isSame做频次判定位数不同则直接跳过避免了无意义的字符比较。每轮迭代末尾i i 1用位运算完成乘 2既高效又体现了 2 的幂本质。辅助函数isSame第一遍遍历tm[v]记录候选幂中每个数字字符的频次。第二遍遍历sm[v]--用N的字符逐一抵消。若m[v] 0说明s中某字符比t多两串频次不可能一致立即返回false短路剪枝若m[v] 0将该键从map删除保持map只存尚未抵消完的字符最终len(m) 0意味着所有字符都被完全抵消即两个字符串的字符构成完全相同——N可以重排得到这个 2 的幂。复杂度分析设N的十进制位数为d本题d ≤ 10时间位数不超过d的 2 的幂约d × log₂10 ≈ 3.32d个每个幂做一次O(d)的频次比较总复杂度约O(d²)。在d ≤ 10时执行次数约为百次量级性能开销极小。空间isSame中map最多容纳d个键空间复杂度O(d)。测试用例验证仓库为该题提供了完整的单元测试 869. Reordered Power of 2_test.go覆盖了题目给出的全部示例并额外补充了边界与随机用例输入n预期输出说明1true本身就是2^010false重排后只有01前导 0 非法与10均非 2 的幂16true本身是2^424false可重排为24、42均非 2 的幂46true重排为64 2^6100false前导 0 限制下重排无效123453242false较大数据的负例其中123453242这类 9 位数用例验证了算法在接近数据上限10^9时依然能快速给出结论。测试函数Test_Problem869采用表驱动写法将每个用例作为question869{para869{...}, ans869{...}}结构体组织后循环断言与仓库其他题目的测试风格保持一致。可以通过以下命令单独运行该题的测试仓库根目录执行go test ./leetcode/0869.Reordered-Power-of-2/ -v -run Test_Problem869若需连同整个仓库一起回归并统计覆盖率可参考仓库根目录的 gotest.sh其核心命令为go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...该脚本使用 Go 1.10 的多包一次性-coverprofile写法直接产出单一合法的覆盖率文件与本仓库100% test coverage的工程约定一致。延伸思考打表 vs 通用枚举不少题解会直接硬编码[1, 2, 4, 8, ...]这张 2 的幂表。本仓库实现刻意放弃打表改用i 1实时生成换来两个好处可读性更接近问题本质代码直接表达枚举所有 2 的幂并与N比较不需要读者对照幂表核对边界可扩展性若题目把数据范围放宽到10^18甚至更大只需相应放宽循环条件代码本身对位长无硬编码假设解法依旧成立。这一取舍也提示了一个通用的算法思维当候选集合规模小且可快速生成时本题仅 30 个候选动态生成 特征比较往往比离线打表更简洁、更不易出错。小结判定两数互为数字重排 ⇔ 判定两数十进制字符串的字符频次完全一致用i 1与位数剪枝枚举所有可能匹配的 2 的幂避免打表硬编码isSame用一张map完成加频次、减频次、归零即删的抵消式比较配合提前false短路兼顾正确性与效率。完整可运行的解法与测试见 leetcode/0869.Reordered-Power-of-2可结合 README.md 中的原题描述对照学习。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考