欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

程序员面试金典 - 面试题 17.09. 第 k 个数(set优先队列/DP)

程序员文章站 2024-03-04 09:15:35
...

1. 题目

有些数的素因子只有 3,5,7,请设计一个算法找出第 k 个数。
注意,不是必须有这些素因子,而是必须不包含其他的素因子。
例如,前几个数按顺序应该是 1,3,5,7,9,15,21。

示例 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) {
    	set<long> 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;
    }
};

程序员面试金典 - 面试题 17.09. 第 k 个数(set优先队列/DP)

2.2 动态规划

自己画一下就明白了,比较潦草,见谅
程序员面试金典 - 面试题 17.09. 第 k 个数(set优先队列/DP)

class Solution {
public:
    int getKthMagicNumber(int k) {
        vector<long> dp(k+1,0);
        dp[1] = 1;
        int i3=1, i5=1, i7=1;
        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