LeetCode 313 超级丑数
2021/8/9 23:07:11
本文主要是介绍LeetCode 313 超级丑数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
超级丑数 是一个正整数,并满足其所有质因数都出现在质数数组 primes
中。
给你一个整数 n
和一个整数数组 primes
,返回第 n
个 超级丑数 。
题目数据保证第 n
个 超级丑数 在 32-bit 带符号整数范围内。
示例 1:
输入:n = 12, primes = [2,7,13,19] 输出:32 解释:给定长度为 4 的质数数组 primes = [2,7,13,19],前 12 个超级丑数序列为:[1,2,4,7,8,13,14,16,19,26,28,32] 。
示例 2:
输入:n = 1, primes = [2,3,5] 输出:1 解释:1 不含质因,因此它的所有质因数都在质数数组 primes = [2,3,5] 中。
提示:
1 <= n <= 106
1 <= primes.length <= 100
2 <= primes[i] <= 1000
- 题目数据 保证
primes[i]
是一个质数 primes
中的所有值都 互不相同 ,且按 递增顺序 排列
动态规划
/** * DP * * @param n * @param primes * @return */ public static int nthSuperUglyNumber(int n, int[] primes) { if (n <= 0) return -1; // 用来记录生成的丑数,dp[i]表示第i个超级丑数 int[] dp = new int[n]; // 初始条件:第1个超级丑数是1 dp[0] = 1; // 表示下一个超级丑数是当前指针指向的超级丑数乘以对应的因数,初始是为1 int pointers[] = new int[primes.length]; for (int i = 1; i < n; i++) { int minNum = Integer.MAX_VALUE; for (int j = 0; j < primes.length; j++) { // 取最小值 minNum = Math.min(minNum, primes[j] * dp[pointers[j]]); } // 下一个超级丑数 dp[i] = minNum; for (int j = 0; j < primes.length; j++) { // 某位置数字对应的指针加1 if (dp[i] == primes[j] * dp[pointers[j]]) pointers[j]++; } } return dp[n - 1]; }
测试用例
public static void main(String[] args) { int n = 12; int[] primes = new int[]{2, 7, 13, 19}; int uglyNumber = NthSuperUglyNumber.nthSuperUglyNumber(n, primes); System.out.println("NthSuperUglyNumber demo01 result : " + uglyNumber); n = 1; primes = new int[]{2, 3, 5}; uglyNumber = NthSuperUglyNumber.nthSuperUglyNumber(n, primes); System.out.println("NthSuperUglyNumber demo02 result : " + uglyNumber); }
运行结果
NthSuperUglyNumber demo01 result : 32 NthSuperUglyNumber demo02 result : 1
这篇关于LeetCode 313 超级丑数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享
- 2024-07-03微信支付提示订单号重复-icode9专业技术文章分享
- 2024-07-02微服务启动nacos注册上去了,但是一直没有收到请求-icode9专业技术文章分享
- 2024-07-02如何检查文件的编码格式-icode9专业技术文章分享
- 2024-07-02sublime 更改编码格式-icode9专业技术文章分享
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享