leetcode題目鏈接

有些數的素因子只有 3，5，7，請設計一個算法找出第 k 個數。注意，不是必須有這些素因子，而是必須不包含其他的素因子。例如，前幾個數按順序應該是 1，3，5，7，9，15，21。

示例 1:

輸入: k = 5

輸出: 9

根據題意我們可以知道，一個滿足要求的數一定是之前的一個dp3* 3，dp5* 5，dp7* 7，并且這一結果一定是三個乘積的最小值,因此我們只需要記錄3，5，7各自dp的值，再相互與 3，5，7 相乘，取其中的最小值，就是當前的目標值。代碼如下

    public int getKthMagicNumber(int k) {

        int i3 = 0, i5 = 0, i7 = 0;

        int[] dp = new int[k];

        dp[0] = 1;

        for(int i = 1; i < k; i++){

            // 3 5 7 9 15 21 25

            // 1 1 1 2 3  4  4  i3

            // 0 1 1 1 2  2  3  i5

            // 0 0 1 1 1  2  2  i7

            dp[i] = Math.min(Math.min(dp[i3]*3, dp[i5]*5) , dp[i7]*7);

            if(dp[i] == dp[i3]*3)i3++;

            if(dp[i] == dp[i5]*5)i5++;

            if(dp[i] == dp[i7]*7)i7++;

        }

        return dp[k-1];

    }

總結

以上是生活随笔為你收集整理的JAVA丑数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。