LeetCode 263 丑数Ugly Number题解质因数分解判断法JS / C / Java / Python 多语言实现【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本篇基于 LeetCode 263「丑数Ugly Number」原题讲解如何通过质因数分解判断一个正整数是否只包含质因子 2、3、5。文章完整继承题解的核心思路与 JS / C / Java / Python 四种实现并进一步结合循环与递归两种写法的原理、复杂度与边界条件做纵深分析帮助读者在面试与刷题中快速识别「丑数 / 超级丑数」这一数论题型的通用套路。读完本文你将掌握丑数判定算法、多语言代码写法及其在仓库知识体系如堆专题中的延伸位置。题目地址与描述题目地址中文版https://leetcode-cn.com/problems/ugly-number/题解文档problems/263.ugly-number.md另有英文版 problems/263.ugly-number.en.md注意题目地址为外部平台链接仅作题目出处说明本文全部解题内容均来自仓库内题解文档。题目描述编写一个程序判断给定的数是否为丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。 示例 1: 输入: 6 输出: true 解释: 6 2 × 3 示例 2: 输入: 8 输出: true 解释: 8 2 × 2 × 2 示例 3: 输入: 14 输出: false 解释: 14 不是丑数因为它包含了另外一个质因数 7。 说明 1 是丑数。 输入不会超过 32 位有符号整数的范围: [−2^31, 2^31 − 1]。前置知识数学质数、质因数质因子的概念因数分解将合数拆解为若干个质数相乘的形式题目归类与高频考点原文档标注此题出现在阿里、腾讯、百度、字节等公司的面试题单中collections/easy.md 亦将本题收录于 Easy 难度合集英文版见 collections/easy.en.md。其核心考点是数论 因数分解属于面试中考察基础数学功底的入门级题目。解题思路质因数分解判断法丑数的定义是只包含质因子 2、3、5 的正整数。根据定义我们只需将给定数字反复除以 2、3、5顺序无所谓直到无法整除为止如果最后得到 1说明该数的所有质因子都是 2 或 3 或 5即为丑数如果最后不是 1说明它还携带了其他质因子不是丑数。这一步与「判断一个数是否为 nn 为大于 1 的正整数的幂次方」的思路完全一致不断除以 n直到无法整除若结果为 1 则是 n 的幂。本题的差异仅在于除数从一个 n 变成了三个数2、3、5但解题骨架完全相同。下面这张图解通过两个数字的质因子分解对比直观展示了丑数判定的核心逻辑如图所示20分解为2 × 2 × 5质因子全部落在 {2, 3, 5} 集合内是丑数而22分解为2 × 11包含质因子 11不是丑数。核心伪代码循环写法如下while (num % 2 0) num num / 2; while (num % 3 0) num num / 3; while (num % 5 0) num num / 5; return num 1;关键点数论质因子分解的唯一性算术基本定理因数分解用取模%判断能否整除用除法/逐步剥离因子边界处理非正整数num 0直接返回falsenum 1按题意是丑数返回true多语言代码实现原文档题解支持JS、C、Java、Python四种语言下面逐一展开并补充关键注释与边界说明。JavaScript递归写法原文档中的 JS 版使用递归实现并特别注明「我下方给出的代码是用了递归实现只是给大家看下不同的写法而已」——即递归与循环在思路上等价选择哪种取决于个人习惯。/* * lc appleetcode id263 langjavascript * * [263] Ugly Number */ /** * param {number} num * return {boolean} */ var isUgly function (num) { // TAG: 数论 if (num 0) return false; // 非正整数一定不是丑数 if (num 1) return true; // 1 是丑数没有任何质因子 const list [2, 3, 5]; if (list.includes(num)) return true; // 本身就是 2 / 3 / 5 之一 for (let i of list) { if (num % i 0) return isUgly(Math.floor(num / i)); // 能整除则递归剥离该因子 } return false; // 都不能整除说明携带其他质因子 };递归写法复杂度分析时间复杂度$O(logN)$空间复杂度$O(logN)$递归调用栈深度与剥因子轮数成正比C循环写法class Solution { public: bool isUgly(int num) { int ugly[] {2,3,5}; for(int u : ugly) { while(num%u0 num%u num) { num/u; } } return num 1; } };说明while(num%u0 num%u num)中的第二个条件用于防御num 0时死循环的情况——当num为 0 时0 % u 0恒成立若无附加判断将无限除以u。实际提交时更常见的写法是显式处理num 0后直接while (num % u 0) num / u;。Java循环写法class Solution { public boolean isUgly(int num) { int [] ugly {2,3,5}; for(int u : ugly) { while(num%u0 num%u num) { num/u; } } return num 1; } }Java 版与 C 版结构完全一致均为「遍历因子集合 {2,3,5} 内层循环剥离」的写法。Python非递归写法# 非递归写法 class Solution: def isUgly(self, num: int) - bool: if num 0: return False for i in (2, 3, 5): while num % i 0: num / i return num 1循环写法复杂度分析时间复杂度$O(logN)$空间复杂度$O(1)$仅使用常数级额外空间无递归栈小结同一算法两种实现方式递归版空间 $O(logN)$循环版空间 $O(1)$时间均为 $O(logN)$。从空间占用看循环写法更优。边界条件与陷阱非正整数num 0一律返回false。题目限定输入范围为 32 位有符号整数[−2^31, 2^31 − 1]因此负数与 0 必须显式排除否则%运算语义会偏离题意。1 的处理按题意1是丑数它没有任何质因子可视为 2⁰×3⁰×5⁰需单独返回true。除零 / 死循环防御C / Java 写法中num%u num条件本质是防御num 0时的死循环0 % 2 0恒真。若改用先判num 0再循环则可直接省略该条件。浮点误差Python 中num / i得到 float极端大数下除法可能引入精度问题若追求严格可用num // i整型整除。仓库原文档给出的即/写法遵循题目给定的 32 位整数范围是可接受的。从丑数到超级丑数仓库知识体系的延伸丑数判定是「丑数家族」问题的第一环。在仓库的堆专题 thinkings/heap.md 与 thinkings/heap-2.md 中作者将丑数问题推广到了两个经典变体264. 丑数 II求第 n 个丑数因子集合固定为 {2,3,5}可用**三个指针多路归并**或堆解决参见 thinkings/heap-2.md 第 1410 行附近的分析「因子个数有限不使用堆也容易解决……就可以使用三个指针来记录即可」。313. 超级丑数给定任意质数列表primes求第 n 个超级丑数。核心性质是「超级丑数一定可以写成a^x1 * b^x2 * c^x3 ...的形式」thinkings/heap.md 中给出了多路归并与堆两种解法的完整推导与 Java 实现。thinkings/heap-2.md 还特别点明了一个可复用的套路结论「丑数就是质因数只包含 2, 3, 5 的正整数本质就是因子分解之后只剩 2、3、5 的整数……大多数丑数题目都可以从堆的角度考虑只不过因子个数有限时不使用堆也容易解决」。因此先掌握本题的质因数分解判断法再向第 k 个丑数 / 超级丑数递进是一条完整的数论 堆的进阶路径。总结核心思想反复除以 2、3、5最终结果是否为 1 即丑数判定的充要条件。与「判断 n 的幂」同构只是除数从单个 n 扩展为 {2,3,5} 三个因子。四种语言实现JS 递归 / C 循环 / Java 循环 / Python 循环思路一致时间复杂度 $O(logN)$循环版空间 $O(1)$。注意边界num 0返回 false1返回 true循环写法避免除以 0 死循环。进阶方向264 丑数 II多路归并三指针、313 超级丑数堆 / 多路归并见仓库堆专题与 heap-2 专题。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 263 丑数（Ugly Number）题解：质因数分解判断法（JS / C++ / Java / Python 多语言实现）
LeetCode 263 丑数Ugly Number题解质因数分解判断法JS / C / Java / Python 多语言实现【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本篇基于 LeetCode 263「丑数Ugly Number」原题讲解如何通过质因数分解判断一个正整数是否只包含质因子 2、3、5。文章完整继承题解的核心思路与 JS / C / Java / Python 四种实现并进一步结合循环与递归两种写法的原理、复杂度与边界条件做纵深分析帮助读者在面试与刷题中快速识别「丑数 / 超级丑数」这一数论题型的通用套路。读完本文你将掌握丑数判定算法、多语言代码写法及其在仓库知识体系如堆专题中的延伸位置。题目地址与描述题目地址中文版https://leetcode-cn.com/problems/ugly-number/题解文档problems/263.ugly-number.md另有英文版 problems/263.ugly-number.en.md注意题目地址为外部平台链接仅作题目出处说明本文全部解题内容均来自仓库内题解文档。题目描述编写一个程序判断给定的数是否为丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。 示例 1: 输入: 6 输出: true 解释: 6 2 × 3 示例 2: 输入: 8 输出: true 解释: 8 2 × 2 × 2 示例 3: 输入: 14 输出: false 解释: 14 不是丑数因为它包含了另外一个质因数 7。 说明 1 是丑数。 输入不会超过 32 位有符号整数的范围: [−2^31, 2^31 − 1]。前置知识数学质数、质因数质因子的概念因数分解将合数拆解为若干个质数相乘的形式题目归类与高频考点原文档标注此题出现在阿里、腾讯、百度、字节等公司的面试题单中collections/easy.md 亦将本题收录于 Easy 难度合集英文版见 collections/easy.en.md。其核心考点是数论 因数分解属于面试中考察基础数学功底的入门级题目。解题思路质因数分解判断法丑数的定义是只包含质因子 2、3、5 的正整数。根据定义我们只需将给定数字反复除以 2、3、5顺序无所谓直到无法整除为止如果最后得到 1说明该数的所有质因子都是 2 或 3 或 5即为丑数如果最后不是 1说明它还携带了其他质因子不是丑数。这一步与「判断一个数是否为 nn 为大于 1 的正整数的幂次方」的思路完全一致不断除以 n直到无法整除若结果为 1 则是 n 的幂。本题的差异仅在于除数从一个 n 变成了三个数2、3、5但解题骨架完全相同。下面这张图解通过两个数字的质因子分解对比直观展示了丑数判定的核心逻辑如图所示20分解为2 × 2 × 5质因子全部落在 {2, 3, 5} 集合内是丑数而22分解为2 × 11包含质因子 11不是丑数。核心伪代码循环写法如下while (num % 2 0) num num / 2; while (num % 3 0) num num / 3; while (num % 5 0) num num / 5; return num 1;关键点数论质因子分解的唯一性算术基本定理因数分解用取模%判断能否整除用除法/逐步剥离因子边界处理非正整数num 0直接返回falsenum 1按题意是丑数返回true多语言代码实现原文档题解支持JS、C、Java、Python四种语言下面逐一展开并补充关键注释与边界说明。JavaScript递归写法原文档中的 JS 版使用递归实现并特别注明「我下方给出的代码是用了递归实现只是给大家看下不同的写法而已」——即递归与循环在思路上等价选择哪种取决于个人习惯。/* * lc appleetcode id263 langjavascript * * [263] Ugly Number */ /** * param {number} num * return {boolean} */ var isUgly function (num) { // TAG: 数论 if (num 0) return false; // 非正整数一定不是丑数 if (num 1) return true; // 1 是丑数没有任何质因子 const list [2, 3, 5]; if (list.includes(num)) return true; // 本身就是 2 / 3 / 5 之一 for (let i of list) { if (num % i 0) return isUgly(Math.floor(num / i)); // 能整除则递归剥离该因子 } return false; // 都不能整除说明携带其他质因子 };递归写法复杂度分析时间复杂度$O(logN)$空间复杂度$O(logN)$递归调用栈深度与剥因子轮数成正比C循环写法class Solution { public: bool isUgly(int num) { int ugly[] {2,3,5}; for(int u : ugly) { while(num%u0 num%u num) { num/u; } } return num 1; } };说明while(num%u0 num%u num)中的第二个条件用于防御num 0时死循环的情况——当num为 0 时0 % u 0恒成立若无附加判断将无限除以u。实际提交时更常见的写法是显式处理num 0后直接while (num % u 0) num / u;。Java循环写法class Solution { public boolean isUgly(int num) { int [] ugly {2,3,5}; for(int u : ugly) { while(num%u0 num%u num) { num/u; } } return num 1; } }Java 版与 C 版结构完全一致均为「遍历因子集合 {2,3,5} 内层循环剥离」的写法。Python非递归写法# 非递归写法 class Solution: def isUgly(self, num: int) - bool: if num 0: return False for i in (2, 3, 5): while num % i 0: num / i return num 1循环写法复杂度分析时间复杂度$O(logN)$空间复杂度$O(1)$仅使用常数级额外空间无递归栈小结同一算法两种实现方式递归版空间 $O(logN)$循环版空间 $O(1)$时间均为 $O(logN)$。从空间占用看循环写法更优。边界条件与陷阱非正整数num 0一律返回false。题目限定输入范围为 32 位有符号整数[−2^31, 2^31 − 1]因此负数与 0 必须显式排除否则%运算语义会偏离题意。1 的处理按题意1是丑数它没有任何质因子可视为 2⁰×3⁰×5⁰需单独返回true。除零 / 死循环防御C / Java 写法中num%u num条件本质是防御num 0时的死循环0 % 2 0恒真。若改用先判num 0再循环则可直接省略该条件。浮点误差Python 中num / i得到 float极端大数下除法可能引入精度问题若追求严格可用num // i整型整除。仓库原文档给出的即/写法遵循题目给定的 32 位整数范围是可接受的。从丑数到超级丑数仓库知识体系的延伸丑数判定是「丑数家族」问题的第一环。在仓库的堆专题 thinkings/heap.md 与 thinkings/heap-2.md 中作者将丑数问题推广到了两个经典变体264. 丑数 II求第 n 个丑数因子集合固定为 {2,3,5}可用**三个指针多路归并**或堆解决参见 thinkings/heap-2.md 第 1410 行附近的分析「因子个数有限不使用堆也容易解决……就可以使用三个指针来记录即可」。313. 超级丑数给定任意质数列表primes求第 n 个超级丑数。核心性质是「超级丑数一定可以写成a^x1 * b^x2 * c^x3 ...的形式」thinkings/heap.md 中给出了多路归并与堆两种解法的完整推导与 Java 实现。thinkings/heap-2.md 还特别点明了一个可复用的套路结论「丑数就是质因数只包含 2, 3, 5 的正整数本质就是因子分解之后只剩 2、3、5 的整数……大多数丑数题目都可以从堆的角度考虑只不过因子个数有限时不使用堆也容易解决」。因此先掌握本题的质因数分解判断法再向第 k 个丑数 / 超级丑数递进是一条完整的数论 堆的进阶路径。总结核心思想反复除以 2、3、5最终结果是否为 1 即丑数判定的充要条件。与「判断 n 的幂」同构只是除数从单个 n 扩展为 {2,3,5} 三个因子。四种语言实现JS 递归 / C 循环 / Java 循环 / Python 循环思路一致时间复杂度 $O(logN)$循环版空间 $O(1)$。注意边界num 0返回 false1返回 true循环写法避免除以 0 死循环。进阶方向264 丑数 II多路归并三指针、313 超级丑数堆 / 多路归并见仓库堆专题与 heap-2 专题。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考