发道面试题求大牛帮解答 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

发道面试题求大牛帮解答

发道面试题求大牛帮解答# JobHunting - 待字闺中

x*o2014-03-04 08:03

1 楼

Find the complement domino pairs.
多米诺骨牌由2个数字构成，每个数字可以是0-6. 给定an array of Dominos, find if
there are two complement dominos. Complement dominos是说两个多米诺骨牌a和b
。a的上半部分的数字和b的上半部分的数字相加是6，a的下半部分的数字和b的下半部
分的数字相加也是6。多米诺骨牌可以翻转。
举个例子，
+----+ +----+
| x | | x x |
| x x | | x x |
+----+ +----+
| x | | x |
| x | | x x |
+----+ +----+
是complement dominos，
+----+ +----+
| x x | | |
| x x | | |
+----+ +----+
| x | |x x x |
| x | |x x x |
+----+ +----+
以上每一个和自身都是complementory，但是在上面的题中，IFF array里面有2个一样
的才算。
请大牛赐教用什么data structure表示domino，然后怎么找complement。多谢啦！！

j*82014-03-04 08:03

2 楼

第一个例子右边的牌上下是不是颠倒了？

x*o2014-03-04 08:03

3 楼

多米诺骨牌可以翻转的，所以2-4和 4-2 其实是一样的。我是故意翻过来来说明这个。

【在 j*****8 的大作中提到】

: 第一个例子右边的牌上下是不是颠倒了？

t*h2014-03-04 08:03

4 楼

没太看明白就是找两个元素一个元素的一对和另一个的一对数字配对加起来都是6就
行了？

if
b

【在 x*****o 的大作中提到】

: Find the complement domino pairs.
: 多米诺骨牌由2个数字构成，每个数字可以是0-6. 给定an array of Dominos, find if
: there are two complement dominos. Complement dominos是说两个多米诺骨牌a和b
: 。a的上半部分的数字和b的上半部分的数字相加是6，a的下半部分的数字和b的下半部
: 分的数字相加也是6。多米诺骨牌可以翻转。
: 举个例子，
: +----+ +----+
: | x | | x x |
: | x x | | x x |
: +----+ +----+

x*o2014-03-04 08:03

5 楼

请看这个：
http://www.amazon.com/Double-Professional-Dominoes-Spinner-Wood
就是给一个array of 这个，找是否存在两张，使得上，下的和分别是6.

【在 t*********h 的大作中提到】

: 没太看明白就是找两个元素一个元素的一对和另一个的一对数字配对加起来都是6就
: 行了？
:
: if
: b

s*t2014-03-04 08:03

6 楼

穷举吧。。数字也没有规律，面试考这个有什么意义

【在 t*********h 的大作中提到】

: 没太看明白就是找两个元素一个元素的一对和另一个的一对数字配对加起来都是6就
: 行了？
:
: if
: b

l*82014-03-04 08:03

7 楼

觉得是two-sum变种

if
b

【在 x*****o 的大作中提到】

b*e2014-03-04 08:03

8 楼

这还sum个啥，直接hashmap, 一共就36种情况。

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

: 觉得是two-sum变种
:
: if
: b

l*82014-03-04 08:03

9 楼

同意你的解法。
对于unsorted array的two-sum, 一种解法就是用hashmap.
PS. 对于本题，如不考虑上下颠倒的重复，最多有7*7=49可能性。

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

: 这还sum个啥，直接hashmap, 一共就36种情况。

t*a2014-03-04 08:03

10 楼

Struct Card
{
int ID;
int up;
int bottom;
}
card上下颠倒了，ID不变，然后Hashmap扫一遍就行了，用ID判断是不是self-comp

x*o2014-03-04 08:03

11 楼

能详细说说嘛？key和value各是什么呢？

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

: 同意你的解法。
: 对于unsorted array的two-sum, 一种解法就是用hashmap.
: PS. 对于本题，如不考虑上下颠倒的重复，最多有7*7=49可能性。

t*a2014-03-04 08:03

12 楼

我也想知道有没有啥好的structure.我想的是
unordered_map>;
int key只存up的value就行了。找到up匹配的再判断bottom是否匹配。

【在 x*****o 的大作中提到】

: 能详细说说嘛？key和value各是什么呢？

l*82014-03-04 08:03

13 楼

我觉得用hashset就可以了， key就是一个多米诺牌。

【在 x*****o 的大作中提到】

: 能详细说说嘛？key和value各是什么呢？

b*e2014-03-04 08:03

14 楼

哎，又算错了，是49个。two-sum也是对的。

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

: 同意你的解法。
: 对于unsorted array的two-sum, 一种解法就是用hashmap.
: PS. 对于本题，如不考虑上下颠倒的重复，最多有7*7=49可能性。

x*o2014-03-04 08:03

15 楼

可是这样的话，要先sort一下吗？不然如果有2个2-4这种是找不到的啊。。。还是每次
匹配up都要匹配一下down？
能具体说说匹配过程吗？

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

:
: 我也想知道有没有啥好的structure.我想的是
: unordered_map>;
: int key只存up的value就行了。找到up匹配的再判断bottom是否匹配。

x*o2014-03-04 08:03

16 楼

想不太明白用set怎么做。。能具体说说过程吗？

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

: 我觉得用hashset就可以了， key就是一个多米诺牌。

z*e2014-03-04 08:03

17 楼

你每次找到一个骨牌，可以把他的complementary加到hashset里面，然后拿到新的骨牌
就看在不在这个hashset里，如果在就找到了，如果没有，那就把新的骨牌的
complementary也push到hashset里面去。这个set可以加个限定条件，比如上面的数字
小于等于下面的数字
就是two sum的做法吧

【在 x*****o 的大作中提到】

: 想不太明白用set怎么做。。能具体说说过程吗？

t*a2014-03-04 08:03

18 楼

首先你要把每个骨牌做一个copy, id一样，但上下颠倒。你说的两个2-4最后是两个2-4
,两个4-2的copy，但ID只有两个。不用sort啊，你拿到一个up,直接找对应的(6-up)的
hash item，然后再匹配down就行了。要是再想快就建立成unordered_mapunordered_map>，不过感觉没必要。
直接用unordered_set好一些

【在 x*****o 的大作中提到】

: 可是这样的话，要先sort一下吗？不然如果有2个2-4这种是找不到的啊。。。还是每次
: 匹配up都要匹配一下down？
: 能具体说说匹配过程吗？

f*t2014-03-04 08:03

19 楼

vector> dominos;
unordered_map> seen;
for (auto pr : dominos) {
if (seen.find(6 - pr->first) != seen.end() &&
seen[6 - pr->first].find(6 - pr->second) != seen[6 - pr->first].end() ||
seen.find(6 - pr->second) != seen.end() &&
seen[6 - pr->second].find(6 - pr->first) != seen[6 - pr->second].end())
{
return true;
}//if
seen[pr->second].insert(pr->first);
seen[pr->first].insert(pr->second);
}

if
b

【在 x*****o 的大作中提到】

n*s2014-03-04 08:03

20 楼

就是简单的hashset。
用0-6作为key，0和6, 1和5，2和4，3和3配对即可