【力扣 leetcode】面试题 17.09：第k个数

矫情吗；* 2023-10-09 14:48 26阅读 0赞

## 每日进步 ##

*  **求最小值：** `Math.min()`
 *  **动态规划：**
    
     *  确定要存储的信息
     *  确定初值
     *  确定递推公式

## 题目 ##

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

*  **示例：**
    
     *  输入: k = 5
     *  输出: 9

> 来源：力扣（LeetCode）  
> 链接：https://leetcode.cn/problems/get-kth-magic-number-lcci  
> 著作权归领扣网络所有。本文仅供个人学习，非商用。

## 题解 ##

**动态规划：**

*  本题中所求数据的素因子只能是3，5，7或者其中的一两个，我们暂且称这样的数据为“好数”  g o o d n u m \\mathop\{goodnum\} goodnum。这就意味着所有“好数”可以通过几个3、5或者7相乘得到，即： g o o d n u m = 3 i 5 j 7 k \\mathop\{goodnum\}=3^i5^j7^k goodnum=3i5j7k。
 *  并且每一个“好数”都可以通过一个比它小的“好数”乘以3或者5或者7得到。
 *  由此我们可以编写代码：
    
     *  **存储信息：**`dp[i]`存储第`i`个“好数”。
     *  **确定初值：**`dp[1]=1`。我们从下标1开始存储“好数”，题目中最小的“好数”为1。
     *  **递推公式：**`dp[i] = Math.min(Math.min(dp[pos3]*3, dp[pos5]*5), dp[pos7]*7)`
        
         *  我们创建3个指针`pos3, pos5, pos7`，它们指向3个相同或不同的“好数”，这些被指向的“好数”分别可以通过乘以3、5或者7来构造一个比当前最大的“好数”更大的“好数”。
         *  最开始，这三个指针的大小均为1。最初我们使用`dp[1]`分别乘以3、5或者7来构造一个更大的“好数”。
         *  如果我们已经得到了`dp[i]`的值，要如何获得`dp[i+1]`的值呢？  
            我们需要求3个数值：`dp[pos3]*3, dp[pos5]*5, dp[pos7]*7`。即：通过对已经得到的**指针指向的**“好数”乘以3、5或者7来构造3个更大一些的好数，这三个新构造出的“好数”的最小值就是`dp[i+1]`。
         *  每次构造了一个新的“好数”后，我们需要把这次用到的指针加1。这样每次用到这个指针时，都可以构造一个比上一次更大的“好数”。

class Solution {
        
        public int getKthMagicNumber(int k) {
        
            int[] dp = new int[k+1];
            dp[1] = 1;
            int pos3 = 1, pos5 = 1, pos7 = 1;
    
            for (int i = 2; i <= k; i++){
        
                dp[i] = Math.min(Math.min(dp[pos3]*3, dp[pos5]*5), dp[pos7]*7);
                if (dp[i] == dp[pos3]*3)
                    pos3++;
                if (dp[i] == dp[pos5]*5)
                    pos5++;
                if (dp[i] == dp[pos7]*7)
                    pos7++;
            }
    
            return dp[k];
        }
    }