264. 丑数 II

 1 //动态方程dp[i]=min(dp[p_2]*2,dp[p_3]*3,dp[p_5]*5)
 2 class Solution
 3 {
 4 public:
 5     int nthUglyNumber(int n)
 6     {
 7         vector<int> dp(n);
 8         dp[0] = 1;
 9         int p2,p3,p5;
10         p2 = p3 = p5 = 0;
11         for (int i = 1;i < n;++ i)
12         {
13             dp[i] = min(2 * dp[p2],min(3 * dp[p3],5 * dp[p5]));
14             if(dp[i] == 2 * dp[p2]) ++p2;
15             if(dp[i] == 3 * dp[p3]) ++p3;
16             if(dp[i] == 5 * dp[p5]) ++p5;
17         }
18         return dp.at(n-1);
19     }
20 };

原文地址:https://www.cnblogs.com/yuhong1103/p/12700284.html

时间: 04-14

264. 丑数 II的相关文章

Leetcode 264.丑数II

丑数II 编写一个程序,找出第 n 个丑数. 丑数就是只包含质因数 2, 3, 5 的正整数. 示例: 输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数. 说明:  1 是丑数. n 不超过1690. 思路:动态规划思想.后面的丑数一定是由前面的丑数乘以2.3或5得到.所以第n个丑数一定是由前n-1个数中的某3个丑数(分别记为index2.index3.index5)分别乘以2.3或者5得到的数中的最小数,index2,

Leetcode之动态规划(DP)专题-264. 丑数 II(Ugly Number II)

编写一个程序,找出第 n 个丑数. 丑数就是只包含质因数 2, 3, 5 的正整数. 示例: 输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数. 说明: 1 是丑数. n 不超过1690. dp含义: dp[i]表示第i-1个丑数. class Solution { public int nthUglyNumber(int n) { int[] dp = new int[n + 1]; dp[0] = 1; int i2

264丑数II

题目: 来源: 法一:自己的超时代码 思路:从2开始由小到大遍历判断每一个数是否为丑数,由于到后面丑数越来越稀疏,导致非常费时间. class Solution: def nthUglyNumber(self, n: int) -> int: if n == 1: return 1 ans = [1] k = 2 while len(ans) < n: for j in [2,3,5]: # 如果除以2 3 5中的某个数可以除尽,则判断商是否在之前的数中 # 如果在说明是丑数,否则不是 if

LeetCode——264. 丑数 II

编写一个程序,找出第 n 个丑数. 丑数就是只包含质因数 2, 3, 5 的正整数. 示例: 输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数. 说明: 1 是丑数. n 不超过1690. 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/ugly-number-ii 1.暴力(brute force) class Solution { public: int nth

[Swift]LeetCode264.丑数 II | Ugly Number II

Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. Example: Input: n = 10 Output: 12 Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers. Note

leetcode 丑数 II java

题目: 编写一个程序,找出第 n 个丑数. 丑数就是只包含质因数 2, 3, 5 的正整数. 示例: 输入: n = 10输出: 12解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数.说明: 1 是丑数.n 不超过1690. 解题: 使用三指针 class Solution { public int nthUglyNumber(int n) { int min2 = 0; int min3 = 0; int min5 = 0; int []result =

[LeetCode]70. Ugly Number II第N个丑数

Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers. Note that 1 is typically treated as an

丑数 uva-136 丑数

代码如下: /*丑数是指不能被2.3.5以外的其他素数整除的数,把丑数从小到大排列起来,结果如下: 1,2,3,4,5,6,8,9,10,12,15... 求出第1500个丑数. */ #include<iostream> #include<vector> #include<queue> #include<set> using namespace std; typedef long long LL; int su[3]={2,3,5}; int main()

LeetCode(264):Ugly Number II

Ugly Number II:Write a program to find the n-th ugly number.Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.Note that 1 is typically