y*****e
发帖数: 712 | 1 在一亩三分地上看到的，听说挂了很多人。咱板上牛人多，发上来和大家讨论一下呀
class IntFileIterator {
boolean hasNext();
int next();
}
class{
public boolean isDistanceZeroOrOne(IntFileIterator a, IntFileIterator b)；
}
// return if the distance between a and b is at most 1..
// Distance: minimum number of modifications to make a=b
// Modification:
// 1. change an int in a
// 2. insert an int to a
// 3. remove an int from a
这题就是one edit distance的变形题，难点在于给的Iterator，事先不知道两个file
的长度，也不允许用extra space（所以不能转成两个string再比），那么一个个往前
跑的时候就得三种情况都考虑。。。。 | v********o
发帖数: 67 | 2 zero or one限定很死了吧？判断zero没啥好说的。判断one也只要记录第一次不匹配的
位置，然后回溯就可以了吧，总共就change add remove三种情况了。不知道是不是想
简单了？
【在 y*****e 的大作中提到】
: 在一亩三分地上看到的，听说挂了很多人。咱板上牛人多，发上来和大家讨论一下呀
: class IntFileIterator {
: boolean hasNext();
: int next();
: }
: class{
: public boolean isDistanceZeroOrOne(IntFileIterator a, IntFileIterator b)；
: }
: // return if the distance between a and b is at most 1..
: // Distance: minimum number of modifications to make a=b
| m******e
发帖数: 201 | 3 难在iterater不能回头啊
【在 v********o 的大作中提到】
: zero or one限定很死了吧？判断zero没啥好说的。判断one也只要记录第一次不匹配的
: 位置，然后回溯就可以了吧，总共就change add remove三种情况了。不知道是不是想
: 简单了？
| g*****5
发帖数: 87 | 4 zeroorone的话存一下前两个的值就行了吧，不用回头啊 | w*******i
发帖数: 186 | 5 不允许用extra space 这个比较狠啊 否定了用dp或者memorization。
感觉如果增加时间复杂度的话可以是不是可以允许iterator的copy呢？这里copy一个
iterator感觉可以不断调用next直到新的iterator的val的地址与另一个旧的相等。这
样即使iterator不能回走也可以完成递归。 | s******s
发帖数: 2721 | 6 Code snippets:
boolean isDistanceZero(IntFileIterator a, IntFileIterator b) {
while (a.hasNext() && b.hasNext()) {
if (a.next() != b.next()) {
return false;
}
}
return a.hasNext() == b.hasNext();
}
boolean isDistanceZeroOrOne(IntFileIterator a, IntFileIterator b) {
while (a.hasNext() && b.hasNext()) {
IntFileIterator curA = a;
IntFileIterator curB = b;
if (a.next() != b.next()) {
return isDistanceZero(a, curB) || isDistanceZero(curA, b) ||
isDistanceZero(a, b);
}
}
// A and B are the same till this point; make sure at most one element
left so far...
if (a.hasNext()) a.next();
if (b.hasNext()) b.next();
return !a.hasNext() && !b.hasNext();
}
【在 m******e 的大作中提到】
: 难在iterater不能回头啊
| s******s
发帖数: 2721 | 7 这个跟DP有神马关系呀
【在 w*******i 的大作中提到】
: 不允许用extra space 这个比较狠啊 否定了用dp或者memorization。
: 感觉如果增加时间复杂度的话可以是不是可以允许iterator的copy呢？这里copy一个
: iterator感觉可以不断调用next直到新的iterator的val的地址与另一个旧的相等。这
: 样即使iterator不能回走也可以完成递归。
| S*******C
发帖数: 822 | 8 这答案不对，看我测试结果，IntFileIterator对象是mutable的
[1, 2, 3, 4, 5, 9, 8, 7, 6]
[1, 2, 3, 4, 5, 4, 8, 7, 6]
true
=====================
[1, 2, 3, 4, 5, 9, 8, 7, 6]
[1, 2, 3, 4, 5, 9, 7, 6]
false
=====================
[1, 2, 3, 4, 5, 9, 8, 7, 6]
[1, 2, 3, 4, 5, 9, 8, 7, 1, 6]
false
=====================
[1, 2, 3, 4, 5, 9, 8, 7, 6]
[1, 2, 3, 4, 5, 9, 8, 7, 6, 3, 2]
false
=====================
[1, 2, 3, 4, 5, 4, 8, 7, 6]
[1, 2, 3, 4, 5, 9, 7, 6]
false
=====================
[1, 2, 3, 4, 5, 4, 8, 7, 6]
[1, 2, 3, 4, 5, 9, 8, 7, 1, 6]
false
=====================
[1, 2, 3, 4, 5, 4, 8, 7, 6]
[1, 2, 3, 4, 5, 9, 8, 7, 6, 3, 2]
false
=====================
[1, 2, 3, 4, 5, 9, 7, 6]
[1, 2, 3, 4, 5, 9, 8, 7, 1, 6]
false
=====================
[1, 2, 3, 4, 5, 9, 7, 6]
[1, 2, 3, 4, 5, 9, 8, 7, 6, 3, 2]
false
=====================
[1, 2, 3, 4, 5, 9, 8, 7, 1, 6]
[1, 2, 3, 4, 5, 9, 8, 7, 6, 3, 2]
false
=====================
package given_two_IntFileIterators_determine_if_they_are_1_or_0_edit_
distance_apart;
public class Solution {
static Solution sol = new Solution();
static String dir = "D:\workspace_interviews\input\";
static void test(int s1, int s2){
IntFileIterator a = new IntFileIterator(dir+s1+".txt");
IntFileIterator b = new IntFileIterator(dir+s2+".txt");
a.print();
b.print();
System.out.println(sol.isDistanceZeroOrOne(a, b));
System.out.println("=====================");
}
public static void main(String args[]){
test(1, 2);
test(1, 3);
test(1, 4);
test(1, 5);
test(2, 3);
test(2, 4);
test(2, 5);
test(3, 4);
test(3, 5);
test(4, 5);
}
// _given_two_strings_S_and_T_determine_if_they_are_both_one_edit_distance_
apart
public boolean isDistanceZeroOrOne(IntFileIterator a, IntFileIterator b) {
while (a.hasNext() && b.hasNext()) {
IntFileIterator curA = a;
IntFileIterator curB = b;
if (a.next() != b.next()) {
return isDistanceZero(a, curB) || isDistanceZero(curA, b)
|| isDistanceZero(a, b);
}
}
// A and B are the same till this point; make sure at most one element
// left so far...
if (a.hasNext())
a.next();
if (b.hasNext())
b.next();
return !a.hasNext() && !b.hasNext();
}
private boolean isDistanceZero(IntFileIterator a, IntFileIterator b) {
while (a.hasNext() && b.hasNext()) {
if (a.next() != b.next())
return false;
}
return a.hasNext() == b.hasNext();
}
}
package given_two_IntFileIterators_determine_if_they_are_1_or_0_edit_
distance_apart;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.Iterator;
import java.util.Scanner;
import java.util.List;
import java.util.LinkedList;
public class IntFileIterator implements Iterator{
private List elements;
private int index;
public IntFileIterator(String path) {
index = -1;
elements = new LinkedList();
readFile(path);
}
public Integer next() {
if (index == elements.size())
return null;
return elements.get(++index);
}
public boolean hasNext() {
return index < elements.size() - 1;
}
public void remove() {
throw new UnsupportedOperationException("Remove is not supported by
WordsIter");
}
private void readFile(String path){
FileReader fr = null;
BufferedReader br = null;
Scanner in = null;
try {
fr = new FileReader(path);
br = new BufferedReader(fr);
in = new Scanner(br);
while (in.hasNextInt())
elements.add(in.nextInt());
} catch (FileNotFoundException e) {
e.printStackTrace();
} finally {
try {
if (in != null)
in.close();
if (br != null)
br.close();
if (fr != null)
fr.close();
} catch (IOException e) {
}
}
}
public void print(){
System.out.println(elements);
}
}
【在 s******s 的大作中提到】
: Code snippets:
: boolean isDistanceZero(IntFileIterator a, IntFileIterator b) {
: while (a.hasNext() && b.hasNext()) {
: if (a.next() != b.next()) {
: return false;
: }
: }
: return a.hasNext() == b.hasNext();
: }
: boolean isDistanceZeroOrOne(IntFileIterator a, IntFileIterator b) {
| S*******C
发帖数: 822 | | C****t
发帖数: 53 | 10 def OneorZero(a, b):
return recur(a, b) <=1
def recur(a,b):
# ---------base cases
if not a.hasNext() and not b.hasNext(): return 0
elif not b.hasNext():
a.next()
if a.hashNext(): return 2
else: return 1
else:
b.next()
if b.hashNext(): return 2
else: return 1
cp_a, cp_b = a, b
if a.next() == b.next(): return 0 + recur(a,b)
else: return 1 + min( recur(a,b), recur(cp_a, b), recur(a, cp_b) ) | | | s******s
发帖数: 2721 | 11 哪里不对？
【在 S*******C 的大作中提到】
: 这答案不对，看我测试结果，IntFileIterator对象是mutable的
: [1, 2, 3, 4, 5, 9, 8, 7, 6]
: [1, 2, 3, 4, 5, 4, 8, 7, 6]
: true
: =====================
: [1, 2, 3, 4, 5, 9, 8, 7, 6]
: [1, 2, 3, 4, 5, 9, 7, 6]
: false
: =====================
: [1, 2, 3, 4, 5, 9, 8, 7, 6]
| S*******C
发帖数: 822 | 12 [1, 2, 3, 4, 5, 9, 8, 7, 6]
[1, 2, 3, 4, 5, 9, 7, 6]
这个例子应该是true而不是false，还有很多错误
【在 s******s 的大作中提到】
: 哪里不对？
| s******s
发帖数: 2721 | 13 哈哈，你还真的去执行了。看出代码哪行错了吗？
你用java写的，下面这行是不是给你麻烦了？
IntFileIterator curA = a;
有没有想过我不希望curA不会因为a.next()而改变？
【在 S*******C 的大作中提到】
: [1, 2, 3, 4, 5, 9, 8, 7, 6]
: [1, 2, 3, 4, 5, 9, 7, 6]
: 这个例子应该是true而不是false，还有很多错误
| S*******C
发帖数: 822 | 14 你每次调用next()方法都会使index往后移动，而且不能回退，也就是说你调用next()
方法时改变了对象中的成员变量index
【在 s******s 的大作中提到】
: 哈哈，你还真的去执行了。看出代码哪行错了吗？
: 你用java写的，下面这行是不是给你麻烦了？
: IntFileIterator curA = a;
: 有没有想过我不希望curA不会因为a.next()而改变？
| s******s
发帖数: 2721 | 15 so what? curA and curB不能变。
【在 S*******C 的大作中提到】
: 你每次调用next()方法都会使index往后移动，而且不能回退，也就是说你调用next()
: 方法时改变了对象中的成员变量index
| Q**F
发帖数: 995 | 16 如果你的curA 和 curB 都是reference或者指针，那么a，b移动的时候，curA和curB也
跟着移动了
【在 s******s 的大作中提到】
: so what? curA and curB不能变。
| s******s
发帖数: 2721 | 17 那我补充一下我原先的意思不是reference，这样行了吗？
你自己去看看13楼，我觉得已经说得很清楚了。
我是一个c++码农。
【在 Q**F 的大作中提到】
: 如果你的curA 和 curB 都是reference或者指针，那么a，b移动的时候，curA和curB也
: 跟着移动了
| Q**F
发帖数: 995 | 18 问题是这个不是你能左右的，而是取决与IntFileIterator自己的实现。
当你做
IntFileIterator curA = a
假设copy／assignment constructor 只给你返回reference／指针，你怎么办？ | s******s
发帖数: 2721 | 19 我可以表示我很无语吗？这是一个算法题。。。
我不知道争论language有什么意义。。。那如果别人写了IntFileIterator curA = new
IntFileIterator(a)，你是不是还要追究constructor怎么实现的。
by default，c++就是直接拷贝value的，你想弄一个by reference的copy constructor
是非常非常的麻烦。。。
【在 Q**F 的大作中提到】
: 问题是这个不是你能左右的，而是取决与IntFileIterator自己的实现。
: 当你做
: IntFileIterator curA = a
: 假设copy／assignment constructor 只给你返回reference／指针，你怎么办？
| r****7
发帖数: 2282 | 20 如果做one edit distance是自己做的而不是看答案的，应该这个题也会做吧。。。
【在 y*****e 的大作中提到】
: 在一亩三分地上看到的，听说挂了很多人。咱板上牛人多，发上来和大家讨论一下呀
: class IntFileIterator {
: boolean hasNext();
: int next();
: }
: class{
: public boolean isDistanceZeroOrOne(IntFileIterator a, IntFileIterator b)；
: }
: // return if the distance between a and b is at most 1..
: // Distance: minimum number of modifications to make a=b
| | | p****e
发帖数: 4 | 21 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
// In other words, one of them could be changed.
if (curA != curB)
return false; // No more difference is allowed
return isSame(a, b); // check if the remaining parts of A and B
are same
}
if (curA == prevB && curB == prevA) // two different pairs
return false;
if (curA == prevB) {
// Now there are two possible cases:
// 1: prevA is the extra item added
// 2: prevA or prevB is the changed item
if (curA != curB)
return isAdd(a, b, curB);
return isAddOrChange(a, b, curB);
}
// last case: curA == preB
if (curA != curB)
return isAdd(b, a, curA);
return isAddOrChange(b, a, curA);
}
else if (a.hasNext()) { // && !b.hasNext()
curA = a.next();
return (!a.hasNext() && curA == prevB); // the second last item in
A is added
}
else if (b.hasNext()) { // && !a.hasNext()
curB = b.next();
return (!b.hasNext() && curB == prevA); // the second last item in
B is added
}
else { // the last one is different b/w A and B-> one item change
return true;
}
}
}
if (a.hasNext()) {
a.next();
return (!a.hasNext()); // the last item in A is added
}
if (b.hasNext()) {
b.next();
return (!b.hasNext()); // the last time in B is added
}
return true;
}
private boolean isSame(IntFileIterator a, IntFileIterator b) {
while (a.hasNext() && b.hasNext()) {
if (a.next() != b.next())
return false;
}
return !a.hasNext() && !b.hasNext();
}
private boolean isAdd(IntFileIterator a, IntFileIterator b, int prevB) {
if (!a.hasNext())
return false;
if (a.next() != prevB)
return false;
return isSame(a, b);
}
private boolean isAddOrChange(IntFileIterator a, IntFileIterator b, int
prevB) {
boolean isValidAddCase = true, isValidChangeCase = true
while (a.hasNext() && b.hasNext()) {
int curA = a.next();
int curB = b.next();
isValidAddCase &&= (curA == prevB);
isValidChangeCase &&= (curA == curB);
if (!isValidAddCase && !isValidChangeCase)
return false;
prevB = curB;
}
if (isValidChangeCase && !a.hasNext() && !b.hasNext())
return true; // this is the change case
if (isValidAddCase && a.hasNext()) {
int curA = a.next();
return (curA == prevB) && !a.hasNext();
}
return false;
}
}
【在 y*****e 的大作中提到】
: 在一亩三分地上看到的，听说挂了很多人。咱板上牛人多，发上来和大家讨论一下呀
: class IntFileIterator {
: boolean hasNext();
: int next();
: }
: class{
: public boolean isDistanceZeroOrOne(IntFileIterator a, IntFileIterator b)；
: }
: // return if the distance between a and b is at most 1..
: // Distance: minimum number of modifications to make a=b
| i*********7
发帖数: 348 | 22 这一题我个人的中心思想是这样的。
实际上当遇到第一个不同值的时候，会产生三个分支，插入，修改和删除。
这个时候我们就introduce四个变量。
int curA, prevA, curB, prevB
那么接下来在两边的iterator走到尽头之前我们实际上比较的就是这三个东西：
curA 和 curB ---这个是修改的分支
curA 和 prevB -- 这个是插入的分支
prevA 和 curB -- 这个是删除的分支。
我们在每一次取next的时候都同时比较这三个，当任意一个分支不成立的时候下一次
next我们就不比这个分支了。
看看任意一端iterator或者两端iterator走到尽头的时候哪个分支还活着。然后看看活
着的分支是否匹配当前的情况，譬如如果curA和curB的分支活着，那么就看看是不是两
个iterator都走到尽头了。又譬如curA和prevB的分支活着，就看看iterator_a是不是
恰好能比iterator_b多走一步。最后譬如prevA和curB的分支活着，就看看iterator_b
是不是恰好能比iterator_a多走一步。
上面三个“譬如”任意一个成真（或者说最多只有一个为真）。那么返回true，否则返
回false. 当然，如果在next过程里三个分支就全死了就可以直接过程中返回false了 | i*********7
发帖数: 348 | 23 我想我刚才说的跟你的代码的思路应该是一样的。我在打字的时候你post出来了.....
{
【在 p****e 的大作中提到】
: 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()) {
| h**********9
发帖数: 43 | 24 感觉层主分析的有道理，就是这么个思路。额外的空间复杂度也是常数级别的。赞。
【在 i*********7 的大作中提到】
: 这一题我个人的中心思想是这样的。
: 实际上当遇到第一个不同值的时候，会产生三个分支，插入，修改和删除。
: 这个时候我们就introduce四个变量。
: int curA, prevA, curB, prevB
: 那么接下来在两边的iterator走到尽头之前我们实际上比较的就是这三个东西：
: curA 和 curB ---这个是修改的分支
: curA 和 prevB -- 这个是插入的分支
: prevA 和 curB -- 这个是删除的分支。
: 我们在每一次取next的时候都同时比较这三个，当任意一个分支不成立的时候下一次
: next我们就不比这个分支了。
| a***a
发帖数: 739 | 25 This indeed can be solved by DP.
Since DP[i][j] is always false if abs(i-j) >=2
So when iterating,
there are only 3 things need to be stored: DP[i][i], DP[i+1][i], DP[i-1][i]
So this DP actually just needs 3 extra space, which is O(1). And there is no
need to backtrack; just use the two iterators to scan the files once. | d*****a
发帖数: 3 | 26 贴一下我的代码，为了测试方便，我用的是char*代替的iterator,只要不往回走，意思
应该是一样的。大牛帮忙看看有没有什么问题
bool isDistanceZeroOrOne(const char *a, const char *b)
{
bool insertA = false;
bool insertB = false;
bool replace = false;
bool diff = false;
char preA;
char preB;
while (*a != '\0' && *b != '\0')
{
if (!insertA && !insertB && !replace)
{
if (*a != *b)
{
insertA = true;
insertB = true;
replace = true;
diff = true;
}
}
else
{
if (insertA && preB != *a)
{
insertA = false;
}
if (insertB && preA != *b)
{
insertB = false;
}
if (replace && *a != *b)
{
replace = false;
}
if (!insertA && !insertB && !replace)
{
return false;
}
}
preA = *a;
preB = *b;
a++;
b++;
}
if (*a == '\0' && *b == '\0')
{
return (!diff || replace);
}
else if (*a != '\0')
{
return ((!diff || (insertA && preB == *a)) && *(a + 1) == '\0');
}
else if (*b != '\0')
{
return ((!diff || (insertB && preA == *b)) && *(b + 1) == '\0');
}
} | y*****e
发帖数: 712 | 27 这个思路太棒了！完全拜倒啊。。。。但fb店面考这个太不厚道了吧
{
【在 p****e 的大作中提到】
: 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()) {
| l*****n
发帖数: 246 | 28 第一次贴代码，错了勿怪。。。。
public boolean isDistanceZeroOrOne(IntFileIterator a, IntFileIterator b) {
int shift = 0;
while(a.hasNext() && b.hasNext()){
int aPre = a.next();
int bPre = b.next();
if(aPre!=bPre){
if(shift>0){return false;}
if(!a.hasNext() && !b.hasNext()){return true;}
if(a.hasNext() && b.hasNext()){
shift=1;
int aNext = a.next();
int bNext = b.next();
if(aNext == bNext){continue;}
if(aNext==bPre){
if(a.hasNext() && a.next()==bNext){continue;}
else{return false;}
}
if(bNext==aPre){
if(b.hasNext() && b.next()==aNext){continue;}
else{return false;}
}
}
else{return false;}
}
}
if(a.hasNext()){
if(shift>0){return false;}
a.next();
return !a.hasNext();
}
if(b.hasNext()){
if(shift>0){return false;}
b.next();
return !b.hasNext();
}
return false;
} | S*******C
发帖数: 822 | 29 你的代码测试结果
[1, 2, 3, 4, 5, 9, 8, 7, 6]
[1, 2, 3, 4, 5, 4, 8, 7, 6]
false
=====================
[1, 2, 3, 4, 5, 9, 8, 7, 6]
[1, 2, 3, 4, 5, 9, 7, 6]
false
=====================
[1, 2, 3, 4, 5, 9, 8, 7, 6]
[1, 2, 3, 4, 5, 9, 8, 7, 1, 6]
false
=====================
[1, 2, 3, 4, 5, 9, 8, 7, 6]
[1, 2, 3, 4, 5, 9, 8, 7, 6, 3, 2]
false
=====================
[1, 2, 3, 4, 5, 4, 8, 7, 6]
[1, 2, 3, 4, 5, 9, 7, 6]
false
=====================
[1, 2, 3, 4, 5, 4, 8, 7, 6]
[1, 2, 3, 4, 5, 9, 8, 7, 1, 6]
false
=====================
[1, 2, 3, 4, 5, 4, 8, 7, 6]
[1, 2, 3, 4, 5, 9, 8, 7, 6, 3, 2]
false
=====================
[1, 2, 3, 4, 5, 9, 7, 6]
[1, 2, 3, 4, 5, 9, 8, 7, 1, 6]
false
=====================
[1, 2, 3, 4, 5, 9, 7, 6]
[1, 2, 3, 4, 5, 9, 8, 7, 6, 3, 2]
false
=====================
[1, 2, 3, 4, 5, 9, 8, 7, 1, 6]
[1, 2, 3, 4, 5, 9, 8, 7, 6, 3, 2]
false
=====================
【在 l*****n 的大作中提到】
: 第一次贴代码，错了勿怪。。。。
: public boolean isDistanceZeroOrOne(IntFileIterator a, IntFileIterator b) {
: int shift = 0;
: while(a.hasNext() && b.hasNext()){
: int aPre = a.next();
: int bPre = b.next();
: if(aPre!=bPre){
: if(shift>0){return false;}
: if(!a.hasNext() && !b.hasNext()){return true;}
: if(a.hasNext() && b.hasNext()){
| S*******C
发帖数: 822 | | | | l*****n
发帖数: 246 | 31 早上起来发现最后返回不对，最后应该return true。。。所以test case的返回true的
都错了。。。最后一行return改成true，能够过这些case嚒。。
【在 S*******C 的大作中提到】
: 你的代码测试结果
: [1, 2, 3, 4, 5, 9, 8, 7, 6]
: [1, 2, 3, 4, 5, 4, 8, 7, 6]
: false
: =====================
: [1, 2, 3, 4, 5, 9, 8, 7, 6]
: [1, 2, 3, 4, 5, 9, 7, 6]
: false
: =====================
: [1, 2, 3, 4, 5, 9, 8, 7, 6]
| m*****g
发帖数: 71 | 32 画图看了一下，好像不行，感觉至少要有一条对角线的数组才够用，不过我DP菜鸟一个
，请高手指点!
【在 S*******C 的大作中提到】
: 那你写个JAVA代码，我可以给你测试
| a***a
发帖数: 739 | 33 计算的过程中不需要记住对角线上所有的历史，只需要记录对角线上前一个点以及其相
邻的2个点。
所以只需要3个变量不停迭代即可。
【在 m*****g 的大作中提到】
: 画图看了一下，好像不行，感觉至少要有一条对角线的数组才够用，不过我DP菜鸟一个
: ，请高手指点!
| w****a
发帖数: 710 | 34 bool one_dist(Iterator&& i0, Iterator&& i1) {
int dist = 0;
while(i0.has_next() || i1.has_next()) {
bool h0 = i0.has_next(), h1 = i1.has_next();
int v0 = h0 ? i0.get_next() : 0, v1 = h1 ? i1.get_next() : 0;
if(h0 && h1) {
if(v0 == v1) continue;
else {
h0 = i0.has_next(), h1 = i1.has_next();
if(!h0 && !h1) return dist == 0;
int next0 = h0 ? i0.get_next() : 0, next1 = h1 ? i1.get_next
() : 0;
if(h1 && v0 == next1) {
if(i1.has_next() && i1.get_next() != next0) return false;
} else if(h0 && v1 == next0) {
if(i0.has_next() && i0.get_next() != next1) return false;
} else if(next0 != next1){
return false;
}
}
}
if(++dist > 1) return false;
}
return true;
}
这个是完整版
http://ideone.com/dtpgr1 | S*******C
发帖数: 822 | 35 这个答案大部分test cases都对了，但是有一个test case报错
[1, 2, 3, 4, 5, 9, 7, 6]
[1, 2, 3, 4, 5, 9, 8, 7]
应该return false而不是true
能修改一下吗？
【在 w****a 的大作中提到】
: bool one_dist(Iterator&& i0, Iterator&& i1) {
: int dist = 0;
: while(i0.has_next() || i1.has_next()) {
: bool h0 = i0.has_next(), h1 = i1.has_next();
: int v0 = h0 ? i0.get_next() : 0, v1 = h1 ? i1.get_next() : 0;
: if(h0 && h1) {
: if(v0 == v1) continue;
: else {
: h0 = i0.has_next(), h1 = i1.has_next();
: if(!h0 && !h1) return dist == 0;
| w****a
发帖数: 710 | 36 回头看了下这个写法问题不少，不止你给的那个出错，我又想出好几个过不了的test
case。
试了下dotajia的那个解法，好理解也正确：
顶一个
http://ideone.com/zfAq3R
【在 S*******C 的大作中提到】
: 这个答案大部分test cases都对了，但是有一个test case报错
: [1, 2, 3, 4, 5, 9, 7, 6]
: [1, 2, 3, 4, 5, 9, 8, 7]
: 应该return false而不是true
: 能修改一下吗？
| S*******C
发帖数: 822 | 37 链接中的答案是对的
【在 w****a 的大作中提到】
: 回头看了下这个写法问题不少，不止你给的那个出错，我又想出好几个过不了的test
: case。
: 试了下dotajia的那个解法，好理解也正确：
: 顶一个
: http://ideone.com/zfAq3R
| S*******C
发帖数: 822 | 38 但能不能讲一下大意？
【在 w****a 的大作中提到】
: 回头看了下这个写法问题不少，不止你给的那个出错，我又想出好几个过不了的test
: case。
: 试了下dotajia的那个解法，好理解也正确：
: 顶一个
: http://ideone.com/zfAq3R
| y*****e
发帖数: 712 | 39 他的意思是一旦碰到两个不同的，就把可能的三种情况,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) {
boolean ins_a = false, ins_b = false, replace = false, diff =
false;
int pre_a = 0;
int pre_b = 0;
while (a.hasNext() && b.hasNext()) {
int cur_a = a.next(), cur_b = b.next();
if (!ins_a && !ins_b && !replace) {
if (cur_a != cur_b) {
ins_a = ins_b = replace = diff = true;
}
} else {
if (ins_a && pre_b != cur_a) ins_a = false;
if (ins_b && pre_a != cur_b) ins_b = false;
if (replace && cur_a != cur_b) replace = false;
if (!ins_a && !ins_b && !replace) return false;
}
pre_a = cur_a;
pre_b = cur_b;
}
if (!a.hasNext() && !b.hasNext()) {
return !diff || replace;
} else if (a.hasNext()) {
int cur_a = a.next();
return (!diff || (ins_a && pre_b == cur_a)) && !a.hasNext();
} else if (b.hasNext()) {
int cur_b = b.next();
return (!diff || (ins_b && pre_a == cur_b)) && !b.hasNext();
}
return false;
}
}
}
【在 S*******C 的大作中提到】
: 但能不能讲一下大意？
| m*****g
发帖数: 71 | 40 只用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;
if (a.hasNext() && b.hasNext()) {
prevA = a.next();
prevB = b.next();
if (prevA == prevB) {
dist = 0;
} else {
dist = 1;
}
}
while (a.hasNext() || b.hasNext()) {
diagnal = dist;
if (a.hasNext()) { // a has more numbers
currA = a.next();
up = Math.min(dist + 1, up + matchCost(currA, prevB)); //
insert into a, or match a, b
if (b.hasNext()) { //b has more numbers
currB = b.next();
left = Math.min(dist + 1, left + matchCost(currB, prevA)
); //delete head of a, or match a, b
dist = Math.min(up + 1, left + 1); //delete or insert
dist = Math.min(diagnal + matchCost(currA, currB), dist)
; //match
} else { //b is out of numbers
++left;
++dist; //delete head of a
break;
}
} else { // a is out of numbers, b has to have more numbers
currB = b.next();
left = Math.min(dist + 1, left + matchCost(currB, prevA)); /
/delete head of a, or match a, b
++up;
++dist;
break;
}
if (dist > 1 && up > 1 && left > 1) {
return false;
}
prevA = currA;
prevB = currB;
}
dist = Math.min(dist, up);
dist = Math.min(dist, left);
while (a.hasNext()) {
a.next();
++dist;
}
while (b.hasNext()) {
b.next();
++dist;
}
return dist <= 1;
} | | | m*****g
发帖数: 71 | 41 JUnit test 代码
public class SolutionTest {
@Test
public void test() {
int[] a;
int[] b;
boolean expect;
Solution s = new Solution();
//both empty
a = new int[] {};
b = new int[] {};
expect = true;
testSolution(s, a, b, expect);
//empty and 1 element
a = new int[] {};
b = new int[] {1};
expect = true;
testSolution(s, a, b, expect);
//empty and 2 element all 0s
a = new int[] {};
b = new int[] {0, 0};
expect = false;
testSolution(s, a, b, expect);
//empty and 2 element
a = new int[] {};
b = new int[] {1, 2};
expect = false;
testSolution(s, a, b, expect);
//one element and 2 elements, miss last element
a = new int[] {1};
b = new int[] {1, 2};
expect = true;
testSolution(s, a, b, expect);
//one element and 2 elements, miss first element
a = new int[] {2};
b = new int[] {1, 2};
expect = true;
testSolution(s, a, b, expect);
//one element and 2 elements, no equal elements
a = new int[] {3};
b = new int[] {1, 2};
expect = false;
testSolution(s, a, b, expect);
//different element in the middle
a = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 6};
b = new int[] {1, 2, 3, 4, 5, 4, 8, 7, 6};
expect = true;
testSolution(s, a, b, expect);
//different element in the middle, but equals next element
a = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 6};
b = new int[] {1, 2, 3, 4, 5, 8, 8, 7, 6};
expect = true;
testSolution(s, a, b, expect);
//different element at the end
a = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 6};
b = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 32};
expect = true;
testSolution(s, a, b, expect);
//different element at the end, but equals previous element
a = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 6};
b = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 7};
expect = true;
testSolution(s, a, b, expect);
//different element at the beginning, but equals next element
a = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 6};
b = new int[] {2, 2, 3, 4, 5, 9, 8, 7, 6};
expect = true;
testSolution(s, a, b, expect);
//different element at the beginning, but equals next element
a = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 6};
b = new int[] {22, 2, 3, 4, 5, 9, 8, 7, 6};
expect = true;
testSolution(s, a, b, expect);
//miss first element
a = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 6};
b = new int[] {2, 3, 4, 5, 9, 8, 7, 6};
expect = true;
testSolution(s, a, b, expect);
//miss last element
a = new int[] {1, 2, 3, 4, 5, 9, 8, 7};
b = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 6};
expect = true;
testSolution(s, a, b, expect);
//one difference and miss one
a = new int[] {1, 2, 3, 4, 5, 4, 7, 6};
b = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 6};
expect = false;
testSolution(s, a, b, expect);
//two differences and miss one
a = new int[] {1, 2, 3, 4, 5, 4, 8, 7, 1, 6};
b = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 6};
expect = false;
testSolution(s, a, b, expect);
//one difference and miss two
a = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 6};
b = new int[] {1, 2, 3, 4, 5, 4, 8, 7, 6, 3, 2};
expect = false;
testSolution(s, a, b, expect);
//miss one
a = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 6};
b = new int[] {1, 2, 3, 4, 5, 9, 7, 6};
expect = true;
testSolution(s, a, b, expect);
//miss one
a = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 6};
b = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 1, 6};
expect = true;
testSolution(s, a, b, expect);
//miss one, and equals next
a = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 6};
b = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 7, 6};
expect = true;
testSolution(s, a, b, expect);
//miss one, and equals next
a = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 7};
b = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 1, 7};
expect = true;
testSolution(s, a, b, expect);
//miss two
a = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 6};
b = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 6, 3, 2};
expect = false;
testSolution(s, a, b, expect);
//miss two
a = new int[] {1, 2, 3, 4, 5, 9, 7, 6};
b = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 1, 6};
expect = false;
testSolution(s, a, b, expect);
//miss three
a = new int[] {1, 2, 3, 4, 5, 9, 7, 6};
b = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 6, 3, 2};
expect = false;
testSolution(s, a, b, expect);
//one extra, miss two
a = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 1, 6};
b = new int[] {1, 2, 3, 4, 5, 9, 8, 7, 6, 3, 2};
expect = false;
testSolution(s, a, b, expect);
}
private void testSolution(Solution s, int[] a1, int[] b1, boolean expect
) {
IntFileIterator a = new IntFileIterator(a1);
IntFileIterator b = new IntFileIterator(b1);
a.print();
b.print();
boolean result = s.isDistanceZeroOrOne(a, b);
System.out.println("expected: " + expect + ": got: " + result);
System.out.println("");
assertEquals(expect, result);
b = new IntFileIterator(a1);
a = new IntFileIterator(b1);
a.print();
b.print();
result = s.isDistanceZeroOrOne(a, b);
System.out.println("expected: " + expect + ": got: " + result);
System.out.println("");
assertEquals(expect, result);
}
} | b***e
发帖数: 1419 | 42 我来给你试着解释一下。这个题说到底是一个有限自动机的问题。我们可以定义一下四
种状态：
0： 到目前为止A和B的字母都相同。
1： 到目前为止A和B的字母除了一个以外都相同。
2： 到目前为止A比B少一个字母，其他的都相同。
3： 到目前为止B比A少一个字母，其他的都相同。
初始状态设为S0 = {0}，因为A和B都是空，所以是相等的。下面是从S_n到S_{n+1}的转
换：
* Let S_{n+1} = {}
* If 0 is in S_n, then
- put 2 and 3 in S_{n+1}.
- If A[n] == B[n], then put 0 in S_{n+1}, otherwise put 1 in S_{n+1}
* If 1 is in S_n, then
- if A[n] == B[n], then put 1 in S_{n+1}
* If 2 is in S_n, then
- if A[n-1] == B[n], then put 2 in S_{n+1}
* If 3 is in S_n, then
- if A[n] == B[n-1], then put 3 in S_{n+1}
Any time if S_n is {} for some n, return false. Otherwise, return true
while both A and B deplete.
【在 S*******C 的大作中提到】
: 但能不能讲一下大意？
| m**6
发帖数: 47 | 43 我用C#写的，自己测试的没发现问题，
代码在这里:
http://ideone.com/AhFzEF
Test Cases:
===================
False: ab :: ba
False: a :: bb
False: aa :: bb
False: aaa :: abb
True: a :: b
True: ab :: bb
True: ab :: abb
True: abaa :: abba
True: aba :: abb
True: abaa :: abaaa
True: acaaa :: abaaa
True: ab00 :: abb0
True: ab00 :: abb00
True: ab000 :: abb00 | l****4
发帖数: 27 | 44 这个思路是对的，唯一值得讨论的地方是，我觉得三个分支不是最多只有一个可以为
true，应该是insert和delete不能同时为true，但是insert和replace，或者delete和
replace可以同时为true。比如：
{1,2,2}
{1,3,2,2}
or
{1,2,2,2}
{1,3,2,2}
【在 i*********7 的大作中提到】
: 这一题我个人的中心思想是这样的。
: 实际上当遇到第一个不同值的时候，会产生三个分支，插入，修改和删除。
: 这个时候我们就introduce四个变量。
: int curA, prevA, curB, prevB
: 那么接下来在两边的iterator走到尽头之前我们实际上比较的就是这三个东西：
: curA 和 curB ---这个是修改的分支
: curA 和 prevB -- 这个是插入的分支
: prevA 和 curB -- 这个是删除的分支。
: 我们在每一次取next的时候都同时比较这三个，当任意一个分支不成立的时候下一次
: next我们就不比这个分支了。
| p**********k
发帖数: 191 | 45 。。。我就挂在这道题了
【在 y*****e 的大作中提到】
: 在一亩三分地上看到的，听说挂了很多人。咱板上牛人多，发上来和大家讨论一下呀
: class IntFileIterator {
: boolean hasNext();
: int next();
: }
: class{
: public boolean isDistanceZeroOrOne(IntFileIterator a, IntFileIterator b)；
: }
: // return if the distance between a and b is at most 1..
: // Distance: minimum number of modifications to make a=b
| y*****e
发帖数: 712 | 46 我觉得店面问这个有点过了。。。
【在 p**********k 的大作中提到】
: 。。。我就挂在这道题了
| p**********k
发帖数: 191 | 47 我是onsite其中一轮ninja被问到的。。第一题就问我这个。。还是个国人大哥问的，
我当时给了跟第一页差不多的recursive的答案，那位国人大哥一直在皱眉头，后来我
就完全没信心了，45分钟全花这上面了。
【在 y*****e 的大作中提到】
: 我觉得店面问这个有点过了。。。
| y*****e
发帖数: 712 | 48 好可惜啊，这题没见过的话很难一下子写出漂亮简洁的代码。何况他还一直给负反馈，
肯定对自信打击蛮大的。
【在 p**********k 的大作中提到】
: 我是onsite其中一轮ninja被问到的。。第一题就问我这个。。还是个国人大哥问的，
: 我当时给了跟第一页差不多的recursive的答案，那位国人大哥一直在皱眉头，后来我
: 就完全没信心了，45分钟全花这上面了。
| p**********k
发帖数: 191 | 49 这个解法不能过这个test case吧
12121212121
2121212121
【在 i*********7 的大作中提到】
: 这一题我个人的中心思想是这样的。
: 实际上当遇到第一个不同值的时候，会产生三个分支，插入，修改和删除。
: 这个时候我们就introduce四个变量。
: int curA, prevA, curB, prevB
: 那么接下来在两边的iterator走到尽头之前我们实际上比较的就是这三个东西：
: curA 和 curB ---这个是修改的分支
: curA 和 prevB -- 这个是插入的分支
: prevA 和 curB -- 这个是删除的分支。
: 我们在每一次取next的时候都同时比较这三个，当任意一个分支不成立的时候下一次
: next我们就不比这个分支了。
| S*******C
发帖数: 822 | 50 下面答案能过所有test case，如果谁发现有错请告诉我
public boolean isDistanceZeroOrOne(IntFileIterator a, IntFileIterator b)
{
boolean ins_a = false, ins_b = false, replace = false, diff = false;
int pre_a = 0, pre_b = 0;
while (a.hasNext() && b.hasNext()) {
int cur_a = a.next(), cur_b = b.next();
if (!ins_a && !ins_b && !replace) {
if (cur_a != cur_b) {
ins_a = ins_b = replace = diff = true;
}
} else {
if (ins_a && pre_b != cur_a)
ins_a = false;
if (ins_b && pre_a != cur_b)
ins_b = false;
if (replace && cur_a != cur_b)
replace = false;
if (!ins_a && !ins_b && !replace)
return false;
}
pre_a = cur_a;
pre_b = cur_b;
}
if (!a.hasNext() && !b.hasNext()) {
return !diff || replace;
} else if (a.hasNext()) {
int cur_a = a.next();
return (!diff || (ins_a && pre_b == cur_a)) && !a.hasNext();
} else if (b.hasNext()) {
int cur_b = b.next();
return (!diff || (ins_b && pre_a == cur_b)) && !b.hasNext();
}
return true;
}
【在 p**********k 的大作中提到】
: 这个解法不能过这个test case吧
: 12121212121
: 2121212121
| | | c***3
发帖数: 10 | 51 how about this case:
A; 22221111
B:11112222 | m*****g
发帖数: 71 | 52 能过，我的DP也能过，呵呵:-)
【在 c***3 的大作中提到】
: how about this case:
: A; 22221111
: B:11112222
| b******i
发帖数: 914 | 53 看了一下这个帖子的讨论，
最后大家都推崇dotajia同学贴的方法和类似的方法。
请问第一页里面seamless的方法（复制iterator，然后分三条路走）有什么不妥？ | p*****2
发帖数: 21240 | 54 面试官肯定不想要这个解法吧？
【在 b******i 的大作中提到】
: 看了一下这个帖子的讨论，
: 最后大家都推崇dotajia同学贴的方法和类似的方法。
: 请问第一页里面seamless的方法（复制iterator，然后分三条路走）有什么不妥？
| p*****2
发帖数: 21240 | 55 dp一般是减少复杂度的吧？
【在 m*****g 的大作中提到】
: 能过，我的DP也能过，呵呵:-)
| n******n
发帖数: 12088 | 56 太长。
{
【在 p****e 的大作中提到】
: 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()) {
| j**********3
发帖数: 3211 | | l***2
发帖数: 486 | | i*****o
发帖数: 105 | 59 it works one way that when they mismatch, build a FSM with three slots,
corresponding to insert, change, skip. Then continue matching, asl long as
any of these slots match continuously until end, return 1 other wise return
0.
I think it is hard to write clean code in a shot, too many boundaries. |
|
