LeetCode算法题-Ugly Number(Java实现-四种解法)

作者 : 开心源码 本文共1441个字,预计阅读时间需要4分钟 发布时间: 2022-05-12 共118人阅读

这是悦乐书的第199次升级,第208篇原创

01 看题和准备

今天详情的是LeetCode算法题中Easy级别的第64题(顺位题号是263)。编写一个程序来检查给定的数字能否是一个丑陋的数字。丑陋的数字是正数,其主要因子仅包括2,3,5。例如:

输入:6
输出:true
说明:6 = 2×3

输入:8
输出:true
说明:8 = 2×2×2

输入:14
输出:false
说明:14并不丑陋,由于它包含另一个因子7。

注意:

  • 1通常被视为丑陋的数字。

  • 输入在32位有符号整数范围内:[ -2^31, 2^31 – 1]。

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

特殊情况:1是丑陋数字,小于等于0的不是丑陋数字。

正常情况:num假如是丑陋数字,可以分为两种情况:一是单纯的某一因子的幂次方,二是三个因子的随机排列组合,可能两个一起出现,也有可能三个一起出现。除以这三个因子中的一个,最后商是1,则说明这个数是丑陋数字;除以这三个因子中的两个或者三个,最后商是1,那么这个数也是丑陋数字。

对此,使用两层循环,外层循环控制因子,从2开始,一直到5,中间有个4其实就是2的平方,也可以算作其中的一个因子,内层循环先判断对当前因子取余能否等于0,假如不等于0则说明可能是另外的因子的积,也有可能不是丑陋数字,假如等于0,则除以当前因子获取商,重新赋值给num,继续判断和循环。

public boolean isUgly(int num) {    if (num > 0) {        for (int i = 2; i < 6; i++) {            while (num % i == 0) {                num /= i;            }        }    }    return num == 1;}

03 第二种解法

将2,3,5这三个因子放入数组,使用两层循环,外层依次取出数组中的因子,内层做取余判断和求商,前提条件是num大于0。

public boolean isUgly2(int num) {    if (num > 0) {        int[] arr = {2, 3, 5};        for (int d : arr) {            while (num % d == 0) {                num /= d;            }        }    }    return num == 1;}

04 第三种解法

也可以分开来计算商,使用3个循环分开判断取余和求商,最后判断num等不等于1。

public boolean isUgly3(int num) {    if (num > 0) {        while (num % 2 == 0) {            num /= 2;        }        while (num % 3 == 0) {            num /= 3;        }        while (num % 5 == 0) {            num /= 5;        }    }    return num == 1;}

05 第四种解法

使用递归的解法,判断逻辑和上面两种解法一样,对2取余等于0的话,除以2后继续调用自身,对于3和5,情况一样,最后判断能否等于1。

public boolean isUgly4(int num) {    if (num <= 0) {        return false;    }    if (num % 2 == 0) {        return isUgly4(num/=2);    }    if (num % 3 == 0) {        return isUgly4(num/=3);    }    if (num % 5 == 0) {        return isUgly4(num/=5);    }    return num == 1;}

06 小结

算法专题目前已连续日更超过一个月,算法题文章64+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是一律内容,假如大家有什么好的解法思路、建议或者者其余问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » LeetCode算法题-Ugly Number(Java实现-四种解法)

发表回复