.net网站开发课程设计,企业网站在百度搜索不到,二手网站专业做附近人的有吗,html网页代码成品**
描述
把只包含质因子2、3和5的数称作丑数#xff08;Ugly Number#xff09;。例如6、8都是丑数#xff0c;但14不是#xff0c;因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。
数据范围#xff1a; 0≤n≤2000 要求#x…**
描述
把只包含质因子2、3和5的数称作丑数Ugly Number。例如6、8都是丑数但14不是因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。
数据范围 0≤n≤2000 要求空间复杂度 O(n) 时间复杂度 O(n) 示例1 输入7 返回值8
题目分析
我们先看到题目把只包含质因子2、3和5的数称作丑数Ugly Number。例如6、8都是丑数但14不是因为它包含质因子7。 习惯上我们把1当做是第一个丑数。 有了上面的定义我们就可以知道丑数的形式就是2x3y5z.所有的丑数都会是由2x3y5^z组成的. 因此我们只需要根据此公式从小到大列举出每一个丑数,那么我们就能找到第n个丑数. 由于,x,y,z都是幂次方,且如果要从小到大寻找丑数,那么x,y,z都会逐渐增加,若想找到后一个幂次方的丑数,那么我们肯定会需要找到前一个幂次方的丑数.这时候我们就会想到用动态规划来解决此问题,因为我们可以将第n个丑数一直分解到第一个丑数,根据动态规划的转移方程,我们就可以一步步找到第n个丑数.
题解
说到动态规划我们肯定会想到动态规划的三个步骤 1.确定状态 2.定义状态转移方程 3.求得最优解
1.确定状态
首先我们应该确定动态规划的起始状态根据题干我们能发现第一个丑数就是我们即dp[0]1,且此时x,y,z的值肯定都是0,即x0,y0,z0.
2.定义状态转移方程
状态转移方程是这个题目的难点我们需要知道如何通过状态转移方程来实现下一个丑数的定位我们通过分析函数dp[i]2x3y5z(其中i是第i个丑数的下标存储位置)可知我们只要分别增大幂x,y,z(x,y,z都从0开始增大)然后进行比较我们就能找到我们想要的下一个丑数。 比如dp[0]1,那么dp[1]的值就是需要比较 213050 ,203150 ,203051 这三个值的大小得出dp[1]213050 2 因为213050 已经给dp[1],因此需要将第一个位置增大继续进行比较那么如何进行增大呢 这个地方也是本题最难理解的地方。我们先回到本题dp[i]2x3y5z 这个函数上我们可以想一下dp[i1]有什么规律dp[i1]无非就是dp[i-k]*2dp[i-k]*3,dp[i-k]*5 (ki)三个其中的一个值其中K可以是任意一个值不一定是1.我们也可以反过来想dp[i1]/2,dp[i1]/3,dp[i1]/5的其中一个值一定是dp[i]。所以我们这里只需要列出三路函数第一路是关于dp[x]*2的函数第二路是关于dp[y]*3,第三路是关于dp[z]*5的函数然后一直比较就可以逐一找到每个丑数。其中x,y,z都是每一路线性增长的下标。这里需要解释一下为什么要分三路因为d[i]的每次结果都需要乘2乘3和乘5以达到所有的质数都会被比较到的目的。且dp[i]乘2乘3乘5的值比较的时机是不同的。所以必须分为3个下标来分别统计幂x,y,z增长的值从而进行动态规划比较。
求dp[2]: 根据上面的规则第一个位置增大的值是dp[x1]*2(213050)*24 所以dp[2]的值需要比较 223050 ,203150 ,203051 这三个值的大小得出dp[2]203150 3 求dp[3]: 同理第二个位置被取出增大第二个位置即dp[y1]*3(213050)*36 所以dp[3]的值需要比较 223050 ,21315^0 ,203051 这三个值的大小得出dp[3]223050 4 求dp[4]: 后面为了便于观看将直接用数字来代替 接着第一个位置被取出所以x需要继续增加即dp[x2]*23*26 dp[4]的值需要比较 6 ,6 ,5 这三个值的大小得出dp[4]5 求dp[5]: 第三个数增大为dp[z1]*52*510 dp[5]的值需要比较 6 ,6 ,10 这三个值的大小得出dp[5]6,这时一二位置都为6所以都要增大 即第一个位置dp[x3]*24*28,第二个位置dp[y2]*39 所以dp[5]的值需要比较 8910这个三个数得出dp[5]8.
3.求得最优解
以此类推就能列举出所有的丑数了。
下面是一个更为直观的动画图来解释此过程 接下来就是算法部分
public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可* ** param index int整型* return int整型*/public int GetUglyNumber_Solution (int index) {if(index6){return index;}int[] dp new int[index];dp[0] 1;int x0,y0,z0;for(int i1;idp.length;i){dp[i] Math.min(dp[z]*5,Math.min(dp[x]*2,dp[y]*3));if(dp[i] dp[x]*2){x;}if(dp[i] dp[y]*3){y;}if(dp[i] dp[z]*5){z;}}return dp[index-1];}
}
