[LintCode] Ugly Number

raise_yang 發布于2019-08-14 15:20 / 2653人閱讀

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;
    }
}

云服務器 GPU云服務器 Ugly LintCode LintCode134_LRU number

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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