LeetCode 263. Ugly Number 题解Go 实现判断丑数只含质因数 2、3、5【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go丑数Ugly Number是只含质因数 2、3、5 的正整数本题要求判断任意给定整数是否满足该定义。本文以 LeetCode-Go 仓库中 0263.Ugly-Number 的题解文档为骨架结合仓库内实际提交的 Go 源码与单元测试完整讲解题目约束、逐行实现、复杂度分析、边界情况处理与测试运行方式并顺带梳理仓库中同系列的 264、1201 题帮助你掌握质因数分解判定这一类题目的标准解法。读完后你将能独立写出正确、简洁且覆盖负数与零等边界输入的丑数判定代码。题目回顾Write a program to check whether a given number is an ugly number.Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.即编写一个程序判断给定的数字是否为丑数。丑数被定义为只包含质因数 2、3、5 的正整数。题目给出了三个经典示例与仓库测试用例一一对应示例 1Input: 6 Output: true Explanation: 6 2 × 36 可以分解为 2 × 3两个质因数都在 {2, 3, 5} 集合内因此是丑数。示例 2Input: 8 Output: true Explanation: 8 2 × 2 × 28 只包含质因数 2出现三次因此是丑数。示例 3Input: 14 Output: false Explanation: 14 is not ugly since it includes another prime factor 7.14 2 × 7其中 7 不在 {2, 3, 5} 集合内因此不是丑数。题目附带的两个重要说明1 通常被视为丑数1 没有任何质因数按照惯例算作丑数输入范围输入为 32 位有符号整数即区间 [−2^31, 2^31 − 1]包含负数与零因此判定逻辑必须显式处理非正数。解题思路原文档给出的思路非常精炼——依照题意要求做即可。展开来说这是一个纯粹的质因数分解判定问题核心思路分三步排除非正数丑数必须是正数因此任何num 0直接返回false反复除以 2、3、5只要当前数字仍能被 2、3、5 中的某一个整除就持续除以它把所有属于 {2, 3, 5} 的质因数全部剥掉收尾判断若最终剩下的数字是 1说明原数字除 2、3、5 之外没有其他质因数是丑数否则说明还存在其他质因子如 7、11 等返回false。这种不断整除并检查余数是否为 1的模式本质上是把 LeetCode 204. Count-Primes 一类质数判定中的试除思想反过来使用不是去枚举候选质数而是只针对题目限定的三个质因数做整除从而把时间复杂度压到 O(log n) 量级。仓库源码逐行解析仓库 0263.Ugly-Number 目录下的核心实现位于 263. Ugly Number.go完整代码如下package leetcode func isUgly(num int) bool { if num 0 { for _, i : range []int{2, 3, 5} { for num%i 0 { num / i } } } return num 1 }逐行拆解这段代码的设计代码片段作用与设计考量if num 0 { ... }只对正数执行质因数剥离。负数与 0 直接跳过整个循环走到最后的return num 1时由于num非正数永远不等于 1天然返回false。这个外层判断同时起到了丑数必须是正数的约束作用无需单独写num 0的提前返回。for _, i : range []int{2, 3, 5}外层循环固定遍历题目限定的三个质因数。以字面量切片承载常量集合代码紧凑、可读性高。for num%i 0 { num / i }内层循环用取模判断能否整除能整除则连续除以i。例如对 8 会连续除以 2 三次num最终变为 1。注意 Go 的整数除法会向零截断但在num%i 0保证整除的前提下除法结果必然是精确的不存在精度损失。return num 1循环结束后唯一合法的剩余值就是 1。若剩余值大于 1说明它含有非 2、3、5 的质因子。该函数属于package leetcode与仓库其他题解共用同一包isUgly函数名与 LeetCode 官方函数签名一致可直接被 263. Ugly Number_test.go 中的测试用例调用。正确性论证可以用数学归纳的方式验证算法的正确性对任意输入n内层循环等价于计算n n / (2^a * 3^b * 5^c)其中a、b、c是 n 中 2、3、5 因子的最大指数。显然2^a * 3^b * 5^c只含质因数 2、3、5。若n 1则n的全部质因数都来自 {2, 3, 5}是丑数若n 1则n至少含有一个不在集合内的质因子比如 7、11、13……n不是丑数。而n 0时在if num 0处被拦截不可能返回true。因此判定与定义严格等价。复杂度分析时间复杂度每次除法至少将num减半或缩至 1/3、1/5迭代次数约为 O(log₅ num) 量级对 32 位有符号整数而言最坏情况如2^31 - 1下常数极小可视为 O(log n)空间复杂度O(1)仅使用常数个变量与一个固定长度的字面量切片不随输入规模增长。边界情况与输入范围分析原文档明确说明输入处于 32 位有符号整数范围 [−2^31, 2^31 − 1]结合实现可将全部输入划分为四类边界场景num 0含 −2^31 与 0num 0为假直接返回false。负数虽然也可能被 2、3、5 整除但丑数定义限定为正数因此一律判否。num 1不进入任何内层循环num保持 1num 1成立返回true与题目1 通常被视为丑数的约定一致。num 2^31 - 1最大正整数该值是质数无法被 2、3、5 整除最终num不变返回false不会发生溢出。纯 2、3、5 幂次的组合如 6、8、12、30、2^15 × 3^10 × 5^6 等所有质因子被剥离后余 1返回true。值得一提的是这段实现并不依赖任何乘法或加法运算因此即使在 32 位边界输入上也绝对安全没有整数溢出风险。这也是只做除法、不做乘法这一写法天然带来的健壮性优势。测试用例与验证仓库为本题提供了完整的表驱动测试位于 263. Ugly Number_test.go其结构与原文档中的三个示例完全对齐package leetcode import ( fmt testing ) type question263 struct { para263 ans263 } // para 是参数 // one 代表第一个参数 type para263 struct { one int } // ans 是答案 // one 代表第一个答案 type ans263 struct { one bool } func Test_Problem263(t *testing.T) { qs : []question263{ { para263{6}, ans263{true}, }, { para263{8}, ans263{true}, }, { para263{14}, ans263{false}, }, } fmt.Printf(------------------------Leetcode Problem 263------------------------\n) for _, q : range qs { _, p : q.ans263, q.para263 fmt.Printf(【input】:%v 【output】:%v\n, p, isUgly(p.one)) } fmt.Printf(\n\n\n) }测试覆盖了 6 →true、8 →true、14 →false三组数据恰好对应原文档的示例 1、2、3。question263结构体将输入参数para263与期望答案ans263绑定是仓库中统一的表驱动测试风格方便后续按需扩充用例例如补充1、0、-6、2147483647等边界值。若需在本仓库环境中实际运行验证仓库根目录提供了统一的测试脚本 gotest.sh其对全部 leetcode 包执行覆盖率收集go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...也可以只针对本题所在包运行go test -v ./leetcode/0263.Ugly-Number/项目 go.mod 声明模块github.com/halfrost/LeetCode-Go、Go 版本 1.19并内置了structures、template等本地辅助模块的 replace 指令直接go test即可编译运行。丑数系列的延伸阅读丑数问题在 LeetCode 上是一整个系列仓库均收录了对应题解可与本题对照学习264. Ugly Number II求第 n 个丑数。从判断单个数字升级为按序生成丑数序列仓库给出的解法采用三指针 DP 数组时间复杂度 O(n)是本题思路的进阶延伸1201. Ugly Number III求能被 a、b、c 整除的第 n 个正整数属于丑数概念的变体以任意三个数为质因子集合配合二分查找与容斥原理求解。从 263 的简单除法判定到 264 的 DP 生成再到 1201 的二分 容斥恰好构成了丑数主题下从易到难的能力进阶路径。总结LeetCode 263 题的核心价值在于两点一是对质因数分解判定这一基础数论技能的考察二是对边界处理严谨性的考察——题目特意给出 32 位有符号整数范围与1 是丑数的约定就是为了逼出遗漏负数、零或 1 的粗糙实现。仓库提供的 Go 解法以if num 0拦截非正数、以双重循环剥离 2/3/5 因子、以num 1收尾判定三行核心逻辑即完整覆盖全部边界兼顾了正确性、简洁性与 O(1) 空间复杂度是这类判定题的推荐范式。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考