再上到题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

再上到题

再上到题# JobHunting - 待字闺中

p*22011-11-25 08:11

1 楼

Provide an implementation of the following interface:
public interface Powers extends Iterator
{
/* Returns the next integer a in the arithmetic sequence of integers where
* a = m^n, m > 1 n > 1, and m and n are both integers
* Thus, the first few outputs will be 4, 8, 9, 16, 25, 27, 32, 36, etc.
*/
public Long next();
/* Resets the sequence to the beginning, such that the next call to next()
* will return 4.
*/
public void reset();
}

s*n2011-11-25 08:11

2 楼

优化一下，避免反复做乘法：
class PowerImpl implements Power {
List values;
public PowerImpl() {
//初始长度为3, 0和1闲置不用为了方便, values[2]对应到2^2
values = new ArrayList(3);
values[0]=dum; values[1]=dum;
values[2]=4;
}
public void reset() {
values.setSize(3);
values[2] = 4;
}
public int next() {
int nextValue=Integer.Max;
int nextIndex=-1;
for (int i=2; iint t = values[i];
if (t < nextValue) {
nextValue = t;
nextIndex = i;
}
}
values[nextIndex]=nextValue*nextIndex;
if (nextIndex==values.length-1) {
values.append(values.length*values.length);
}
return nextValue;
}
}

s*n2011-11-25 08:11

3 楼

再想一想，用heap快，减少排序时间。
class PowerImpl {
static class Node {
public int index;
public int value;
int compare(Node anotherNode) {
return this.value - anotherNode.value;
}
}
PriorityQueue values;
public PowerImpl() {
values.add(new Node(2, 4));
}
public int next() {
Node n = values.pop();
int retValue = n.value;
n.value = n.value * n.index;
values.add(n);
if (n.index==values.size()+1) {
int n = n.index+1;
values.add(new Node(n, n*n));
}
return retValue;
}
}

q*x2011-11-25 08:11

4 楼

想不出什么好算法。
coding倒是不难。

where
next()

【在 p*****2 的大作中提到】

: Provide an implementation of the following interface:
: public interface Powers extends Iterator
: {
: /* Returns the next integer a in the arithmetic sequence of integers where
: * a = m^n, m > 1 n > 1, and m and n are both integers
: * Thus, the first few outputs will be 4, 8, 9, 16, 25, 27, 32, 36, etc.
: */
: public Long next();
: /* Resets the sequence to the beginning, such that the next call to next()
: * will return 4.

n*w2011-11-25 08:11

5 楼

这个有点像careercup 150题里边一个题的变体。对只包含2 3 5因子的整数顺序print。
这题用min-heap会很好。唯一的问题，heap到底多大，什么时候插入一个entry挺麻烦。
if (n.index==values.size()+1) 这个判断不够。比如index是8，插入9^2，等于3^4，
重复元素。
感觉m应该给个上限。heap直接开m个entry。不断pop堆顶再判断是不是跟前一个重复。

【在 q****x 的大作中提到】

: 想不出什么好算法。
: coding倒是不难。
:
: where
: next()

q*x2011-11-25 08:11

6 楼

重复插入。pop时一直到栈顶比出栈院士大为止。

print。
烦。

【在 n*******w 的大作中提到】

: 这个有点像careercup 150题里边一个题的变体。对只包含2 3 5因子的整数顺序print。
: 这题用min-heap会很好。唯一的问题，heap到底多大，什么时候插入一个entry挺麻烦。
: if (n.index==values.size()+1) 这个判断不够。比如index是8，插入9^2，等于3^4，
: 重复元素。
: 感觉m应该给个上限。heap直接开m个entry。不断pop堆顶再判断是不是跟前一个重复。

s*n2011-11-25 08:11

7 楼

加了重复value处理，选value相同的index最大的一个，这样可以了吧？
class PowerImpl {
static class Node {
public int index;
public int value;
int compare(Node anotherNode) {
return this.value - anotherNode.value;
}
}
PriorityQueue values;
public PowerImpl() {
values.add(new Node(2, 4));
}
public int next() {
Node n = values.pop();
int retValue = n.value;
// find all nodes with least value
// for such nodes, values*=index
// find out n: the least value node with largest index
ArrayList temp = new ArrayList();
temp.add(n);
while(values.peek().value==n.value) {
Node n2 = values.pop());
if (n2.index > n.index) n=n2;
temp.add(n2);
}
for (int i=0; iNode x = temp[i];
x.value = x.value * x.index;
values.add(x);
}
// the least value node with largest index is the last index,
// then span the heap
if (n.index==values.size()+1) {
int n = n.index+1;
values.add(new Node(n, n*n));
}
return retValue;
}
}

print。
烦。

【在 n*******w 的大作中提到】

q*x2011-11-25 08:11

8 楼

白板代码不应该超过30行。20行都有点多。

【在 s******n 的大作中提到】

: 加了重复value处理，选value相同的index最大的一个，这样可以了吧？
: class PowerImpl {
: static class Node {
: public int index;
: public int value;
: int compare(Node anotherNode) {
: return this.value - anotherNode.value;
: }
: }
: PriorityQueue values;

m*q2011-11-25 08:11

9 楼

next()里面的if判断减少了不少重复的工作
一个小问题: 目前的代码会输出重复的数字，比如2^4 = 4^2
因为2^4的下一个2^5，而4^2的下一个是4^3和5^2，所以需要
把两者都保存在heap中。只是在从heap里面pop的时候，如果
发现当前pop出来的值和pop后的top一样，继续pop直到top值
不同。

【在 s******n 的大作中提到】

: 再想一想，用heap快，减少排序时间。
: class PowerImpl {
: static class Node {
: public int index;
: public int value;
: int compare(Node anotherNode) {
: return this.value - anotherNode.value;
: }
: }
: PriorityQueue values;

r*g2011-11-25 08:11

10 楼

对，我能想到的也是用相似做法
维护不同的队列，队列的头再用minheap维护，每从minheap里面取出一个，那么就在相
应的队列插入一个新的。
那么什么时候插入新的entry呢？比如取出的是K，那么需要查看ceil(sqrt(K))是否已
经出现在队列中了，如果没有就插入新的队列。

print。
烦。

【在 n*******w 的大作中提到】