数字与数学5:丑数
程序员文章站
2022-03-09 13:40:37
...
LeetCode263和264是两道关于丑数的问题,一听名字挺邪乎。看一下要求:
给你一个整数 n ,请你判断 n 是否为 丑数 。如果是,返回 true ;否则,返回 false 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
示例1:
输入:n = 6
输出:true
解释:6 = 2 × 3
示例2:
输入:n = 14
输出:false
解释:14 不是丑数,因为它包含了另外一个质因数 7 。
LeetCode263是让你判断一个数是不是丑数,264是让你判断前n个丑数。
如果 n 不是正整数(即小于等于 0):必然不是丑数,直接返回 false。如果 n是正整数:我们对 n执行 2 3 5 的整除操作即可,直到 nn 被除干净,如果 nn 最终为 1 说明是丑数,否则不是丑数。
这里有一点需要想明白,2 3 5 先除哪一个都是可以的,因为乘法本身具有交换律。所以代码就是:
class Solution {
public boolean isUgly(int n) {
if (n <= 0) return false;
while (n % 2 == 0) n /= 2;
while (n % 3 == 0) n /= 3;
while (n % 5 == 0) n /= 5;
return n == 1;
}
}
第二个题,我们可以通过一个个计算 ,然后遍历来寻找,但是这样的问题也很明显 ,那就是计算次数太多了,效率不高。
一般涉及到固定n的时候,都要考虑一下能否使用堆来实现,而且遵循”找第K小用大,找第大用小“的原则,这里是要找第K大,所以我们就尝试用最小堆试一下。
初始时堆为空。首先将最小的丑数 11 加入堆。
每次取出堆顶元素 xx,则 xx 是堆中最小的丑数,由于 2x, 3x, 5x2x,3x,5x 也是丑数,因此将 2x, 3x, 5x2x,3x,5x 加入堆。
上述做法会导致堆中出现重复元素的情况。为了避免重复元素,可以使用哈希集合去重,避免相同元素多次加入堆。
在排除重复元素的情况下,第 n 次从最小堆中取出的元素即为第 n个丑数。
class Solution {
public int nthUglyNumber(int n) {
int[] factors = {2, 3, 5};
Set<Long> seen = new HashSet<Long>();
PriorityQueue<Long> heap = new PriorityQueue<Long>();
seen.add(1L);
heap.offer(1L);
int ugly = 0;
for (int i = 0; i < n; i++) {
long curr = heap.poll();
ugly = (int) curr;
for (int factor : factors) {
long next = curr * factor;
if (seen.add(next)) {
heap.offer(next);
}
}
}
return ugly;
}
}
这个题还可以使用dp来做,后面再说。
下一篇: Qt中快速定义函数的小技巧
推荐阅读
-
js实现将一位整数型数字转化为二进制数(十进制与二进制互转)
-
for循环练习 打印4面三角形,99乘法表 ,打印1-100内整数 数字包含9跳过 每行输出5个 用空格分隔,按照从大到小的顺序输出4位数中的个位+百位=十位+千位的数字及个数
-
求s=a+aa+aaa+aaaa+aa...a的值,其中a是一个数字。例如2+22+222+2222+22222(此时共有5个数相加),几个数相加由键盘控制
-
实验2-4-1 统计各位数字之和是5的数 (20分)
-
C语言实现5位数=2*4位数,9个数字互不相同
-
AI开发者大会之计算机视觉技术实践与应用:2020年7月3日《RPA+AI助力政企实现智能时代的人机协同》、《5G风口到来,边缘计算引领数据中心变革》、《数字化时代金融市场与AI算法如何结合?》
-
JavaScript连载5-数据转换为Number与String、数字解析
-
5组数字,每组取一个组成不相同的5位数,大神
-
PHP求0到5数字组成的三位数总和
-
5组数字,每组取一个组成不相同的5位数,大神