LeetCode 263. Ugly Number

简介: 编写一个程序判断给定的数是否为丑数。丑数就是只包含质因数 2, 3, 5 的正整数。

v2-5b45bbf06cce9efd32fed88d576846d4_1440w.jpg

Description



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.


Example 1:

Input: 6

Output: true

Explanation: 6 = 2 × 3


Example 2:

Input: 8

Output: true

Explanation: 8 = 2 × 2 × 2


Example 3:

Input: 14

Output: false

Explanation: 14 is not ugly since it includes another prime factor 7.


Note:

1 is typically treated as an ugly number.

Input is within the 32-bit signed integer range: [−231, 231 − 1].


描述



编写一个程序判断给定的数是否为丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。


示例 1:

输入: 6

输出: true

解释: 6 = 2 × 3


示例 2:

输入: 8

输出: true

解释: 8 = 2 × 2 × 2


示例 3:

输入: 14

输出: false

解释: 14 不是丑数,因为它包含了另外一个质因数 7。


说明:

1 是丑数。

输入不会超过 32 位有符号整数的范围: [−231, 231 − 1]。


思路



  • 根据题意丑数一定可以写成


v2-c0049c3f1ca124de8b23d87edbb3ea71_720w.png


  • 我们依次从给定的数字中去除因子2,3,5 如果给定的数符合丑数的条件,那么最后剩下的数字一定是1,如果不是1,说明给定的数字不是丑数.


# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-02-03 09:30:18
# @Last Modified by:   何睿
# @Last Modified time: 2019-02-03 10:05:52
class Solution:
    def isUgly(self, num):
        """
        :type num: int
        :rtype: bool
        """
        if num <= 0: return False
        for factor in [2, 3, 5]:
            # 用给定的数模上给定的因子,如果结果为0说明还能从
            # 给定的数字中至少分解出一个当前因子
            # 如果不为零,我们用当前的数给下一个因子取模
            while not num % factor:
                num /= factor
        # 如果是丑数,那么最后的结果一定是1
        if num == 1: return True
        return False


源代码文件在这里.


目录
相关文章
|
算法
Leetcode 313. Super Ugly Number
题目翻译成中文是『超级丑数』,啥叫丑数?丑数就是素因子只有2,3,5的数,7 14 21不是丑数,因为他们都有7这个素数。 这里的超级丑数只是对丑数的一个扩展,超级丑数的素因子不再仅限于2 3 5,而是由题目给定一个素数数组。与朴素丑数算法相比,只是将素因子变了而已,解法还是和朴素丑数一致的。
98 1
|
5月前
|
存储 SQL 算法
LeetCode 题目 65:有效数字(Valid Number)【python】
LeetCode 题目 65:有效数字(Valid Number)【python】
|
6月前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
42 0
|
6月前
|
Java Go C++
Golang每日一练(leetDay0092) 丑数 I\II Ugly Number i\ii
Golang每日一练(leetDay0092) 丑数 I\II Ugly Number i\ii
73 0
Golang每日一练(leetDay0092) 丑数 I\II Ugly Number i\ii
|
存储
Leetcode Single Number II (面试题推荐)
给你一个整数数组,每个元素出现了三次,但只有一个元素出现了一次,让你找出这个数,要求线性的时间复杂度,不使用额外空间。
38 0
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode 136. 只出现一次的数字 Single Number
LeetCode 136. 只出现一次的数字 Single Number
|
算法
LeetCode 414. Third Maximum Number
给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
93 0
LeetCode 414. Third Maximum Number
|
存储
LeetCode 313. Super Ugly Number
编写一段程序来查找第 n 个超级丑数。 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。
95 0
LeetCode 313. Super Ugly Number