侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【数学, 迭代, 递归】丑数

GabrielxD
2022-09-28 / 0 评论 / 0 点赞 / 16 阅读 / 649 字 / 正在检测是否收录...

题目

263. 丑数


丑数 就是只包含质因数 235 的正整数。

给你一个整数 n ,请你判断 n 是否为 丑数 。如果是,返回 true ;否则,返回 false

示例 1:

输入:n = 6
输出:true
解释:6 = 2 × 3

示例 2:

输入:n = 1
输出:true
解释:1 没有质因数,因此它的全部质因数是 {2, 3, 5} 的空集。习惯上将其视作第一个丑数。

示例 3:

输入:n = 14
输出:false
解释:14 不是丑数,因为它包含了另外一个质因数 7 。

提示:

  • -2^31 <= n <= 2^31 - 1

解题

方法一:数学 递归

思路

首先,根据丑数的定义,n0n \le 0 时一定不是丑数,直接返回 false
然后根据定义,当 n>0n>0 时如果 nn 是丑数,那么它一定可以写成 n=2a×3b×5c(a0,b0,c0)n = 2^a \times 3^b \times 5^c (a\ge0,b\ge0,c\ge0) 的形式,而当 a=b=c=0a=b=c=0n=1n = 1,正是第一个丑数。

于是就可以递归求解:

  • n 能被 55 整除时,isUgly(n) 可以转换为 isUlgy(n / 5)
  • n 能被 33 整除时,isUgly(n) 可以转换为 isUlgy(n / 3)
  • n 能被 22 整除时,isUgly(n) 可以转换为 isUlgy(n / 2)
  • n 不能被 223355 整除时,若 n=1n=1,则说明 nn 不包含其他质因数,是丑数;否则,说明 nn 包含其他质因数,不是丑数。

代码

class Solution {
    public boolean isUgly(int n) {
        if (n <= 0) return false;
        if (n % 5 == 0) return isUgly(n / 5);
        if (n % 3 == 0) return isUgly(n / 3);
        if ((n & 1) == 0) return isUgly(n >> 1);
        return n == 1;
    }
}

方法二:数学 迭代

思路

思路与递归差不多,反复地把 nn 除以 2,3,52,3,5,直到 nn 不再包含质因数 2,3,52,3,5。若剩下的数等于 11,则说明 nn 不包含其他质因数,是丑数;否则,说明 nn 包含其他质因数,不是丑数。

参考:https://leetcode.cn/problems/ugly-number/solution/chou-shu-by-leetcode-solution-fazd/

代码

class Solution {
    public boolean isUgly(int n) {
        if (n <= 0) return false;
        while (n % 5 == 0) n /= 5;
        while (n % 3 == 0) n /= 3;
        while ((n & 1) == 0) n >>= 1;
        return n == 1;
    }
}
0

评论区