h****p
发帖数: 87 | 1 Write a class DominoChecker that has a method called addBox(int[]) that
takes a box of five dominoes,
described as a list of 10 integers (explained after), adds it to a
collection,
and returns true if a box with the same dominoes was already in the
collection and false otherwise.
A box of dominoes is encoded as a list of 10 integers from 0 to 9, where a
pair of numbers represent a domino.
For example: 0,2,9,1,3,3,7,4,5,6 represents a box containing dominoes: (0,2)
; (9,1); (3,3); (7,4); (5,6).
注意： （1）对于domino（0,2）和（2,0）是一样的.
（2） addBox的时候需要track以前添加的box
DominoChecker checker = new DominoChecker(???? up to you ???);
checker.addBox("1234567811"); // returns false
checker.addBox("1233445566"); // returns false
checker.addBox("1233445566"); // returns true;
checker.addBox("3344556612"); // returns true;
checker.addBox("3344556621"); // returns true;
请教大家有什么好的思路 |
f*******t
发帖数: 7549 | |
h****p
发帖数: 87 | 3 不行吧，里面每个domino（pair of integer）的次序可以不一样啊
【在 f*******t 的大作中提到】
: HashSet?
|
f*******t
发帖数: 7549 | |
c****p
发帖数: 6474 | 5 弄成有序的再hash。
【在 h****p 的大作中提到】
: 不行吧，里面每个domino（pair of integer）的次序可以不一样啊
|
h****p
发帖数: 87 | 6 我当时就是把每个box的每个domino的两个数弄成有序，然后根据每个domino的第一个
数再对整个box排序，然后hash
不知道有没有更好的方法
【在 c****p 的大作中提到】
: 弄成有序的再hash。
|
c****p
发帖数: 6474 | 7 时间复杂度O(N)，空间复杂度O(N)，
至少是接近最优的了吧。。
【在 h****p 的大作中提到】
: 我当时就是把每个box的每个domino的两个数弄成有序，然后根据每个domino的第一个
: 数再对整个box排序，然后hash
: 不知道有没有更好的方法
|
p*****2
发帖数: 21240 | 8
我看到也是这个思路。一共就10个整数，排序还是很快的。感觉再优意义也不大了吧？
【在 h****p 的大作中提到】
: 我当时就是把每个box的每个domino的两个数弄成有序，然后根据每个domino的第一个
: 数再对整个box排序，然后hash
: 不知道有没有更好的方法
|
h****p
发帖数: 87 | 9 是的，我当时也是这么感觉，这题太非主流了。。解释这题就解释了半天。。
【在 p*****2 的大作中提到】
:
: 我看到也是这个思路。一共就10个整数，排序还是很快的。感觉再优意义也不大了吧？
|
h****p
发帖数: 87 | 10 请教二爷后面那个根据第一个数的排序怎么做比较好？
【在 p*****2 的大作中提到】
:
: 我看到也是这个思路。一共就10个整数，排序还是很快的。感觉再优意义也不大了吧？
|
|
|
s*****n
发帖数: 5488 | 11 用long表示box. 每4位代表一个点. little eudian
前6个hex保留 00 00 00 56 74 33 91 02 表示 (0,2) (9,1); (3,3); (7,4); (5,6).
add的时候
1. sort成标准型
2. 检查输入是否正确
3. 查重复的box简单long比较
2)
【在 h****p 的大作中提到】
: Write a class DominoChecker that has a method called addBox(int[]) that
: takes a box of five dominoes,
: described as a list of 10 integers (explained after), adds it to a
: collection,
: and returns true if a box with the same dominoes was already in the
: collection and false otherwise.
: A box of dominoes is encoded as a list of 10 integers from 0 to 9, where a
: pair of numbers represent a domino.
: For example: 0,2,9,1,3,3,7,4,5,6 represents a box containing dominoes: (0,2)
: ; (9,1); (3,3); (7,4); (5,6).
|
d****n
发帖数: 233 | 12 I guess you can maintain a 10 x 10 2D lookup table and solve it like this.
checker.addBox(int []points)
{
bool found = true;
for(int I = 0; I < 10; I+=2)
{
if (!table[points[I]][points[I+1]] && !table[points[I+1]][points[I]])
{
found = false;
break;
}
}
for(int I = 0; I < 10; I+=2)
{
table[points[I]][points[I+1]] = true;
table[points[I+1]][points[I]] = true;
}
return found;
}
【在 s*****n 的大作中提到】
: 用long表示box. 每4位代表一个点. little eudian
: 前6个hex保留 00 00 00 56 74 33 91 02 表示 (0,2) (9,1); (3,3); (7,4); (5,6).
: add的时候
: 1. sort成标准型
: 2. 检查输入是否正确
: 3. 查重复的box简单long比较
:
: 2)
|
h*******0
发帖数: 270 | 13 如果还需要把box取出呢？ 是不是把true 和false换成数字会好一些？ 不过这个方法
真好！
【在 d****n 的大作中提到】
: I guess you can maintain a 10 x 10 2D lookup table and solve it like this.
: checker.addBox(int []points)
: {
: bool found = true;
: for(int I = 0; I < 10; I+=2)
: {
: if (!table[points[I]][points[I+1]] && !table[points[I+1]][points[I]])
: {
: found = false;
: break;
|
h****p
发帖数: 87 | 14 照你的思路每加一个box就得maintain一个table，box多了你怎么办？
【在 d****n 的大作中提到】
: I guess you can maintain a 10 x 10 2D lookup table and solve it like this.
: checker.addBox(int []points)
: {
: bool found = true;
: for(int I = 0; I < 10; I+=2)
: {
: if (!table[points[I]][points[I+1]] && !table[points[I+1]][points[I]])
: {
: found = false;
: break;
|
d****n
发帖数: 233 | 15 There should be only one table, it can be global or class member.
【在 h****p 的大作中提到】
: 照你的思路每加一个box就得maintain一个table，box多了你怎么办？
|
h*******0
发帖数: 270 | 16 这样貌似不行。。 例如，原来有boxes［12，34，14，78，90］，［15，16，56，18，
19］， 再插入［12，34，56，78，90］的时候就会错误的返回true
【在 d****n 的大作中提到】
: There should be only one table, it can be global or class member.
|
d****n
发帖数: 233 | 17 hmm, didn't know the same dominos have to be in same box.
【在 h*******0 的大作中提到】
: 这样貌似不行。。 例如，原来有boxes［12，34，14，78，90］，［15，16，56，18，
: 19］， 再插入［12，34，56，78，90］的时候就会错误的返回true
|
