x*****o
发帖数: 33 | 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*****8
发帖数: 3635 | |
x*****o
发帖数: 33 | 3 多米诺骨牌可以翻转的，所以2-4和 4-2 其实是一样的。我是故意翻过来来说明这个。
【在 j*****8 的大作中提到】
: 第一个例子右边的牌上下是不是颠倒了？
|
t*********h
发帖数: 941 | 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*****o
发帖数: 33 | 5 请看这个：
http://www.amazon.com/Double-Professional-Dominoes-Spinner-Wood
就是给一个array of 这个，找是否存在两张，使得上，下的和分别是6.
【在 t*********h 的大作中提到】
: 没太看明白 就是找两个元素 一个元素的一对和另一个的一对数字配对 加起来都是6就
: 行了？
:
: if
: b
|
s******t
发帖数: 229 | 6
穷举吧。。数字也没有规律，面试考这个有什么意义
【在 t*********h 的大作中提到】
: 没太看明白 就是找两个元素 一个元素的一对和另一个的一对数字配对 加起来都是6就
: 行了？
:
: if
: b
|
l*********8
发帖数: 4642 | 7 觉得是two-sum变种
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 |
: +----+ +----+
|
b***e
发帖数: 1419 | 8 这还sum个啥，直接hashmap, 一共就36种情况。
【在 l*********8 的大作中提到】
: 觉得是two-sum变种
:
: if
: b
|
l*********8
发帖数: 4642 | 9 同意你的解法。
对于unsorted array的two-sum, 一种解法就是用hashmap.
PS. 对于本题，如不考虑上下颠倒的重复，最多有7*7=49可能性。
【在 b***e 的大作中提到】
: 这还sum个啥，直接hashmap, 一共就36种情况。
|
t*****a
发帖数: 106 | 10 Struct Card
{
int ID;
int up;
int bottom;
}
card上下颠倒了，ID不变，然后Hashmap扫一遍就行了，用ID判断是不是self-comp |
|
|
x*****o
发帖数: 33 | 11 能详细说说嘛？key和value各是什么呢？
【在 l*********8 的大作中提到】
: 同意你的解法。
: 对于unsorted array的two-sum, 一种解法就是用hashmap.
: PS. 对于本题，如不考虑上下颠倒的重复，最多有7*7=49可能性。
|
t*****a
发帖数: 106 | 12
我也想知道有没有啥好的structure.我想的是
unordered_map>;
int key只存up的value就行了。找到up匹配的再判断bottom是否匹配。
【在 x*****o 的大作中提到】
: 能详细说说嘛？key和value各是什么呢？
|
l*********8
发帖数: 4642 | 13 我觉得用hashset就可以了， key就是一个多米诺牌。
【在 x*****o 的大作中提到】
: 能详细说说嘛？key和value各是什么呢？
|
b***e
发帖数: 1419 | 14 哎，又算错了，是49个。two-sum也是对的。
【在 l*********8 的大作中提到】
: 同意你的解法。
: 对于unsorted array的two-sum, 一种解法就是用hashmap.
: PS. 对于本题，如不考虑上下颠倒的重复，最多有7*7=49可能性。
|
x*****o
发帖数: 33 | 15 可是这样的话，要先sort一下吗？不然如果有2个2-4这种是找不到的啊。。。还是每次
匹配up都要匹配一下down？
能具体说说匹配过程吗？
【在 t*****a 的大作中提到】
:
: 我也想知道有没有啥好的structure.我想的是
: unordered_map>;
: int key只存up的value就行了。找到up匹配的再判断bottom是否匹配。
|
x*****o
发帖数: 33 | 16 想不太明白用set怎么做。。能具体说说过程吗？
【在 l*********8 的大作中提到】
: 我觉得用hashset就可以了， key就是一个多米诺牌。
|
z*********e
发帖数: 10149 | 17 你每次找到一个骨牌，可以把他的complementary加到hashset里面，然后拿到新的骨牌
就看在不在这个hashset里，如果在就找到了，如果没有，那就把新的骨牌的
complementary也push到hashset里面去。这个set可以加个限定条件，比如上面的数字
小于等于下面的数字
就是two sum的做法吧
【在 x*****o 的大作中提到】
: 想不太明白用set怎么做。。能具体说说过程吗？
|
t*****a
发帖数: 106 | 18
首先你要把每个骨牌做一个copy, id一样，但上下颠倒。你说的两个2-4最后是两个2-4
,两个4-2的copy，但ID只有两个。不用sort啊，你拿到一个up,直接找对应的(6-up)的
hash item，然后再匹配down就行了。要是再想快就建立成unordered_map
unordered_map>，不过感觉没必要。
直接用unordered_set好一些
【在 x*****o 的大作中提到】
: 可是这样的话，要先sort一下吗？不然如果有2个2-4这种是找不到的啊。。。还是每次
: 匹配up都要匹配一下down？
: 能具体说说匹配过程吗？
|
f**********t
发帖数: 1001 | 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 的大作中提到】
: 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 |
: +----+ +----+
|
n**s
发帖数: 2230 | 20 就是简单的hashset。
用0-6作为key，0和6, 1和5，2和4，3和3配对即可 |
