微网站自助建站平台哪个好,做企业信用贷的网站,广西网站建设建议,网站优化关键词排名1. 题目
有些数的素因子只有 3#xff0c;5#xff0c;7#xff0c;请设计一个算法找出第 k 个数。 注意#xff0c;不是必须有这些素因子#xff0c;而是必须不包含其他的素因子。 例如#xff0c;前几个数按顺序应该是 1#xff0c;3#xff0c;5#xff0c;7…1. 题目
有些数的素因子只有 357请设计一个算法找出第 k 个数。 注意不是必须有这些素因子而是必须不包含其他的素因子。 例如前几个数按顺序应该是 135791521。
示例 1:
输入: k 5
输出: 9来源力扣LeetCode 链接https://leetcode-cn.com/problems/get-kth-magic-number-lcci 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
2.1 set “队列”
满足题目要求的数只能乘以3、5、7用set有序可以去重、当做优先队列不断的出队begin(), 且把 begin() 的 3,5,7倍数插入队列
class Solution {
public:int getKthMagicNumber(int k) {setlong q;//可以看做小顶堆long ans;q.insert(1);while(k--){ans *q.begin();q.erase(q.begin());q.insert(ans*3);q.insert(ans*5);q.insert(ans*7);}return ans;}
};2.2 动态规划
参考 LeetCode 263. 丑数 264. 丑数 IIDP LeetCode 313. 超级丑数动态规划 LeetCode 1201. 丑数 III最小公倍数二分查找
自己画一下就明白了比较潦草见谅
class Solution {
public:int getKthMagicNumber(int k) {vectorlong dp(k1,0);dp[1] 1;int i31, i51, i71;for(int i 2; i k; i){dp[i] min(dp[i3]*3, min(dp[i5]*5, dp[i7]*7));if(dp[i3]*3 dp[i])i3;if(dp[i5]*5 dp[i])i5;if(dp[i7]*7 dp[i])i7;}return dp[k];}
};0 ms 6.1 MB
