文档章节

ugly number

B
 BlueWoods
发布于 2015/08/19 22:36
字数 1165
阅读 128
收藏 0

leetcode 263 & 264是关于ugly number的; 

https://leetcode.com/problems/ugly-number/

https://leetcode.com/problems/ugly-number-ii/


简单的263,给定一个数,判断该数是否ugly;这个比较直观,只需要判断该数是否只能被2, 3, 5整除即可;

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

    return false;
}

264要求找出第n个ugly number;如果直接使用前面的算法,依次递增数字,判断该数字是否ugly,直到第n个为止,可以得到正确的答案,但在n比较大的时候,肯定会出现TLE的问题;

这个问题有多种解法,从最笨拙的,到精巧的,再到更加精巧和更高效率的;

  1. 使用一个数组用来存放n个ugly number,假设处理到第i个数字,x,那么下一个数字必然满足: 假设有三个ugly number, a, b, c, 且 2 * a > x, 3 * b > x, 5 * c > x,那么下一个数字肯定为2 * a, 3 * b, 5 * c中得最小的值;我的想法是如何找到a,b, c;最简单的方式是从头到i得遍历,那么这样话,最后会得到一个O(n * n)的算法;注意到i之前的数字是升序排列的,所以可以用二分查找,那么最后会得到一个O(n * log n)的算法;


  2. public int nthUglyNumber(int n) {
        if (n <= 5) {
            return n;
        }
        int[] zs = {2, 3, 5};
        int[] nums = new int[n + 1];
        int i = 1;
        for (; i <= 5; i++) {
            nums[i] = i;
        }
        int x = 5;
    
        while (i <= n) {
            int nextMin = Integer.MAX_VALUE;
            for (int z : zs) {
                int y = x / z;
                int j = nextPosGe(nums, y, 1, i);
                while (nums[j] * z <= x) {
                    j = j + 1;
                }
                nextMin = Math.min(nextMin, nums[j] * z);
            }
            x = nextMin;
            nums[i] = x;
            i += 1;
        }
    
        return nums[n];
    }
    
    private int nextPosGe(int[] nums, int y, int start, int end) {
        int i = start, j = end - 1;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (nums[mid] < y) {
                i = mid + 1;
            } else {
                j = mid - 1;
            }
        }
        return i;
    }
  3. 这个算法是leetcode上面,别人分享的 https://leetcode.com/discuss/52746/java-solution-using-priorityqueue-o-n  ,使用PriorityQueue的O(n)的算法;想象一下,如果把所有的(前n个)ugly number都放到了PQ里面,那么每次poll,都可以得到目前为止最大的(也是PQ中目前最小的)的数字;假设为x,同时 2 * x, 3 * x, 5 * x,肯定也在PQ中;所以这个算法,从PQ不断的poll,同时把当前number的2, 3, 5倍也放进去,那么poll了n次以后,得到的就是第n个ugly number;这个算法直观且易于理解,代码简单优美;因为PQ offer的时间复杂度是O(log n),所以它的时间复杂度也是 O(n * log n);另外因为PQ本身比数组要复杂,所以比前面的算法要慢一些(600ms vs 400ms);

  4. public int nthUglyNumber(int n) {
        PriorityQueue<Long> q = new PriorityQueue<Long>();
        q.offer(1l);
        long cur = 0;
        while(n-->0){
            while(q.peek()==cur){
                q.poll();
            }
            cur = q.poll();
            q.offer(cur*2);
            q.offer(cur*3);
            q.offer(cur*5);
        }
        return (int)cur;
    }
  5. 第三种是最精巧也最高效的算法;https://leetcode.com/discuss/52716/o-n-java-solution

  6. public int nthUglyNumber2(int n) {
        int[] ugly = new int[n];
        ugly[0] = 1;
        int index2 = 0, index3 = 0, index5 = 0;
        int factor2 = 2, factor3 = 3, factor5 = 5;
        for (int i = 1; i < n; i++) {
            int min = Math.min(Math.min(factor2, factor3), factor5);
            ugly[i] = min;
            if (factor2 == min)
                factor2 = 2 * ugly[++index2];
            if (factor3 == min)
                factor3 = 3 * ugly[++index3];
            if (factor5 == min)
                factor5 = 5 * ugly[++index5];
        }
        return ugly[n - 1];
    }

这个算法是O(n)的,当然也是最快的,用了340ms(没有比第一个快多少,呵呵);简单的分析以下:对于任何一个ugly number x,可以表示为 x = 2 ** a  * 3 ** b * 5 ** c; (** 表示power);其中a, b, c 从0开始递增;我想到了这一点,但我始终没有想清楚要怎么样递增a,b, c以得到这个序列;直到我看到了这个算法;

一点心得:

  1. leetcode对于这种代码分享要open的多;而且对于测试用例也open的多,当在某个测试上面失败的时候,它会告诉你输入是什么,结果应该是什么;并不担心那些作弊的程序;其实也没有什么可担心的吧;所以,对于调试程序,不断改进很有帮助;很多程序,我就是这样做出来的;同时,还可以看到别人分享的代码,有一些程序真的不会做,像那些要做位与运算的,就可以参考别人的代码,学习,也能取得一些进步吧;

  2. 看别人的代码,特别是比自己想法更好的代码,真的可以学到不少;也是写程序的一种乐趣;

© 著作权归作者所有

B
粉丝 4
博文 39
码字总数 21286
作品 0
杭州
私信 提问
LeetCode:Super Ugly Number - 超级丑数

1、题目名称 Super Ugly Number(超级丑数) 2、题目地址 https://leetcode.com/problems/super-ugly-number/ 3、题目内容 英文: Write a program to find the nth super ugly number. Sup......

北风其凉
2015/12/19
3.2K
2
Ugly Number(leetcode263)

Write a program to check whether a given number is an ugly number. Ugly numbers are positive numbers whose prime factors only include . Example 1: Input: 6Output: trueExplanatio......

woshixin
2018/12/12
5
0
LeetCode:Ugly Number - 丑数1:判断指定数字是否为丑数

1、题目名称 Ugly Number(丑数1:判断指定数字是否为丑数) 2、题目地址 https://leetcode.com/problems/ugly-number 3、题目内容 英文:Write a program to check whether a given number...

北风其凉
2015/08/23
4.1K
1
LeetCode:Ugly Number II - 丑数2:找出第n个丑数

1、题目名称 Ugly Number II(丑数2:找出第n个丑数) 2、题目地址 https://leetcode.com/problems/ugly-number-ii/ 3、题目内容 英文:Write a program to find the -th ugly number. 中文:...

北风其凉
2015/08/23
6.5K
3
决战Leetcode: easy part(51-96)

本博客是个人原创的针对leetcode上的problem的解法,所有solution都基本通过了leetcode的官方Judging,个别未通过的例外情况会在相应部分作特别说明。 欢迎互相交流! email: tomqianmaple@...

qq_32690999
2018/02/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Taro 兼容 h5 踩坑指南

最近一周在做 Taro 适配 h5 端,过程中改改补补,好不酸爽。 本文记录📝遇到的问题,希望为有相同需求的哥们👬节约点时间。 Taro 版本:1.3.9。 解决跨域问题 h5 发请求会报跨域问题,需...

dkvirus
53分钟前
3
0
Spring boot 静态资源访问

0. 两个配置 spring.mvc.static-path-patternspring.resources.static-locations 1. application中需要先行的两个配置项 1.1 spring.mvc.static-path-pattern 这个配置项是告诉springboo......

moon888
今天
3
0
hash slot(虚拟桶)

在分布式集群中,如何保证相同请求落到相同的机器上,并且后面的集群机器可以尽可能的均分请求,并且当扩容或down机的情况下能对原有集群影响最小。 round robin算法:是把数据mod后直接映射...

李朝强
今天
4
0
Kafka 原理和实战

本文首发于 vivo互联网技术 微信公众号 https://mp.weixin.qq.com/s/bV8AhqAjQp4a_iXRfobkCQ 作者简介:郑志彬,毕业于华南理工大学计算机科学与技术(双语班)。先后从事过电子商务、开放平...

vivo互联网技术
今天
19
0
java数据类型

基本类型: 整型:Byte,short,int,long 浮点型:float,double 字符型:char 布尔型:boolean 引用类型: 类类型: 接口类型: 数组类型: Byte 1字节 八位 -128 -------- 127 short 2字节...

audience_1
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部