1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 49 题] “丑数”做题记录

[剑指 Offer 第 2 版第 49 题] “丑数”做题记录

第 49 题:丑数

传送门:丑数牛客网 online judge 地址

把只包含因子 235 的数称作丑数(Ugly Number)。

例如 68 都是丑数,但 14 不是,因为它包含因子 7

求按从小到大的顺序的第 N 个丑数。

样例:

输入:5

输出:5

注意:习惯上我们把 1 当做是第一个丑数。

同 LeetCode 第 264 题,题解传送门:LeetCode 上的丑数问题

思路:所谓的一个数 m 是另一个数 n 的因子,是指 n 能被 m 整除,也就是 n\\%m==0 成立。根据丑数的定义,丑数只能被 235 整除。根据丑数的定义,丑数应该是另一个丑数乘以 23 或者 5 的结果(1除外)。因此我们可以创建一个数组,里面的数字是排好序的丑数,每一个丑数都是前面的丑数乘以 23 或者 5 得到的。

这个思路的关键问题在于怎样保证数组里面的丑数是排好序的。对乘以 2 而言,肯定存在某一个丑数 T2,排在它之前的每一个丑数乘以 2 得到的结果都会小于已有最大的丑数,在它之后的每一个丑数乘以乘以 2 得到的结果都会太大。我们只需要记下这个丑数的位置,同时每次生成新的丑数的时候,去更新这个 T2。对乘以 35 而言,也存在着同样的 T3T5

Python 代码:

  class Solution:
        def GetUglyNumber_Solution(self, index):
            # write code here
            if index < 7:
                return index
            res = [1, 2, 3, 4, 5, 6]
            t2, t3, t5 = 3, 2, 1
            for i in range(6, index):
                res.append(min(res[t2] * 2, min(res[t3] * 3, res[t5] * 5)))
                while res[t2] * 2 <= res[i]:
                    t2 += 1
                while res[t3] * 3 <= res[i]:
                    t3 += 1
                while res[t5] * 5 <= res[i]:
                    t5 += 1
            return res[index - 1]

Java 代码:

  public class Solution2 {

        // 1、2、3、4、5、6 都是丑数
        public int GetUglyNumber_Solution(int index) {
            if (index < 7) {
                return index;
            }

            // 状态的定义:第 i 个丑数的最小值,从 0 开始计算
            int[] dp = new int[index];
            dp[0] = 1;

            int t2 = 0;
            int t3 = 0;
            int t5 = 0;

            // 注意: i 从 1 开始
            for (int i = 1; i < index; i++) {
                dp[i] = min3(dp[t2] * 2, dp[t3] * 3, dp[t5] * 5);
                if (dp[i] == dp[t2] * 2) {
                    t2++;
                }
                if (dp[i] == dp[t3] * 3) {
                    t3++;
                }
                if (dp[i] == dp[t5] * 5) {
                    t5++;
                }
            }
            // System.out.println(Arrays.toString(dp));
            return dp[index - 1];
        }

        private int min3(int n1, int n2, int n3) {
            return Integer.min(Integer.min(n1, n2), n3);
        }

        public static void main(String[] args) {
            Solution2 solution2 = new Solution2();
            // 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24
            // [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]
            int getUglyNumberSolution = solution2.GetUglyNumber_Solution(15);
        }
    }

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 49 题] “丑数”做题记录

链接:https://www.javajike.com/article/3295.html

« [剑指 Offer 第 2 版第 48 题] “最长不重复字符串的子字符串”做题记录
[剑指 Offer 第 2 版第 51 题] “数组中的逆序对”做题记录»

相关推荐

QR code