JAVA丑数

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丑数

最新文章

热门文章