当前位置:网站首页>剑指 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;
}
};
边栏推荐
- Is online stock investment exchange group safe? Is it reliable to open an account for free?
- 一位博士在华为的22年(干货满满)
- 无代码软件发展简史及未来趋势
- A16z:元宇宙解锁游戏基础设施中的新机遇
- [today in history] June 17: the creator of the term "hypertext" was born; The birth of Novell's chief scientist; Discovery channel on
- Reading makes people quiet
- The first place on the list - the carrying rate of front-end equipment is up to 10%, and the top 10 suppliers of digital key solutions
- Simple elk configuration to realize production level log collection and query practice
- [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
- Raspberry pie - environment settings and cross compilation
猜你喜欢
STM32的C语言与汇编语言混合编程
[today in history] June 15: the first mobile phone virus; AI master simahe was born; Chromebook launch
Simple file transfer protocol TFTP
Arduino esp8266 web LED control
Thesis reading: General advantageous transformers
喜新厌旧?IT公司为什么宁愿花20k招人,也不愿涨薪留住老员工
如何判断线程池已经执行完所有任务了?
Domain Name System
PSM summary
将PCAP转换为Json文件的神器:joy(安装篇)
随机推荐
JDBC与MySQL数据库
[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
新手炒股开户选哪家证券平台办理是最好最安全的
Arduino Esp8266 Web LED控制
ByteDance Interviewer: how to calculate the memory size occupied by a picture
Heartless sword English Chinese bilingual poem 004 Meditation
被校园暴力,性格内向的马斯克凄惨而励志的童年
Online JSON to plaintext tool
[today in history] June 5: Lovelace and Babbage met; The pioneer of public key cryptography was born; Functional language design pioneer born
apache、iis6、ii7独立ip主机屏蔽限制ip访问
[today in history] June 7: kubernetes open source version was released; Worldofwarcraft landed in China; Birth of the inventor of packet switching network
Apache——阿帕奇簡介
RichView TRVStyle
You got 8K in the 3-year function test, but were overtaken by the new tester. In fact, you are pretending to work hard
[today in history] June 24: Netease was established; The first consumer electronics exhibition was held; The first webcast in the world
Simple elk configuration to realize production level log collection and query practice
Intel Ruixuan A380 graphics card will be launched in China
访问网站提示:您未被授权查看该页恢复办法
Severe Tire Damage:世界上第一个在互联网上直播的摇滚乐队
您的物联网安全性是否足够强大?