【虎年奔宝宝】小圆辞旧迎新给大家拜年啦！ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>NextGeneration - 我爱宝宝

【虎年奔宝宝】小圆辞旧迎新给大家拜年啦！

【虎年奔宝宝】小圆辞旧迎新给大家拜年啦！# NextGeneration - 我爱宝宝

g*r2010-02-08 08:02

1 楼

given "foo", "app"; returns true we can map f -> a and o->p
given "bar", "foo"; returns false we can't map both 'a' and 'r' to 'o'
given "ab", "ca"; returns true we can map 'a' -> 'b' and 'c' -> 'a'
记得lolhaha大牛说过一个hashmap的解法，具体怎么做呢？

y*92010-02-08 08:02

2 楼

倪萍大姑妈深情地播报春晚经典贺卡：各位港澳同胞，海外侨胞，海外游子留学生朋友们，每逢佳节倍思亲，值此新春佳节，我们收到了来自大洋彼岸出生仅4个月的圆圆小朋友发来的电子贺卡，今年是圆圆生命中第一次过春节，虽然远在异国他乡，但是圆圆努力地向爸爸妈妈学习祖国传统文化，和爸爸妈妈一起欢度虎年新春，看。。。。小圆给大家拜年来啦！
先作揖拜一拜爸爸妈妈准爸爸准妈妈叔叔阿姨！恭贺新春！
再拜一拜哥哥姐姐弟弟妹妹（妈妈！我已经换好衣服准备跳舞了）
好吧，接着让我来为大家跳个新春泼水舞
最后，祝买买提宝宝版的爸爸妈妈准爸爸准妈妈叔叔阿姨哥哥姐姐弟弟妹妹新春愉快！万事如意！团团圆圆！

l*a2010-02-08 08:02

3 楼

对于第一个例子
你把f>a a->f都存进去就可以了吧

【在 g********r 的大作中提到】

: given "foo", "app"; returns true we can map f -> a and o->p
: given "bar", "foo"; returns false we can't map both 'a' and 'r' to 'o'
: given "ab", "ca"; returns true we can map 'a' -> 'b' and 'c' -> 'a'
: 记得lolhaha大牛说过一个hashmap的解法，具体怎么做呢？

g*r2010-02-08 08:02

4 楼

"ab", "ca"怎么做呢？
比如第一个char结束后, mp[a] = c, mp[c]=a
然后到了第二个char, 不知道怎么判断了

【在 l*****a 的大作中提到】

: 对于第一个例子
: 你把f>a a->f都存进去就可以了吧

l*a2010-02-08 08:02

5 楼

这个自己想得出来吧
第二个char期待 map[a]=b and map[b]=a
跟现有map conflict了吧

【在 g********r 的大作中提到】

: "ab", "ca"怎么做呢？
: 比如第一个char结束后, mp[a] = c, mp[c]=a
: 然后到了第二个char, 不知道怎么判断了

g*r2010-02-08 08:02

6 楼

不是吧
"ab" "ca"是同构的啊

【在 l*****a 的大作中提到】

: 这个自己想得出来吧
: 第二个char期待 map[a]=b and map[b]=a
: 跟现有map conflict了吧

p*22010-02-08 08:02

7 楼

def isomorphicString(s1:String, s2:String) = {
val f = (s1:String, s2:String) => s1.zip(s2).groupBy(_._1).map(_._2.
toSet).forall(_.size==1)
f(s1,s2) && f(s2,s1)
}

v*a2010-02-08 08:02

8 楼

public static boolean isIsomorphic(String inputString1, String inputString2)
{
int length1 = inputString1.length();
int length2 = inputString2.length();
if (length1 != length2) {
return false;
}
if (length1 == 1) {
return true;
}
Map map = new HashMap();
for (int i = 0; i < length1; i++) {
if (!map.containsKey(inputString1.charAt(i)) && !map.
containsValue(inputString2.charAt(i))) {
map.put(inputString1.charAt(i), inputString2.charAt(i));
}
if (map.get(inputString1.charAt(i)) == null) {
return false;
}
if (!map.get(inputString1.charAt(i)).equals(inputString2.charAt(
i))) {
return false;
}
}
return true;
}

g*r2010-02-08 08:02

9 楼

多谢大牛！可惜俺对java的contains之类的用法不太了解，大牛能讲一下"ab" "ca"在
这段code里面怎么运行的吗？多谢了！

inputString2)

【在 v****a 的大作中提到】

: public static boolean isIsomorphic(String inputString1, String inputString2)
: {
: int length1 = inputString1.length();
: int length2 = inputString2.length();
: if (length1 != length2) {
: return false;
: }
: if (length1 == 1) {
: return true;
: }

s*i2010-02-08 08:02

10 楼

很不幸的是containsValue是O（n），
所以最终的算法复杂度是O(n^2)

inputString2)

【在 v****a 的大作中提到】

r*72010-02-08 08:02

11 楼

怎么定义是“单Hashmap”?
一个Hashmap用完一次清空再重新用算么？

【在 g********r 的大作中提到】

l*a2010-02-08 08:02

12 楼

这code真的work吗？

inputString2)

【在 v****a 的大作中提到】

l*a2010-02-08 08:02

13 楼

try bcb ood

【在 l*****a 的大作中提到】

: 这code真的work吗？
:
: inputString2)

v*a2010-02-08 08:02

14 楼

这个是false吧？
我也发现containsValue 不是O(1)了。。不知道怎么写是单HashMap的O(N)

【在 l*******a 的大作中提到】

: try bcb ood

w*e2010-02-08 08:02

15 楼

char [] a="abcd".toCharArray();
char [] b="pqap".toCharArray();
int i=0;
boolean TF=true;
HashMap h1=new HashMap();
HashMap h2=new HashMap();
for (i=0;i< a.length; i ++){
if (
( h1.containsKey(a[i]) && (h1.get(a[i]).compareTo(b[i])!=0) ) ||
( h2.containsKey(b[i]) && (h2.get(b[i]).compareTo(a[i])!=0) )
){
TF=false;
}else{
h1.put(a[i],b[i]);
h2.put(b[i],a[i]);
}

}
System.out.println(TF);

i*e2010-02-08 08:02

16 楼

一个hashmap两个hashmap的解法区别在哪里？空间复杂度吗？一个是n,另一个是2n,不
过都是O(n).
如果非要一个hashmap，那就在每个字符的前面加个特殊符号来表示左映射或者右映射
，比如：
b --> o
{">b" : "o",
"在判断
bcb --> ood
就会第二个字母发现问题，因为 "{">b" : "o",
"">c": "o"}

l*a2010-02-08 08:02

17 楼

你想多了
直接b->a ,a->b同时放map就好

【在 i*****e 的大作中提到】

: 一个hashmap两个hashmap的解法区别在哪里？空间复杂度吗？一个是n,另一个是2n,不
: 过都是O(n).
: 如果非要一个hashmap，那就在每个字符的前面加个特殊符号来表示左映射或者右映射
: ，比如：
: b --> o
: {">b" : "o",
: ": 在判断
: bcb --> ood
: 就会第二个字母发现问题，因为 "

i*e2010-02-08 08:02

18 楼

确定这样行吗？
比如 ba ac

【在 l*****a 的大作中提到】

: 你想多了
: 直接b->a ,a->b同时放map就好

w*e2010-02-08 08:02

19 楼

原來不行呀，害我改了....

【在 i*****e 的大作中提到】

: 确定这样行吗？
: 比如 ba ac

l*a2010-02-08 08:02

20 楼

题目第三个case是错误的
since u already have b map to a(which means a map to b as well),
how u can map a to c?

【在 i*****e 的大作中提到】

: 确定这样行吗？
: 比如 ba ac

w*e2010-02-08 08:02

21 楼

So, this question is not clear.
if this is a mapping between 2 languages or for Cryptology, then the mapping
is directional, and the case 大饼 mentioned is valid.

l*a2010-02-08 08:02

22 楼

then why below is false?
given "bar", "foo"; returns false we can't map both 'a' and 'r' to 'o'

mapping

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

: So, this question is not clear.
: if this is a mapping between 2 languages or for Cryptology, then the mapping
: is directional, and the case 大饼 mentioned is valid.

s*l2010-02-08 08:02

23 楼

b map to a 不一定 means a map to b as well把~

【在 l*****a 的大作中提到】

: 题目第三个case是错误的
: since u already have b map to a(which means a map to b as well),
: how u can map a to c?

g*r2010-02-08 08:02

24 楼

是啊，我也觉得“同构”是说结构相同，比如abc和bca是同构的

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

: b map to a 不一定 means a map to b as well把~

l*a2010-02-08 08:02

25 楼

那你仔细学学wiki吧。

【在 g********r 的大作中提到】

: 是啊，我也觉得“同构”是说结构相同，比如abc和bca是同构的

s*l2010-02-08 08:02

26 楼

我search了一圈都给了那个例子难道都错了？
你查的谁家wiki啊我怎么没看到？

【在 l*****a 的大作中提到】

: 那你仔细学学wiki吧。

l*a2010-02-08 08:02

27 楼

you should confirm with interviewer
按照你的理论,能否解释一下为什么下面那个return true
while the first return false
given "bar", "foo"; returns false we can't map both 'a' and 'r' to 'o'
given "ab", "ca"; returns true we can map 'a' -> 'b' and 'c' -> 'a'

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

: 我search了一圈都给了那个例子难道都错了？
: 你查的谁家wiki啊我怎么没看到？

s*l2010-02-08 08:02

28 楼

第一个 a->o r ->o 所以false
第二个 a->b c->a true (if a->c 那就是false)
我记得在哪里见过着这样的错位编码是单向不是双向的~

【在 l*****a 的大作中提到】

: you should confirm with interviewer
: 按照你的理论,能否解释一下为什么下面那个return true
: while the first return false
: given "bar", "foo"; returns false we can't map both 'a' and 'r' to 'o'
: given "ab", "ca"; returns true we can map 'a' -> 'b' and 'c' -> 'a'

l*a2010-02-08 08:02

29 楼

需求请问面试官
我看到的一个领英面经是这么写的:
1. Return if two strings are isomorphic. (character 1-1 match)
“zoo” -> “fee” ( z->f, o->e) true
“zoo” -> “dui” ( z->d, o->u, o-> ) false
“dui” -> “zoo” (d->z, u->o, i-> ) false
1. Return if two strings are isomorphic. (character 1-1 match)

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

: 第一个 a->o r ->o 所以false
: 第二个 a->b c->a true (if a->c 那就是false)
: 我记得在哪里见过着这样的错位编码是单向不是双向的~

u*x2010-02-08 08:02

30 楼

How about this?
return singleDirection(str1, str2) && singleDirection(str2, str1);
singleDirection returns false if the same char in the 1st arg maps to two
different chars in the 2nd arg, which is easy to code.

【在 g********r 的大作中提到】