剑指Offer - 九度1214 - 丑数
2024-08-23 20:43:38
-
剑指Offer - 九度1214 - 丑数
2013-11-21 21:06- 题目描述:
-
把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。
习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
- 输入:
-
输入包括一个整数N(1<=N<=1500)。
- 输出:
-
可能有多组测试数据,对于每组数据,
输出第N个丑数。
- 样例输入:
-
3
- 样例输出:
-
3
题意分析:
题目要求按照从小到大的顺序找出因子只有2, 3, 5的第N个数。
由于所有数列中的f(n)都可表示为f(n) = 2 ^ x * 3 ^ y * 5 * z;那么求f(n)必然来自下面三种情况之一:
f(n) = f(a) * 2;
f(n) = f(b) * 3;
f(n) = f(c) * 3;
由于数列从小到大排列,f(n)应该取上述三个结果中最小的一个,去了以后,对应的iterator也应该前移一位。于是有了如下代码。
递推时间复杂度O(n),数组空间复杂度O(n)。
ZOJ 1095 -Humble Number和这题完全一个道理。// 652664 zhuli19901106 1214 Accepted 点击此处查看所有case的执行结果 1020KB 737B 10MS
//
#include <cstdio>
using namespace std; const int &mymin(const int &x, const int &y)
{
return (x < y ? x : y);
} int main()
{
const int MAXN = ;
int a[MAXN + ];
int p2, p3, p5;
int r2, r3, r5;
int minv;
int i; a[] = ;
a[] = ;
p2 = p3 = p5 = ;
for(i = ; i <= MAXN; ++i){
r2 = a[p2] * ;
r3 = a[p3] * ;
r5 = a[p5] * ;
minv = mymin(mymin(r2, r3), r5);
a[i] = minv;
if(minv == r2){
++p2;
}
if(minv == r3){
++p3;
}
if(minv == r5){
++p5;
}
} while(scanf("%d", &i) == ){
if(i >= && i <= MAXN){
printf("%d\n", a[i]);
}
} return ;
}
最新文章
- Android之ListView&;Json加载网络数据
- 为了解决mysqlbing翻译表字段问题而分析frm文件(持续更新)
- 前端技巧:禁止浏览器static files缓存篇(转)
- Hibernate案例-------基于xml配置,使用Hibernate实现对员工表的增、删、改、查功能
- ERROR 1045 (28000): Access denied for user &#39;root&#39;@&#39;localhost&#39; (using password: YES)
- Thread IsBcakgroud
- ansible高级用法
- 你所不知道的ref
- HDOJ/HDU 2087 剪花布条(indexOf()应用~~)
- 【网络流#8】POJ 3469 Dual Core CPU 最小割【ISAP模板】 - 《挑战程序设计竞赛》例题
- Base64技术:把对象转变成字符串
- iterator的romove方法的注意事项
- 用VSCode开发一个基于asp.net core 2.0/sql server linux(docker)/ng5/bs4的项目(3)
- 58 字体反爬攻略 python3
- azkaban group分组,权限
- BZOJ2716 [Violet]天使玩偶(cdq分治+树状数组)
- 配置svn用户及密码
- break&;&;continue
- FWT学习笔记
- hdu 1728 逃离迷宫 bfs记转向