m***n
发帖数: 2154 | 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();
}
这题目有点意思。 | p*****2
发帖数: 21240 | 2 可以看每一个整数是不是另一个整数的power。不是的话就找下一个。 | Z*****Z
发帖数: 723 | 3 如果需要反复调用的话，可以开个buffer（比如大小1024），buffer里存上一个范围内
的数（比如1到1024），但后对一定范围内的M和N遍历，挑出所有符合条件的数,然后依
次返回。
【在 p*****2 的大作中提到】
: 可以看每一个整数是不是另一个整数的power。不是的话就找下一个。
| m***n
发帖数: 2154 | 4 写了一个大家指正
public static class PowerIterator implements Iterator {
long previous = 4;
private boolean isPower(long value) {
int maxb= (int)(Math.log(value)+1);
//binary search from 2 to a^b
int maxa = (int)(Math.sqrt(value)+1);
int mina = 2;
for(int i=2;i<=maxb;i++) {
int minround = mina;
int maxround = maxa;
while(minround<=maxround) {
int mid = (minround+maxround)/2;
if((int)Math.pow(mid,i)
minround = mid+1;
}
else if((int)Math.pow(mid,i)==value) {
return true;
}
else {
maxround = mid -1;
}
}
}
return false;
}
public Long next() {
while(!isPower(previous)) {
previous++;
}
long val= Long.valueOf(previous);
previous++;
return val;
}
public boolean hasNext() {
return true;
}
public void remove() {
}
public void reset() {
previous = 4;
} | p*****2
发帖数: 21240 | 5
hasNext怎么总是true呢？
【在 m***n 的大作中提到】
: 写了一个大家指正
: public static class PowerIterator implements Iterator {
: long previous = 4;
: private boolean isPower(long value) {
: int maxb= (int)(Math.log(value)+1);
: //binary search from 2 to a^b
: int maxa = (int)(Math.sqrt(value)+1);
: int mina = 2;
: for(int i=2;i<=maxb;i++) {
: int minround = mina;
| X*K
发帖数: 87 | 6 靠，想来不难，但是很容易出错啊。这个算是验证过了。
public class NextPower implements Powers {
List powerList;
long previous;
public NextPower() {
powerList = new ArrayList();
reset();
}
@Override
public Long next() {
long min = Long.MAX_VALUE;
List minList = new ArrayList();
for (int i = 0; i < powerList.size(); ++i) {
int base = i + 2;
int power = powerList.get(i) + 1;
long n = (long) Math.pow(base, power);
if (n <= min && n > previous) {
if (n < min) {
minList.clear();
}
minList.add(i);
min = n;
}
}
for (int i : minList) {
if (i == powerList.size() - 1) {
powerList.add(1);
}
powerList.set(i, powerList.get(i) + 1);
}
previous = min;
return min;
}
@Override
public void reset() {
powerList.clear();
powerList.add(1);
previous = 0;
}
@Override
public boolean hasNext() {
return true;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
} |
|
