文档章节

263. Ugly Number

JiaMing
 JiaMing
发布于 07/15 00:09
字数 1214
阅读 86
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

题目: 263. Ugly Number

题目地址:https://leetcode.com/problems/ugly-number/

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. 1 is typically treated as an ugly number.
  2. Input is within the 32-bit signed integer range: [−231,  231 − 1].

解题思路

解决ugly number的原题:

已经被leetcode更新过,原题和上面的描述类似,但原题应该稍微更容易想一些。因此在解上面道题之前,让我们先来看看原题的解法,原题是这样的:它跟上面这道题只有唯一一个不同的地方,那就是输入k,然后要我们求出第k个(或者可以理解为第k小的)ugly number

我们先看看第一个ugly number是什么呢?题目已经说了,是1。注意到接下来的ugly number可以通过用2, 3, 5乘以前面的ugly number得到。现在ugly number的序列里面已经有一个1了,设这个ugly number的序列为uglyNums,则现在有uglyNums=[1],所以那第二个ugly number就看三个质因素(prime factors)2, 3, 5乘以1得到的值哪个最小,发现2*1=2最小,所以第二个ugly number也就是2了,现在uglyNums=[1, 2],如下图所示。由于2*1=2已经被记录到uglyNums里面了,所以接下来与2这个质因数相乘得到的ugly number应该是2*2=4,也就是要让2乘以列表中已记录的下一个ugly number才有意义了。如此类推,下一个uglyNums应该是3了,因为在{3*1=3, 5*1=5, 2*2=4}里面,3*1=3最小,uglyNums更新为[1, 2, 3],同样地,质因素3要指向它对应的下一个ugly number,即uglyNums[1]=2。

重复这个过程,可以得到uglyNums=[1, 2, 3, 4, 5],如下面第一幅图所示。注意到会出现一种情况:两个质因素乘以不同ugly number得出相同的值。例如我们看下第二幅图,3*2=6,同时又有2*3=6,这时候因为它们都比5*2=10小,所以它们同时最小,uglyNums的下一个ugly number(即uglyNums[5])设为6,同时要让3和2都与它们对应的下一个ugly number相乘,质因素将3和2分别与uglyNums[2]和uglyNums[3]相乘,如最后一幅图所示。

至此,ugly number的原题就被解决掉了。写程序的时候要注意第一个ugly number是1,要作为特殊条件判断一下。接下来解决现在的题目:263. Ugly Number https://leetcode.com/problems/ugly-number/

解决现在的题目263. Ugly Number:

现在的题目是:给定一个数,判断它是不是ugly number。设这个给定的数是n,首先考虑到小于x的数不可能多于n个(更准确地说,小于n的ugly number个数不超过n个),因此,只要生成k(令k=n)个ugly number,再判断一下这n个ugly number里面有没有包含n即可,如果包含则说明n是ugly number,否则就不是ugly number。

时间复杂度

按照上面的解法,本题的时间复杂度实际上等于生成n个ugly number的时间复杂度,设质因数的个数m,则生成n个ugly number的时间复杂度是O(mn)

最终实现

Java实现

import java.util.ArrayList;
import java.util.List;

public class Solution {

    private List<Long> uglyNums = new ArrayList<>();

    /**
     *
     * The solution for the old problem 263
     * @param k the input of the problem
     * @return the kth ugly number
     */
    public long calcUglyNumber(int k) {
        uglyNums.clear();
        uglyNums.add(1L);
        FactorRecord factorTwo = new FactorRecord(2, 0);
        FactorRecord factorThree = new FactorRecord(3, 0);
        FactorRecord factorFive = new FactorRecord(5, 0);
        for (int i = 0; i < k; i++) {
            long minVal = Math.min(factorFive.calcCurrentVal(uglyNums),
                    Math.min(factorTwo.calcCurrentVal(uglyNums), factorThree.calcCurrentVal(uglyNums)));
            if (minVal == factorTwo.calcCurrentVal(uglyNums)) {
                if (uglyNums.get(uglyNums.size() - 1) != minVal) {
                    uglyNums.add(minVal);
                }
                factorTwo.setIndex(factorTwo.getIndex() + 1);
            }
            if (minVal == factorThree.calcCurrentVal(uglyNums)) {
                if (uglyNums.get(uglyNums.size() - 1) != minVal) {
                    uglyNums.add(minVal);
                }
                factorThree.setIndex(factorThree.getIndex() + 1);
            }
            if (minVal == factorFive.calcCurrentVal(uglyNums)) {
                if (uglyNums.get(uglyNums.size() - 1) != minVal) {
                    uglyNums.add(minVal);
                }
                factorFive.setIndex(factorFive.getIndex() + 1);
            }
        }
        return uglyNums.get(k);
    }

    public boolean isUgly(int num) {
        if (num == 1) {
            return true;
        }
        uglyNums.clear();
        uglyNums.add(1L);
        FactorRecord factorTwo = new FactorRecord(2, 0);
        FactorRecord factorThree = new FactorRecord(3, 0);
        FactorRecord factorFive = new FactorRecord(5, 0);
        int k = num;
        for (int i = 0; i < k; i++) {
            long minVal = Math.min(factorFive.calcCurrentVal(uglyNums),
                    Math.min(factorTwo.calcCurrentVal(uglyNums), factorThree.calcCurrentVal(uglyNums)));
            if (minVal == num) {
                return true;
            }
            if (minVal > num) {
                return false;
            }
            if (minVal == factorTwo.calcCurrentVal(uglyNums)) {
                if (uglyNums.get(uglyNums.size() - 1) != minVal) {
                    uglyNums.add(minVal);
                }
                factorTwo.setIndex(factorTwo.getIndex() + 1);
            }
            if (minVal == factorThree.calcCurrentVal(uglyNums)) {
                if (uglyNums.get(uglyNums.size() - 1) != minVal) {
                    uglyNums.add(minVal);
                }
                factorThree.setIndex(factorThree.getIndex() + 1);
            }
            if (minVal == factorFive.calcCurrentVal(uglyNums)) {
                if (uglyNums.get(uglyNums.size() - 1) != minVal) {
                    uglyNums.add(minVal);
                }
                factorFive.setIndex(factorFive.getIndex() + 1);
            }
        }
        return false;
    }

    class FactorRecord {
        long factor; // 2, 3, 5
        int index;

        public FactorRecord(long factor, int index) {
            this.factor = factor;
            this.index = index;
        }

        public void setFactor(long factor) {
            this.factor = factor;
        }

        public void setIndex(int index) {
            this.index = index;
        }

        public long getFactor() {
            return factor;
        }

        public int getIndex() {
            return index;
        }

        public long calcCurrentVal(List<Long> uglyNums) {
            return factor * uglyNums.get(index);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        boolean res = solution.isUgly(2144843814);
        System.out.println(res);
    }

}

 

下一篇: 63. Unique Paths II
JiaMing
粉丝 8
博文 57
码字总数 37622
作品 0
广州
私信 提问
加载中
请先登录后再评论。
CDH5: 使用parcels配置lzo

一、Parcel 部署步骤 1 下载: 首先需要下载 Parcel。下载完成后,Parcel 将驻留在 Cloudera Manager 主机的本地目录中。 2 分配: Parcel 下载后,将分配到群集中的所有主机上并解压缩。 3 激...

cloud-coder
2014/07/01
6.8K
1
jquery通过a标签删除table中的一行的代码

删除table中的一行的方法有很多,在本文为大家介绍下jquery是如何做到的,下面有个不错的示例,喜欢的朋友可以参考下 代码如下:

linghangp
2013/12/03
426
0
python 是什么?

  Python(英国发音:/?pa?θ?n/ 美国发音:/?pa?θɑ?n)是什么呢?简单的说,它是一种计算机编程语言及一组配套的软件工具和库。是一种面向对象、解释型计算机程序设计语言,由Guido van...

红牛王
2017/05/24
101
0
如何使用 50 行 Python代码制作一个计算器

在这篇文章中,我将向大家演示怎样向一个通用计算器一样解析并计算一个四则运算表达式。当我们结束的时候,我们将得到一个可以处理诸如 1+2*-(-3+2)/5.6+3样式的表达式的计算器了。当然,你也...

铁扇公主1
2017/06/19
115
0
GreenDAO3的使用教程

简介 GreenDAO是一个轻量、快速的ORM解决方案,它能高效地将对象映射到SQLite数据库,目前升级到了3.1版本,相较于之前的版本来说,易用性大幅度增加了,不需要一些麻烦的配置,详情参考官方文...

gongcheng
2016/08/20
363
0

没有更多内容

加载失败,请刷新页面

加载更多

PHP实现RabbitMQ消息队列

先安装PHP对应的RabbitMQ,这里用的是 php_amqp 不同的扩展实现方式会有细微的差异. php扩展地址: http://pecl.php.net/package/amqp 具体以官网为准 http://www.rabbitmq.com/getstarted.htm...

PHP圈子
30分钟前
22
0
pdd笔试题

拼多多提前批的笔试没有报名,但昨天听伙伴们说很难,所以一共4道题,挑了2道会的,自己编了一下。 #include<iostream>#include<vector>#include<algorithm>using namespace std;int ma...

osc_tylqml9v
30分钟前
0
0
拓扑排序算法

/** * 拓扑排序算法,拓扑都是有向无环图 * 使用场景:编译的时候,比如,springboot启动的时候要读取docker系统环境变量,还要读取各配置文件按照顺序 * 还有比如,a的包依赖...

osc_94gn551r
32分钟前
0
0
巨微代理MS1581蓝牙无线收发器

上海巨微MS1581包含8位单片机和低功耗、低成本的BLE收发器,内部集成了发射机、接收机、GFSK调制解调器和BLE基带处理。遵循BLE广播通道通信,具有成本低、体积小、控制方便等优点。巨微代理英...

英尚微电子
32分钟前
12
0
链接测试(内部)

1、长链 https://chelun.eclicks.cn/web/information?info_tid=156984 - 文章test http://cjjl-h5-test.chelun.com/2020/big/index.html - 以小博大test 2、scheme : 钱包 supercoach://myw......

osc_hwc3munb
33分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部