科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载导读本题LeetCode 1780 Check if Number is a Sum of Powers of Three出自第 47 场双周赛要求判断正整数n能否表示成若干个互不相同的 3 的幂之和每个 3 的幂最多使用一次。表面上是一道幂集合枚举类问题实际上一旦把n写成三进制判定条件会收敛为一行n的三进制表示中每一位都只能是 0 或 1一旦出现数字2即无解。本文以 leetcode/biweekly/47/b/1780.md 的官方分析为骨架结合仓库中的 Go 实现 与 自动化测试讲清贪心证明、三进制判定与多语言模板读完即可在任意语言中 5 分钟内写出可提交的解法。一、题目本质n 能否写成互不相同的 3 的幂之和回顾题意示例均来自原文档分析示例 1n 12 9 3其中9 3²、3 3¹互不相同答案是true示例 3n 21 9 9 3两个9重复出现答案是false。也就是说三的幂集合为{1, 3, 9, 27, ...}每个幂要么不选、要么选一次问能否恰好凑出n。枚举子集显然不现实幂个数可多达几十个必须找到结构性判定。二、贪心证明最大的 3 的幂必须被分解出来原文档给出了一个非常关键的自洽性论证这是整个解法的地基示例 1 的n1293其中9是最大的小于等于12的 3 的幂。如果不从12中分出9那么12必须表示为更小的 3 的幂之和即12 (333)3相当于把9分成了若干个相同的3。题目要求不能有相同元素3必须继续分解但这会得到更多的 3 的幂即3 111。所以如果不从12中分出9就无法满足题目要求。推广到一般情形假设存在一个合法的表示且它没有包含不大于n的最大 3 的幂3^k那么3^k这一数值只能由更小的 3 的幂求和得到即3^k 3^(k-1) 3^(k-1) 3^(k-1)。此时3^(k-1)至少出现两次若再继续拆分为3·3^(k-2)则重复次数更多拆到底111依旧重复。因此不取最大幂的方案无论如何都会产生重复元素不可能合法。于是得到结论任何合法表示都必须分解出小于等于n的最大 3 的幂3^k随后问题缩减为规模更小的子问题n n - 3^k。这正是把n表示为三进制的贪心流程每次取出当前剩余值中最大的一次幂位。原文档给出的两个示例正好印证12 110_(3)即9 3第 2、1 位为 1第 0 位为 021 210_(3)即2·9 1·3第 2 位出现了系数2。三、三进制判定出现数字 2 即无解接着看示例 3 的2121 9 9 3。即便把其中一个9继续拆成333得到的3会与原有的3重复再拆3 111重复元素只会更多。这揭示了本质规律三进制表示中某一位为2意味着该幂被使用两次必然导致重复。三进制的每一位系数取值范围是{0, 1, 2}系数0该幂不用系数1该幂用一次系数2该幂用两次——非法。由于每个 3 的幂在表示n的三进制中占且仅占一位判定条件立刻收敛为遍历n的三进制每一位如果其中有2返回false否则返回true。这与n 是否能表示成互不相同的 3 的幂之和完全等价无需任何搜索或回溯。四、遍历三进制的通用套路原文档贴心地回顾了十进制逐位取法的思想三进制只是换底数对于n123计算n mod 10 3取到个位数然后把n除以10下取整得到12再取12 mod 10 2得到十位数依此类推。对于三进制就是计算n mod 3并更新n ⌊n/3⌋直到n 0为止即遍历了n的三进制的每一位。算法主流程伪代码function checkPowersOfThree(n): while n 0: if n % 3 2: return false n floor(n / 3) return true一个可以互相印证的细节由于判定只看每位是否为2n中只要任意一位出现2就可以提前返回false无需把整个三进制算完因此循环往往在几轮内就会终止。五、七种语言实现完整可直接提交原文档给出了 Python3两种写法、Java、C、C、Go、JavaScript、Rust 共 8 段实现这里全部继承并逐段注解核心行。Python3写法一class Solution: def checkPowersOfThree(self, n: int) - bool: while n: if n % 3 2: return False n // 3 return TruePython3写法二divmod 取商与余数class Solution: def checkPowersOfThree(self, n: int) - bool: while n: n, d divmod(n, 3) if d 2: return False return Truedivmod(n, 3)一次返回(n // 3, n % 3)写法上更紧凑逻辑与写法一完全等价。Javaclass Solution { public boolean checkPowersOfThree(int n) { while (n 0) { if (n % 3 2) { return false; } n / 3; } return true; } }Cclass Solution { public: bool checkPowersOfThree(int n) { while (n) { if (n % 3 2) { return false; } n / 3; } return true; } };Cbool checkPowersOfThree(int n) { while (n) { if (n % 3 2) { return false; } n / 3; } return true; }Gofunc checkPowersOfThree(n int) bool { for ; n 0; n / 3 { if n%3 2 { return false } } return true }注意 Go 版把n / 3直接写进了for的 post 子句循环体只保留判定逻辑是典型的 Go 风格紧凑写法。JavaScriptvar checkPowersOfThree function(n) { while (n) { if (n % 3 2) { return false; } n Math.floor(n / 3); } return true; };JS 中除法会产生浮点数必须用Math.floor(n / 3)显式下取整不能省略。Rustimpl Solution { pub fn check_powers_of_three(mut n: i32) - bool { while n 0 { if n % 3 2 { return false; } n / 3; } true } }Rust 需要对参数标注mut才能原地修改ni32在该题数据范围内足够若题目数据范围更大可改用i64。六、复杂度分析时间复杂度O(log₃ n)。每轮循环把n除以 3循环次数约为⌊log₃ n⌋ 1即三进制的位数空间复杂度O(1)只使用常数个变量没有任何辅助数组或递归栈。对于题目的数据范围即使n达到千万级别三进制位数也只有十几位循环常数极小。七、仓库配套Go 实现与自动化测试验证本仓库在 leetcode/biweekly/47/b/b.go 中给出了与题解完全一致的 Go 实现并在 leetcode/biweekly/47/b/b_test.go 中挂载了三个示例用例输入n期望输出说明12true12 9 3三进制11091true91 81 9 1三进制100121false三进制210含数字 2测试文件由 copypasta/template/leetcode/generator_test.go 生成核心是调用 leetcode/testutil/leetcode.go#L237 的RunLeetCodeFuncWithExamples该工具通过反射获取被测试函数的入参/出参数量把用例文本解析成真实参数并自动比对输出targetCaseNum 0表示运行全部用例若设为-1则只跑最后一个用例。测试文件中还留有// TODO 测试入参最小的情况注释即n 1 3⁰这类边界尚未补齐读者可以自行在本地补测。在仓库根目录下运行以下命令即可复现全部判定结果go test ./leetcode/biweekly/47/b/该题解在灵茶山艾府维护的 leetcode/SOLUTIONS.md 分类题解列表中也有收录可作为复习索引。八、边界情况与变体延伸从代码结构推断n 11 3⁰三进制为1合法返回true测试中的 TODO 注释正指向这类最小入参单个幂本身n 3^k时三进制为100...0不含 2返回true提前退出只要遇到任一2立即return false不需要完成整个循环这也是该实现天然具备的微小剪枝。更进一步这套看进制表示中是否含超限数字的思路可以泛化到一般的k进制幂集合问题能否把n表示成若干个互不相同的k的幂之和等价于n的k进制表示中每一位都不超过1。例如二进制k2下每位天然只有0/1所以任意正整数都能表示成互不相同的 2 的幂之和即唯一的二进制分解而三进制因为存在系数2才需要本题这样的额外判定。理解这一层抽象后遇到幂集合 互不相同 恰好凑和类题目可以第一时间想到进制视角。小结LeetCode 1780 的核心结论可以浓缩为一句话把n写成三进制一旦出现数字2就不可能表示成互不相同的 3 的幂之和。支撑它的是两件事——最大幂必须被分解出去的贪心自洽证明以及三进制系数2与幂重复使用的一一对应。配合仓库中 b.go 的 Go 实现和 b_test.go 的测试用例读者既拿到了可直接提交的多语言模板也掌握了可复用的进制判定思维。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐判断二进制中是否恰好含有一个 11力扣双周赛 184 Q1 的两种位运算解法与 codeforces-go 仓库实现剖析判断二进制中是否恰好含有一个 11力扣双周赛 184 Q1 的两种位运算解法与 codeforces go 仓库实现剖析 本篇技术指南围绕 codefor科学计算LeetCode-Book 精选 88 题解析231. 2 的幂——一行位运算判定二的幂LeetCode Book 精选 88 题解析231. 2 的幂——一行位运算判定二的幂 本篇技术指南聚焦于《Krahets 笔面试精选 88 题》中的经典位示例工程LeetCode 0231「2 的幂」题解精讲循环整除、数论取模与位运算三种判定方案AlgoNote 算法通关手册LeetCode 0231「2 的幂」题解精讲循环整除、数论取模与位运算三种判定方案AlgoNote 算法通关手册 本文是「算法通关手册」AlgoNote教程文档知识库上一篇Set with Friends体验极速多人实时卡牌对战乐趣下一篇vue-hackernews-2.0网络请求库对比axios vs fetch API应用创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考