Google Phone Interview

条件1很容易check

条件2和3加在一起，就是楼上说的1， 以及每轮都必须有floor(n/2)对，而且每对只出现一次

但是一开始是否知道总的比赛人数？

如果不知道的话要读到最后才知道，那还得回头去check一次

或者像前面说的那样最后check每个player是否都跟其他对局过。

echo33 发表于 2016-1-13 01:25
条件1很容易check

条件2和3加在一起，就是楼上说的1， 以及每轮都必须有floor(n/2)对，而且每对只出现一 ...

我猜应该知道n，不然如果有一个人没有比赛，那么不知道是否valid. 比如n=3个人，却只有round: B-C，你没法从round看出来

大家好啊，不好意思来晚了。具体实现的时候当时时间不够了，没想到怎么把三个条件组合起来设计一个刁刁的数据结构，是一个个check的。
第一个就是以建一个map1,以round为key,value 是一个set, 把每个round的player加进set, 重复了return false
第二个和第一个差不多建立map2，以player为key
第三个 是比较map1和map2的size

这题做的不是很好，其实不难，但是当时有点慌，电话接起来以后就等着面two sum了，真是那义务啊，大家加油！！！

ninacc 发表于 2016-1-13 10:56
大家好啊，不好意思来晚了。具体实现的时候当时时间不够了，没想到怎么把三个条件组合起来设计一个刁刁的数 ...

LZ 能说说为什么用map1 map2 size 的比较就能知道rule3吗?

starcroce 发表于 2016-1-12 15:19
round数少于n-1直接false
建hash table，key是player1，value是set of player2
对于每个round，把a-b这样 ...

怎么知道是最少的呢？

nothingtrouble 发表于 2016-1-13 00:32
觉得考点主要是:

1. min number of rounds. 如果是n is odd, min = n, otherwise(n is even) min = n- ...

如何能证明n是基数时，min = n， 偶数时 min=n-1 ?

最少round数是要自己根据是数学关系总结出来吗

zoufengboy 发表于 2016-1-25 12:21
如何能证明n是基数时，min = n， 偶数时 min=n-1 ?

每轮只能打一个对手，要全打过，所以是n-1，当是基数时，会有一个人轮空，所以要多加一轮

pawprinter 发表于 2016-8-17 11:02
每轮只能打一个对手，要全打过，所以是n-1，当是基数时，会有一个人轮空，所以要多加一轮

如何证明一定可达呢？

william_gong 发表于 2016-8-17 13:49
如何证明一定可达呢？

偶数个人，一共 n * (n - 1) / 2场比赛，n为偶数时每轮 n / 2场，那么一共n - 1轮。如果是奇数，每轮 (n - 1) / 2场，一共n轮。

补充内容 (2016-8-17 13:57):
前面的偶数个人去掉，打多了