[LintCode] Ugly Number

raise_yang 發(fā)布于2019-08-14 15:20 / 2660人閱讀

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

當(dāng)num非0，用num除以2，3，5直到不能整除，最后余數(shù)為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;
    }
}

云服務(wù)器 GPU云服務(wù)器 Ugly LintCode LintCode134_LRU number

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65643.html

相關(guān)文章

[LintCode/LeetCode] Super Ugly Number

摘要：建兩個(gè)新數(shù)組，一個(gè)存數(shù)，一個(gè)存。數(shù)組中所有元素初值都是。實(shí)現(xiàn)的過程是，一個(gè)循環(huán)里包含兩個(gè)子循環(huán)。兩個(gè)子循環(huán)的作用分別是，遍歷數(shù)組與相乘找到最小乘積存入再遍歷一次數(shù)組與的乘積，結(jié)果與相同的，就將加，即跳過這個(gè)結(jié)果相同結(jié)果只存一次。 Problem Write a program to find the nth super ugly number. Super ugly numbers a...

wuyumin 2019-08-14 15:20 評(píng)論0 收藏0
264. Ugly NumberII & 313. Super Ugly Number

摘要：題目解答這個(gè)問題最主要的就是如果按順序找出那么我們?nèi)绻芟氲桨岩詾橐蜃拥倪@些分成三個(gè)然后在每次輸出時(shí)取里最小的那個(gè)數(shù)輸出就可以解決了。 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 評(píng)論0 收藏0
[Leetcode] Ugly Number 丑陋數(shù)

摘要：如果有一個(gè)方法能夠順序只生成丑陋數(shù)就好了。仔細(xì)觀察可以發(fā)現(xiàn)，丑陋數(shù)的因子也必定是丑陋數(shù)，它一定是某個(gè)丑陋數(shù)乘得到的。不過，我們可以確定的是，小的丑陋數(shù)乘，肯定小于大的丑陋數(shù)乘。 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 評(píng)論0 收藏0
264. Ugly Number II & 313. Super Ugly Number

摘要：每次出一個(gè)數(shù)，就把這個(gè)數(shù)的結(jié)果都放進(jìn)去。，指針從個(gè)變成個(gè)。的做法參考還是復(fù)雜度的問題，回頭再看看 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 評(píng)論0 收藏0
Leetcode[313] Super Ugly Number

摘要：滾動(dòng)求最大值復(fù)雜度考慮一個(gè)，的值是下一個(gè)可能的替補(bǔ)值。思路數(shù)組中保存的是之前保留到的值，因?yàn)橄乱粋€(gè)可能的值是和之前的值的倍數(shù)關(guān)系。 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 評(píng)論0 收藏0