LeetCode 263. 丑数 && 264. 丑数 II(DP)

关注
LeetCode 263. 丑数 && 264. 丑数 II(DP)www.shan-machinery.com

文章目录 1. LeetCode 263. 丑数解题 2. LeetCode 264. 丑数 IIDP解题

1. LeetCode 263. 丑数

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

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

示例 1:输入: 6输出: true解释: 6 = 2 × 3示例 2:输入: 8输出: true解释: 8 = 2 × 2 × 2示例 3:输入: 14输出: false 解释: 14 不是丑数,因为它包含了另外一个质因数 7。说明:1 是丑数。输入不会超过 32 位有符号整数的范围: [−2^31,2^31 − 1]。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/ugly-number 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题 类似题目: LeetCode 1201. 丑数 III(最小公倍数+二分查找) 程序员面试金典 - 面试题 17.09. 第 k 个数(set优先队列/DP) LeetCode 313. 超级丑数(动态规划) LeetCode 878. 第 N 个神奇数字(二分查找) class Solution {public:bool isUgly(int num) {if(num public:int nthUglyNumber(int n) {int dp[n+1] = {0};dp[1] = 1;int i2=1, i3=1, i5=1;for(int i = 2; i public:int nthUglyNumber(int n) {set s;s.insert(1);int count = 0;long tp;while(count != n){count++;tp = *s.begin();s.erase(s.begin());s.insert(tp*2);s.insert(tp*3);s.insert(tp*5);}return tp;}};

在这里插入图片描述

https://www.shan-machinery.com