首页 > 其他分享 >剑指Offer49 -- DP/贪心

剑指Offer49 -- DP/贪心

时间:2023-03-18 14:46:23浏览次数:49  
标签:pre 丑数 Offer49 -- int DP pre1 pre3 pre2

1. 题目描述

丑数



2. 思路

很明显,丑数就是 \(2,3,5\) 的乘积组合。
最一开始,我竟然傻傻的 \(dfs\) + \(set\) 来求解,其实仔细想想,\(dfs\) 肯定是不行的,因为 \(dfs\) 会一条路走到黑。
理想情况下,我们希望每个丑数都按位置放置,而不是跳着来的,例如,\(6\) 之后的丑数应该是 \(8\),而不是 \(9\)。
对于下一个丑数来说,他只有三种可能:

pre1 * 2;
pre2 * 3;
pre3 * 5;

pre1, pre2, pre3 可能是不同的数。我们希望每次都选取这个组合的最小值,并且刚好是下一个丑数。
那么我们就需要保证,pre1,pre2,pre3 不能大了,也不能小,并且它们都是一个个整数。
好吧,我承认我的论述有点乱,从实际的例子出发好了。
最开始,有一个特殊的丑数 \(1\),从 \(1\) 出发,有:

1 * 2 = 2;
1 * 3 = 3;
1 * 5 = 5;

我们应该选择 \(2\),那么,此时 \(pre1\) 也就是 \(1*2\) 中的 \(1\) 就要编程 \(2\) 了,\(2\) 就是 \(1\) 之后的最近的丑数。即:

2 * 2 = 4;
1 * 3 = 3;
1 * 5 = 5;

此时我们应该选择 \(3\),那么,又变成:

2 * 2 = 4;
2 * 3 = 6;
1 * 5 = 5;

选择 \(4\),变成;

3 * 2 = 6;
2 * 3 = 6;
1 * 5 = 5;

选择 \(5\),变成:

3 * 2 = 6;
2 * 3 = 6;
2 * 5 = 10;

选择 \(6\),但是此时有两个 \(6\) 同时出现,我们同时修改 \(pre2\) 和 \(pre3\),因为不可以重复:

4 * 2 = 8;
3 * 3 = 9;
2 * 5 = 10;

那么,自然而然的,我们可以通过一种类似三指针的方式,求解。



3. 代码

class Solution {
public:
    int nthUglyNumber(int n) {
        int f[n + 10];
        f[0] = 1;
        int pre1 = 0, pre2 = 0, pre3 = 0;
        for(int i = 1; i <= n; i ++ ) {
            int a = f[pre1] * 2, b = f[pre2] * 3, c = f[pre3] * 5;
            int minx = min({a, b, c});
            f[i] = minx;
            // 注意下面不能都用if-else
            // 因为丑数不可以重复出现
            if(a == minx)   pre1 ++ ;
            if(b == minx)   pre2 ++ ;
            if(c == minx)   pre3 ++ ;
        }
        return f[n - 1];
    }
};

4. 思路2,贪心 + 优先队列 + set

思路就是,每次选取一个最小值 \(x\) ,将它发展出来的三个丑数 \(x*2\), \(x*3\), \(x*5\) 放到优先队列当中。
然后,将每次从优先队列取出来的数放到哈希表中,当放入哈希表中的数的个数为 \(n\) 时,就表示我们取出来最小的 \(n\) 个丑数。
然后,就是注意去重就行了。

5. 代码

class Solution {
public:
    int nthUglyNumber(int n) {
        priority_queue<long long, vector<long long>, greater<long long>> q;
        unordered_set<int> s;
        int start = 1;
        q.push(start);
        while(q.size()) {
            auto t = q.top();   q.pop();
            if(s.count(t))  continue;   // 去重
            s.insert(t);
            if(s.size() == n)   return t;
            q.push(t * 2);
            q.push(t * 3);
            q.push(t * 5);
        }
        return -1;
    }
};

6. 总结

其实呢,这题,想到是不太好想,看别人的分析也不太容易看懂,但是看代码就一看就懂了。
其实这题,就像贪心,因为丑数只能从另一个丑数通过 pre1*2,pre2*3,pre3*5(pre都是丑数),的方式得到,因此,找出 \(n\) 个丑数时很容易的。
难点在于,如何保证这 \(n\) 个丑数恰好是最小的 \(n\) 个呢?贪心呗!
如果,我们希望通过 pre1*2,pre2*3,pre3*5 得到的丑数尽可能的小,那么,pre1, pre2, pre3 当然也要尽可能的小,那么,我们就每次枚举最小的 pre
如果使用过了,就要增大 pre,并且我们希望增大的幅度近可能的小,那么与 \(pre\) 相邻的那个丑数就是最好的选择了!
另外,当我们需要增加 \(pre\) 时,与 \(pre\) 相邻的丑数一定存在,因为只要增大,就意味着我们找到了一个新的丑数。

标签:pre,丑数,Offer49,--,int,DP,pre1,pre3,pre2
From: https://www.cnblogs.com/ALaterStart/p/17230583.html

相关文章

  • C 编程指南
    C编程指南编译和执行gcc不是真正的编译器,而是所谓的“编译器驱动程序”,因此它协调了编译的许多步骤【通常有4~5个步骤】gcc将执行C预处理器cpp来处理某些指令......
  • REST风格下的SpringMVC简单响应方法
    学习中,如有错误请见谅  项目结构   ServletContainersInitConfigpublicclassServletContainersInitConfigextendsAbstractAnnotationConfigDispatcher......
  • 万字血书Vue—Vue的核心概念
    MVVMM:模型(Model):dataV:视图(View):模板VM:视图模型(ViewModel):Vue实例对象Vue收到了MVVM模型的启发,MVVM是vue实现数据驱动视图和双向数据绑定的核心原理,通过ViewModel监听DOM......
  • 看板实现数字滚动显示效果
    <!DOCTYPEhtml><html><head><metacharset="utf-8"><title></title><scriptsrc="./js/vue.js"></script><stylescop......
  • linux centos yum 单独安装 mysqldump
    在linux下,mysqldump属于mysql的组件,可以安装mysql获取,如:$yum-yinstallmysql-client1一般情况下,是安装mysql的时候获得mysqldump组件,但有时可能已经安装Mar......
  • java 加密和json格式化代码 、http url提交
      CloseableHttpClientclient=HttpClients.createDefault();CloseableHttpResponseres=null;JsonObjectjson=null;......
  • Vue指令:内置指令和自定义指令
    Vue指令Vue指令指的是,以v-开头的一组特殊语法内置指令v-textv-text指令的作用是:设置标签的内容默认写法会替换全部内容,差值表达式{{}}只会替换指定内容内部......
  • c++常用STL库及常用函数
    临近各种算法比赛,相信很多人想笔者一样还总是记不住很多函数的用法,特此总结一下常用的STL标准库以及标准函数,希望能够有所帮助。1.输入输出输入输出一般用两个标准库:#i......
  • 属性描述符defineProperty
    属性描述符是会直接在一个对象上定义一个新属性,或者修改一个对象的现有属性,并返回此对象。属性描述符有两种主要形式:数据描述符和存取描述符。数据描述符是一个具有值的属......
  • 重装系统
    最近系统盘文件损坏,开机黑屏,折腾了很长时间,在此做个记录。制作U盘启动盘准备材料:U盘一个,大于8Gwin10系统镜像启动盘制作软件下载系统镜像,从官网下载win10系统镜像......