LeetCode|面试题 17.09.第 k 个数

LeetCode习题答案汇总

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

示例 1:

输入: k = 5

输出: 9

分析：

• 由题目可知，前面几个数字是1,3,5,7
• 后面的数字是由3,5,7这三个数相乘结合得来的
• 先构建一个长度为k的列表，初始值都为1
• 然后通过自身和3、5、7相乘，取最小值，并且对应的·指针加1
• 最后返回最后一个数即可

代码：

class Solution:
    def getKthMagicNumber(self, k: int) -> int:
        dp = [1] * k
        num3 = num5 = num7 = 0
        for i in range(1,k):
            dp[i] = min(dp[num3]*3,dp[num5]*5,dp[num7]*7)
            if dp[i] == dp[num3] * 3:
                num3 += 1
            if dp[i] == dp[num5] * 5:
                num5 += 1
            if dp[i] == dp[num7] * 7:
                num7 += 1
        return dp[-1]

结果：