[LintCode] Ugly Number

raise_yang 发布于2019-08-14 15:20 / 2565人阅读

Problem

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. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Example

Given num = 8 return true
Given num = 14 return false

Note

当num非0，用num除以2，3，5直到不能整除，最后余数为1就是ugly num。

Solution

1. Iteration

public class Solution {
    public boolean isUgly(int num) {
        int[] divs = {2, 3, 5};
        for (int div: divs) {
            while (num!= 0 && num % div == 0) {
                num /= div;
            }
        }
        return num == 1;
    }
}

2. Recursion

public class Solution {
    public boolean isUgly(int num) {
        if (num == 0) return false;
        if (num == 1) return true;
        if (num % 2 == 0) return isUgly(num/2);
        if (num % 3 == 0) return isUgly(num/3);
        if (num % 5 == 0) return isUgly(num/5);
        else return false;
    }
}

云服务器服务器托管 Ugly LintCode LintCode134_LRU number

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65643.html

[LintCode/LeetCode] Super Ugly Number

摘要：建两个新数组，一个存数，一个存。数组中所有元素初值都是。实现的过程是，一个循环里包含两个子循环。两个子循环的作用分别是，遍历数组与相乘找到最小乘积存入再遍历一次数组与的乘积，结果与相同的，就将加，即跳过这个结果相同结果只存一次。 Problem Write a program to find the nth super ugly number. Super ugly numbers a...

wuyumin 2019-08-14 15:20 评论0 收藏0
264. Ugly NumberII & 313. Super Ugly Number

摘要：题目解答这个问题最主要的就是如果按顺序找出那么我们如果能想到把以为因子的这些分成三个然后在每次输出时取里最小的那个数输出就可以解决了。 264 Ugly NumberII题目：Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only i...

Lionad-Morotar 2019-08-14 14:06 评论0 收藏0
[Leetcode] Ugly Number 丑陋数

摘要：如果有一个方法能够顺序只生成丑陋数就好了。仔细观察可以发现，丑陋数的因子也必定是丑陋数，它一定是某个丑陋数乘得到的。不过，我们可以确定的是，小的丑陋数乘，肯定小于大的丑陋数乘。 Ugly Number I Write a program to check whether a given number is an ugly number. Ugly numbers are positi...

RobinQu 2019-08-14 16:09 评论0 收藏0
264. Ugly Number II & 313. Super Ugly Number

摘要：每次出一个数，就把这个数的结果都放进去。，指针从个变成个。的做法参考还是复杂度的问题，回头再看看 264. Ugly Number II 题目链接：https://leetcode.com/problems... dp的方法参考discussion：https://discuss.leetcode.com/... dp的subproblem是：dp[i]: i-th ugly numb...

hiyang 2019-08-16 10:29 评论0 收藏0
Leetcode[313] Super Ugly Number

摘要：滚动求最大值复杂度考虑一个，的值是下一个可能的替补值。思路数组中保存的是之前保留到的值，因为下一个可能的值是和之前的值的倍数关系。 Leetcode[313] Super Ugly Number Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whos...

Aklman 2019-08-16 10:27 评论0 收藏0