文档章节

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

一贱书生
 一贱书生
发布于 2016/11/21 09:29
字数 228
阅读 11
收藏 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
CF 470 div2 B - D 题解.

传送门 B: 题意: 两个人轮流玩游戏, 首先有一个x0 >= 3, 然后A先手,第 i 轮每个人选择一个小于X(i-1)的素数然后算出这个素数的倍数并且离x(i-1)最近的那个数作为xi, 现在给定x2,问最小的x...

anxdada
03/12
0
0
微软等公司数据结构+算法面试100题

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / / 6 14 / / / / 4 ...

chambai
2012/08/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

【挑战剑指offer】系列03:逆序打印单链表

本系列的算法原题来自于“牛客网-剑指offer”,写这个板块,不仅仅是解决算法问题本身,更是手动提高难度、自行变式,思考更多的解决方案,以带给自己一些启发。 1. 【逆序打印单链表】原始题...

LinkedBear
9分钟前
1
0
Linux内存布局

今天这篇文章主要是我之前看Linux内核相关知识和博客Gustavo Duarte中。我主要是看了这篇博客,并且结合之前的知识,对内存管理的的理解又上升了一个档次。所以想通过这篇文章总结下。 我们先...

linuxprobe16
28分钟前
1
0
day94-20180921-英语流利阅读-待学习

记录死亡还是消费死者?自杀报道的媒体偏见 雪梨 2018-09-21 1.今日导读 自杀事件报道一直是新闻报道的重要部分,具有骇人听闻、吸引眼球的特点。可是在报道这些事件的时候,除了客观陈述事实...

飞鱼说编程
34分钟前
3
0
如何通过 J2Cache 实现分布式 session 存储

做 Java Web 开发的人多数都会需要使用到 session (会话),我们使用 session 来保存一些需要在两个不同的请求之间共享数据。一般 Java 的 Web 容器像 Tomcat、Resin、Jetty 等等,它们会在...

红薯
今天
3
0
C++ std::thread

C++11提供了std::thread类来表示一个多线程对象。 1,首先介绍一下std::this_thread命名空间: (1)std::this_thread::get_id():返回当前线程id (2)std::this_thread::yield():用户接口...

yepanl
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部