JZ33 丑数
2021/8/28 23:06:36
本文主要是介绍JZ33 丑数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
原题链接
描述
把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
示例
输入:7 返回值8
思路
丑数只包含因子 2, 3, 5。所以丑数=某较小丑数 × 某因子,可以推出该因子也是小于等于该丑数的一个丑数,即:丑数就是由 1经过若干次和2、3、5的乘积得到的数。题目要求第 n 个 丑数,所以重要的是按序求出n个丑数。显然让1直接乘以2、3、5得到的数再依次乘以2、3、5得到的数不是有序的。所以设了三个指针,每个指针指向前几个已经乘过2、3、5的数(乘了几次)。
例:刚开始丑数只有1,如果直接让他们依次乘以2、3、5那么得到的抽数序列必然是1、2、3、5、4、6……这样,明显5>4这是不符合期望的。所以a、b、c刚开始都指向 1,然后让 a * 2,得到丑数是 2,小于3或5,然后a++,a 再乘以2,得到4,b再乘以 3 得到 3,c 乘以 5 得到 5,选取丑数是3,然后b++。
解答
public class Solution { public int GetUglyNumber_Solution(int index) { if(index==0)return 0; int[] dp = new int[index]; dp[0] = 1; int a = 0, b = 0, c = 0; for (int i = 1; i < dp.length; i++) { int tmp1 = dp[a] * 2, tmp2 = dp[b] * 3, tmp3 = dp[c] * 5; dp[i] = Math.min(tmp1, Math.min(tmp2, tmp3)); if (dp[i] == tmp1) { a++; // 第a个数已经通过乘2得到了一个新的丑数,那下个需要通过乘2得到一个新的丑数的数应该是第(a+1)个数 } if (dp[i] == tmp2) { b++; // 第 b个数已经通过乘3得到了一个新的丑数,那下个需要通过乘3得到一个新的丑数的数应该是第(b+1)个数 } if (dp[i] == tmp3) { c++; // 第 c个数已经通过乘5得到了一个新的丑数,那下个需要通过乘5得到一个新的丑数的数应该是第(c+1)个数 } } return dp[index - 1]; } }
这篇关于JZ33 丑数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)