当前位置:网站首页>剑指 Offer 49. 丑数(三指针法)
剑指 Offer 49. 丑数(三指针法)
2022-06-28 01:47:00 【BugMaker-shen】
一、263. 丑数
class Solution {
public:
bool isUgly(int n) {
if(n <= 0){
return false;
}
while(n % 2 == 0){
n >>= 1;
}
while(n % 3 == 0){
n /= 3;
}
while(n % 5 == 0){
n /= 5;
}
return n == 1;
}
};
二、264. 丑数 II
1. 三指针法
class Solution {
public:
int nthUglyNumber(int n) {
int idx2 = 0;
int idx3 = 0;
int idx5 = 0;
vector<int> nums(n, 0);
nums[0] = 1; // 第一个丑数为1
for(int i = 1; i < n; i++){
// 由数组里的丑数生成新的丑数,将最小的丑数存入数组
nums[i] = min(nums[idx2] * 2, min(nums[idx3] * 3, nums[idx5] * 5));
// 由哪个idx生成新的丑数,哪个idx往后移,用于下一次生成丑数
// 三个if并列,用于去重
if(nums[i] == nums[idx2] * 2){
idx2++;
}
if(nums[i] == nums[idx3] * 3){
idx3++;
}
if(nums[i] == nums[idx5] * 5){
idx5++;
}
}
return nums[n-1];
}
};
2. set排序且去重
set可以排序,我们用set保存已经生成的丑数,取出最小的丑数分别乘以2、3、5就可以得到新的丑数,存入set后自动排序,第n轮循环删除最小的丑数,即是第n个丑数
class Solution {
public:
int nthUglyNumber(int n) {
set<double> s; // set 是有序的,且不重复
double answer = 1;
for (int i = 1; i < n; i++) {
s.insert(answer * 2);
s.insert(answer * 3);
s.insert(answer * 5);
answer = *s.begin();
s.erase(answer);
}
return answer;
}
};
边栏推荐
- 买股票应该下载什么软件最好最安全?
- Intel Ruixuan A380 graphics card will be launched in China
- 云成本优化有哪些优秀实践?
- RichView TRVStyle
- 抓包整理外篇fiddler————了解工具栏[一]
- How to judge that the thread pool has completed all tasks?
- [today in history] June 13: parent-child disputes in packet switched networks; The founder of game theory was born; The embryonic form of interactive television
- 2-5基础配置-Win2003增加攻击面
- AgilePLM异常解决-Session篇
- [today in history] June 10: Apple II came out; Microsoft acquires gecad; The scientific and technological pioneer who invented the word "software engineering" was born
猜你喜欢
You got 8K in the 3-year function test, but were overtaken by the new tester. In fact, you are pretending to work hard
抓包整理外篇fiddler————了解工具栏[一]
【活动早知道】LiveVideoStack近期活动一览
[today in history] June 17: the creator of the term "hypertext" was born; The birth of Novell's chief scientist; Discovery channel on
[today in history] June 18: JD was born; The online store platform Etsy was established; Facebook releases Libra white paper
CMU puts forward a new NLP paradigm - reconstructing pre training, and achieving 134 high scores in college entrance examination English
math_ (function & sequence) meaning of limit & misunderstanding and symbol sorting / neighborhood & de centring neighborhood & neighborhood radius
[today in history] June 15: the first mobile phone virus; AI master simahe was born; Chromebook launch
Raspberry pie - environment settings and cross compilation
> Could not create task ‘:app:MyTest.main()‘. > SourceSet with name ‘main‘ not found.问题修复
随机推荐
Arduino esp8266 web LED control
Différences d'utilisation entre IsEmpty et isblank
[kotlin] basic introduction and understanding of its syntax in Android official documents
分布式事务—基于消息补偿的最终一致性方案(本地消息表、消息队列)
如何编写简洁代码?(上)
拾光者,云南白药!
被校园暴力,性格内向的马斯克凄惨而励志的童年
3年功能测试拿8K,被刚来的测试员反超,其实你在假装努力
You got 8K in the 3-year function test, but were overtaken by the new tester. In fact, you are pretending to work hard
视频编解码性能优化与实现
【522. 最长特殊序列 II】
math_ (function & sequence) meaning of limit & misunderstanding and symbol sorting / neighborhood & de centring neighborhood & neighborhood radius
[today in history] June 7: kubernetes open source version was released; Worldofwarcraft landed in China; Birth of the inventor of packet switching network
Agileplm exception resolution session
云成本优化有哪些优秀实践?
apache、iis6、ii7独立ip主机屏蔽限制ip访问
Yes, it's about water
[today in history] June 12: the United States entered the era of digital television; Mozilla's original developer was born; 3com merges with American Robotics
QEMU monitor usage
Simple elk configuration to realize production level log collection and query practice