LeetCode 1201. 丑数 III(最小公倍数+二分查找)
发布日期:2021-07-01 03:25:06
浏览次数:2
分类:技术文章
本文共 2402 字,大约阅读时间需要 8 分钟。
1. 题目
请你帮忙设计一个程序,用来找出第 n 个丑数。
丑数是可以被 a 或 b 或 c 整除的 正整数。
示例 1:输入:n = 3, a = 2, b = 3, c = 5输出:4解释:丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。示例 2:输入:n = 4, a = 2, b = 3, c = 4输出:6解释:丑数序列为 2, 3, 4, 6, 8, 9, 12... 其中第 4 个是 6。示例 3:输入:n = 5, a = 2, b = 11, c = 13输出:10解释:丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 个是 10。示例 4:输入:n = 1000000000, a = 2, b = 217983653, c = 336916467输出:1999999984 提示:1 <= n, a, b, c <= 10^91 <= a * b * c <= 10^18本题结果在 [1, 2 * 10^9] 的范围内
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/ugly-number-iii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题
- 类似题目:
class Solution { public: long nthUglyNumber(long n, long a, long b, long c) { long long mid; long long lcm_ab = lcm(a,b);//ab的最大公约数 long long lcm_ac = lcm(a,c);// ac long long lcm_bc = lcm(b,c);// bc long long lcm_abc = lcm(a,lcm_bc);//abc的最大公约数 //一个周期内,abc的最大公约数假设为n,有多少个丑数? //是 a 的倍数的 n/a 个 减去重复的 case 4,6,7 case 1 //是 b 的倍数的 n/b 个 减去重复的 case 4,5,7 case 2 //是 c 的倍数的 n/c 个 减去重复的 case 5,6,7 case 3 //是 ab 的倍数的 n/lcm_ab 个 减去重复的 case 7 case 4 //是 bc 的倍数的 n/lcm_bc 个 减去重复的 case 7 case 5 //是 ac 的倍数的 n/lcm_ac 个 减去重复的 case 7 case 6 //是 abc 的倍数的 n/lcm_abc = 1 个 case 7 //case1-7汇总:如下 long long count = lcm_abc/a + lcm_abc/b + lcm_abc/c - lcm_abc/lcm_ab - lcm_abc/lcm_ac - lcm_abc/lcm_bc + 1; long long factor = n/count;//到lcm_abc处有count个丑数,n个丑数还需要几倍 long long rest = n%count;//剩余的个数 long long ans = factor*lcm_abc;//在factor*lcm_abc处已经得到,还差rest个丑数 if(rest > 0) { long long l = 1, r = lcm_abc, mid; while(l <= r) { mid = l+((r-l)>>1); count = mid/a + mid/b + mid/c - mid/lcm_ab - mid/lcm_ac - mid/lcm_bc + mid/lcm_abc; if(count >= rest) r = mid-1; else// if(count < rest) l = mid+1; } ans += l; } return ans; } long lcm(long a, long b)//最小公倍数 { return a*b/gcd(a,b); } long gcd(long a, long b)//最大公约数 { long r; while(b) { r = a%b; a = b; b = r; } return a; }};
二分处还可以写做:
while(l < r){ mid = l+((r-l)>>1); count = mid/a + mid/b + mid/c - mid/lcm_ab - mid/lcm_ac - mid/lcm_bc + mid/lcm_abc; if(count >= rest)//mid处可能是答案,因为最后如[1,2]取不到2,不能mid-1 r = mid; else// if(count < rest) l = mid+1;}
0 ms 6 MB
转载地址:https://michael.blog.csdn.net/article/details/105920352 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年04月13日 17时04分45秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
SpringBoot 配置 ELK 环境
2019-05-02
Caffeine !你简直太骚了!
2019-05-02
Windows 10将预装Windows Terminal
2019-05-02
非常强悍的 RabbitMQ 总结,写得真好!
2019-05-02
除了Oracle,谁为JDK 16修复最多issue?
2019-05-02
字符编码,原来是SQL不走索引的元凶之一!
2019-05-02
必须了解的十个高级 SQL 概念
2019-05-02
用了 3 年 Apollo,最后我选择了 Nacos,原因不多说了
2019-05-02
送40本Java畅销书
2019-05-02
ElasticSearch 面试 4 连问,你顶得住么?
2019-05-02
把废弃的Kindle改装成自己的Linux开发平台
2019-05-02
RabbitMQ 如何对消费端限流?
2019-05-02
各种陷进,盘点那些坑你没商量的JDK方法
2019-05-02
老板要我开发一个简单的工作流引擎 !
2019-05-02
SpringCloud中Hystrix容错保护原理及配置,看它就够了!
2019-05-02
因为BitMap,白白搭进去8台服务器...
2019-05-02
让Jenkins自动布署你的Vue项目
2019-05-02
诡异!MyBatis的Insert方法一直返回"-2147482646"?
2019-05-02
Web开发应该学习的Token登录认证知识
2019-05-02
通过 Docker 部署 Redis 集群
2019-05-02