leetcode264-丑数II

原题

编写一个程序,找出第 n 个丑数。

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

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:

  1. 1 是丑数。
  2. n 不超过1690。

解法

思想

该题的关键是要知道丑数的顺序,从第一个丑数开始,得到它的2、3、5的倍数插入到最小堆中,这样每次我们从堆顶拿出来的都是堆中最小的元素,即下一个丑数,重复该步骤并计数就能得到目标解。

代码

class Solution {
    public int nthUglyNumber(int n) {
        Queue<Long> queue = new PriorityQueue<>();
        int count = 1;
        long cur = 1;
        while(count<n){
            queue.offer(cur*2);
            queue.offer(cur*3);
            queue.offer(cur*5);
            cur = queue.poll();
            while (!queue.isEmpty() && cur==queue.peek())
                queue.poll();
            count++;
        }
        return (int)cur;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode264-%e4%b8%91%e6%95%b0ii/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年2月10日
下一篇 2020年2月11日

相关推荐

  • 剑指offer05-替换空格

    原题(来源Leetcode) 请实现一个函数,把字符串 s 中的每个空格替换成"%20"。 示例1: 输入: s = "We are happy." 输出: "We%20are%2…

    算法 2020年4月5日
    0110
  • 程序员面试金典17.01-不用加号的加法

    原题(来源Leetcode) 设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。 示例: 输入: a = 1, b = 1 输出: 2 提示: a, b 均可能是负数或…

    算法 2020年6月9日
    0580
  • leetcode169-多数元素

    原题 给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。 示例1:…

    算法 2020年2月5日
    090
  • leetcode572-另一个树的子树

    原题 给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树…

    算法 2020年5月8日
    0380
  • leetcode8-字符串转换整数 (atoi)

    原题 请你来实现一个 atoi 函数,使其能将字符串转换成整数。 首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。接下来的转化规则如下: 如果第一个…

    算法 2020年4月3日
    0270
  • leetcode771-宝石与石头

    原题 给定字符串J 代表石头中宝石的类型,和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。 J 中的字母不重复,J …

    算法 2019年12月26日
    0360
  • leetcode199-二叉树的右视图

    原题 给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。 示例: 输入: [1,2,3,null,5,null,4] 输出:&nb…

    算法 2020年4月22日
    0110
  • leetcode349-两个数组的交集

    原题 给定两个数组,编写一个函数来计算它们的交集。 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2] 示例2: 输入: nums1 = [4…

    算法 2019年12月14日
    090
  • leetcode700-二叉搜索树中的搜索

    原题 给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。 例如, 给定二叉搜索树…

    算法 2020年1月16日
    0100
  • 剑指offer45-把数组排成最小的数

    原题(来源Leetcode) 输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。 示例 1: 输入: [10,2] 输出: "102" …

    算法 2020年6月11日
    0140

发表回复

登录后才能评论