p*****2 发帖数: 21240 | 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******n 发帖数: 3946 | 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; i
int 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******n 发帖数: 3946 | 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****x 发帖数: 7404 | 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*******w 发帖数: 687 | 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****x 发帖数: 7404 | 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******n 发帖数: 3946 | 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; i
Node 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 的大作中提到】 : 这个有点像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 发帖数: 7404 | 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**q 发帖数: 189 | 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*******g 发帖数: 1335 | 10 对,我能想到的也是用相似做法
维护不同的队列,队列的头再用minheap维护,每从minheap里面取出一个,那么就在相
应的队列插入一个新的。
那么什么时候插入新的entry呢?比如取出的是K,那么需要查看ceil(sqrt(K))是否已
经出现在队列中了,如果没有就插入新的队列。
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堆顶再判断是不是跟前一个重复。
|