My solution:
class FileCompare {
public boolean isDistanceZeroOrOne(IntFileIterator a, IntFileIterator b) {
while (a.hasNext() && b.hasNext()) {
int curA = a.next();
int curB = b.next();
if (curA != curB) {
int prevA = curA;
int prevB = curB;
if (a.hasNext() && b.hasNext()) {
curA = a.next();
curB = b.next();
if (curA != prevB && curB != prevA) {
// This means neither prevA nor prevB is the extra item added... 阅读全帖
他的意思是一旦碰到两个不同的,就把可能的三种情况,ins_a (a has extra letter),
ins_b(b has extra letter), replace都turn on, diff表示至少有一个不同的,这
时也turn on. 如果一直跑到最后所有的letter都相同,diff就remain as false, 也
return false.
一旦碰到两个不一样的,就要一直比较currA, currB, preA, preB, 如果preA !=
currB, 但insertionB是true, 说明insert extra letter to B是不可能的,就turn
off ins_B.同理其他的判断。
跑到最后总结,看A还是B还剩一个letter, 或者两者都跑到头了,再做判断。
我把这个超级genius的答案改写成java的了。。。。
public class FileCompare {
public boolean isDistanceZeroOrOne(IntFileIterator a,
IntFileIterator b) {
... 阅读全帖
只用constant内存的DP解法,自测能过所有test case
public boolean isDistanceZeroOrOne(IntFileIterator a, IntFileIterator b)
{
int up = 1;
int left = 1;
int diagnal = 0;
int dist = 0;
int currA = 0;
int currB = 0;
int prevA = 0;
int prevB = 0;
The following is an O(nlgn) solution for string of size n.
It maintains a heap for eligible chars, preferring longer streams.
Ineligible chars are maintained in a candidate queue, and added back
to the working queue when their position constraint is removed.
public class MinDistance {
public String rearrange(String source, int distance) {
// TODO Check params.
// WorkingQueue of eligible streams. Longest stream at head,
// but BackupStream at tail.
PriorityQueue阅读全帖
好像不难,我写个试试,大家给看看
IntergerIterator iter;
NoSuchElementException e = new NoSuchElementException();
public int next(){
if(!iter.hasNext()) throw e;
int n = iter.next();
return n>0?n:next();
}
public boolean hasNext(){
if(!iter.hasNext()) return false;
int n = iter.next();
return n>0?true:hasNext();
}
public void remove(){
iter.remove();
}
想简单了,hasNext移动iter,见笑了
嗯,看到了,想简单了
单独一个变量记录下个一个正数, 不过remove有问题, 因为hasNext过后,指针到下一
个正数, 就没办法删掉上一个next过的正数
比如 1,-1,2
next(); // get 1,iter到1后面
hasNext(); // test 2, iter到2后面
remove(); 删掉2,没法删掉1
这个题估计不考虑remove, 或者根据implementation来写具体的remove
class PositiveIterator{
IntergerIterator iter;
int nextPositive;
Integer P;
NoSuchElementException e = new NoSuchElementException();
public PositiveIterator(IntegerIterator iter){
this.iter=iter;
nextPositive = -1;
}
public int next(){
if(hasNext()) {
int ret = nextPositive;
nextPosi... 阅读全帖
好像不难,我写个试试,大家给看看
IntergerIterator iter;
NoSuchElementException e = new NoSuchElementException();
public int next(){
if(!iter.hasNext()) throw e;
int n = iter.next();
return n>0?n:next();
}
public boolean hasNext(){
if(!iter.hasNext()) return false;
int n = iter.next();
return n>0?true:hasNext();
}
public void remove(){
iter.remove();
}
想简单了,hasNext移动iter,见笑了
嗯,看到了,想简单了
单独一个变量记录下个一个正数, 不过remove有问题, 因为hasNext过后,指针到下一
个正数, 就没办法删掉上一个next过的正数
比如 1,-1,2
next(); // get 1,iter到1后面
hasNext(); // test 2, iter到2后面
remove(); 删掉2,没法删掉1
这个题估计不考虑remove, 或者根据implementation来写具体的remove
class PositiveIterator{
IntergerIterator iter;
int nextPositive;
Integer P;
NoSuchElementException e = new NoSuchElementException();
public PositiveIterator(IntegerIterator iter){
this.iter=iter;
nextPositive = -1;
}
public int next(){
if(hasNext()) {
int ret = nextPositive;
nextPosi... 阅读全帖
参照 peking2 的写了一个:
public Iterator conditionIterator(final Iterator input,
final Predicate pred) {
return new Iterator() {
T next = null;
public T next() {
if (!hasNext()) throw new NoSuchElementException("no more element");
T ret = next;
next = null;
return ret;
}
public boolean hasNext() {
if (next != null) return true;
else if (!input.hasNext()) return false;
... 阅读全帖
第一题:java.lang.ArrayIndexOutOfBoundsException: -1
T t=flatC.get(currIndex);
用的是楼主提供的testcase https://dl.dropbox.com/u/7472691/mitbbs/DeepIteratorImplTester.java
也贴个我的第一题吧:
public class DeepIteratorImpl implements Iterator {
private Map> deepIterators;
private Map singleElements;
private int index;
private int maxIndex;
// Constructor
public DeepIteratorImpl(Collection> c) {
if (c... 阅读全帖
攒了个段子请大牛点评一下:
// Not thread-safe
// Talk about validation requirement: none vs in next() vs in constructor
private static class DeepIterator implements Iterator {
private final Iterator
攒了个段子请大牛点评一下:
// Not thread-safe
// Talk about validation requirement: none vs in next() vs in constructor
private static class DeepIterator implements Iterator {
private final Iterator myIterator;
private final Class eleType;
private final Iterator empty = new ArrayList().iterator();
//lst1 has N items, and lst2 has M items
public static void Print( List lst1, List lst2)
{
Iterator itr1 = lst1.iterator();
Iterator itr2 = lst2.iterator();
while (itr1.hasNext() || itr2.hasNext())
{
int x=0, y=0;
if (itr1.hasNext())
{
x = itr1.next();
System.out.println(x);
}
if (itr2.hasNext())
{
y = itr2.next();
System.out.println... 阅读全帖
constructor:
List its = new ArrayList<>();
while(iteratorOfIterator.hasNext()){
its.add(iteratorOfIterator.next());
}
hasNext():
while (its.size()>0 && !its.get(0).hasNext() ){
its.remove(0);
}
return its.size()>0;
next():
if(hasNext()){
its.get(0).next();
}
else{
//error out or return null
}
Java:
public class PositiveIterator {
public static void main(String[] args) {
List list = new ArrayList();
for(int i = 0; i < 10; i++) {
list.add(i);
list.add(-i);
}
System.out.println(list.toString());
PositiveIterator posIter = new PositiveIterator(list.iterator());
for(int i = 0; i < 100; i++)
System.out.println(posIter.hasNext());
Java:
public class PositiveIterator {
public static void main(String[] args) {
List list = new ArrayList();
for(int i = 0; i < 10; i++) {
list.add(i);
list.add(-i);
}
System.out.println(list.toString());
PositiveIterator posIter = new PositiveIterator(list.iterator());
for(int i = 0; i < 100; i++)
System.out.println(posIter.hasNext());
public static Iterable mergeKSortedIterators(List
> Iters){
Queue minHeap = new PriorityQueue();
List result = new ArrayList();
for(Iterator iter : Iters){
if(iter.hasNext()){
minHeap.add(new newIter(iter.next(), iter));
}
}
how about in java? tested a few cases and it seems to work.
Map map = new HashMap();
map.put("dog",1);
map.put("sheep",5);
map.put("cat",3);
String s = "dog-cat+dog-sheep";
List list = new LinkedList();
StringTokenizer st = new StringTokenizer(s, "+-");
while(st.hasMoreTokens()) {
St... 阅读全帖
我的java 版本,欢迎指正
public static class Flattener {
final List> _vv;
int _curList = 0;
int _curOffset = 0;
public Flattener(final List> vv) {
if (vv == null) {
throw new IllegalArgumentException();
}
_vv = new ArrayList>();
for (int i = 0; i < vv.size(); ++i) {
if (vv.get(i) == null || vv.get(i).size() == 0) {
continue;
... 阅读全帖