文档章节

有些数的素因子只有3,5,7.请设计一个算法,找出其中第k个数

一贱书生
 一贱书生
发布于 2016/11/21 09:29
字数 228
阅读 12
收藏 0

 

public static int removeMin(Queue<Integer> q)
{
int min=q.peek();
for(Integer v:q)
{
if(min>v)
min=v;
}
while(q.contains(min))
{
q.remove(min);
}
return min;
}
public static void  addProducts(Queue<Integer> q,int v)
{
q.add(v*3);
q.add(v*5);
q.add(v*7);
}
public static int getKthMagicNumber(int k)
{
if(k<0) return 0;
int val=1;
Queue<Integer> q=new LinkedList<Integer>();
addProducts(q,1);
for(int i=0;i<k;i++)
{
val=removeMin(q);
addProducts(q,val);
}
return val;
}

public static int getKthMagicNumber(int k)
{
if(k<0)
{
return 0;
}
int val=0;
Queue<Integer> queue3=new LinkedList<Integer>();
Queue<Integer> queue5=new LinkedList<Integer>();
Queue<Integer> queue7=new LinkedList<Integer>();
queue3.add(1);
//从0到K的迭代
for(int i=0;i<=k;i++)
{
int v3=queue3.size()>0?queue3.peek():Integer.MAX_VALUE;
int v5=queue5.size()>0?queue5.peek():Integer.MAX_VALUE;
int v7=queue7.size()>0?queue7.peek():Integer.MAX_VALUE;
val=Math.min(v3,Math.min(v5,v7));
if(val==v3)
{
queue3.remove();
queue3.add(3*val);
queue5.add(5*val);
}
else if(val==v5)
{
queue5.remove();
queue5.add(5*val);
}
else if(val==v7)
{
queue7.remove();
}
queue7.add(7*val);//总是放入队列7
}
return val;
}

 

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
私信 提问
Humble Numbers(丑数) 超详解!

给定一个素数集合 S = { p[1],p[2],...,p[k] },大于 1 且素因子都属于 S 的数我们成为丑数(Humble Numbers or Ugly Numbers),记第 n 大的丑数为 h[n]。 算法 1:   一种最容易想到的方...

angel_kitty
2017/02/23
0
0
一些面试题,整理自网络

腾讯面试题:tcp三次握手的过程,accept发生在三次握手哪个阶段? 答accept发生在三次握手之后。 第一次握手:客户端发送syn包(syn=j)到服务器。 第二次握手:服务器收到syn包,必须确认客户...

waveer
2016/12/08
24
0
美团网2014笔试算法题汇总

1.链表翻转。给出一个链表和一个数k,比如链表1→2→3→4→5→6,k=2,则翻转后2→1→4→3→6→5,若k=3,翻转后3→2→1→6→5→4,若k=4,翻转后4→3→2→1→5→6,用程序实现。 #include u...

u011729265
2013/10/01
0
0
郑州大学2018新生训赛第十场题解

  比赛(补题)地址:http://222.22.65.164/contest.php?cid=1013   总述:这次新生赛难度偏于平和,但涵盖方面甚广,其中一道签到题是c语言题,并且有两道是hdu一百题的原题,一道简单的...

moonfair
2018/11/17
0
0
改进的筛素数法

最简单的筛素数法方法就是从2开始,将所以2的倍数去掉,然后从3开始,将3的倍数去掉。根据这样很容易写出代码,下面代码就是是筛素数法得到100以内的素数并保存到primes[]数组中。 可以看出这...

长平狐
2012/12/10
28
0

没有更多内容

加载失败,请刷新页面

加载更多

Java并发编程基础(二)

线程安全与数据同步

chendom
15分钟前
0
0
在Centos7 上安装SVN

在Centos7 上安装SVN 2017年11月16日 17:07:54 crossangles_2017 阅读数:2543 1、安装 使用yum安装非常简单: yum install subversion 2、配置 创建仓库 我们这里在/opt下建立一个名为svn的...

linjin200
16分钟前
0
0
牛津词典 2018 年度词汇 ——「有毒」!

简评:本文并没有「标题党」,牛津词典公布的 2018 年度词汇就是 Toxic. 意为「有毒的」。 2018 was toxic. Toxic 这个词是什么意思呢? 牛津词典(Oxford Dictionaries)在 Word of the Da...

极光推送
22分钟前
1
0
浅谈Service Mesh体系中的Envoy

https://blog.csdn.net/yunqiinsight/article/details/81019255

易野
31分钟前
1
0
嵌入式应用选择合适的微控制器

准备所需硬件接口列表 使用微控制器的基本硬件框图,准备一份微控制器需要支持的所有外设接口的列表。微控制器中有两种常见的接口类型需要列出。第一种是通信接口,这些是外围设备,如USB,S...

linuxCool
39分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部