I********y
发帖数: 228 | 1 给一个int的数组parties，每一个element也就是每一个party代表一组玩家，比如
parties[0]是3，代表这个party有3个玩家。然后给一个一场多人游戏最多可以容纳的
玩家数量的值maxHopperSize，要求从这个数组中选任意多party加和组成一个Hopper，
加和的玩家总数要满足小于等于maxHopperSize。然后同时给一个hopper的数目
hopperCount，问是否可以fill所有的玩家到给定数目的Hoppers。
所以方法的签名是：
bool(int[] parties, int maxHopperSize, int hopperCount)
比如parties是[2,3,2,4,3], maxHopperSize是8，hopperCount是2.那么返回的就是
true。
而如果parties是[3,3,3,1,2], maxHopperSize是4，hopperCount是3，那么返回就是
false。 | N******G
发帖数: 33 | 2 只能搜，如果hoppercount不大（比如2、3）可以动态规划，但是复杂度是
maxHoppersize^hopperCount
本身这题是NP完全的，因为假设存在多项式算法，那么下面这个问题可解：
给定N个数，是否可以分两组，使得和一样
maxHopperSize=SUM/2
hopperCount=2
而这个partition problem是NP完全的
https://en.wikipedia.org/wiki/Partition_problem | h**p
发帖数: 211 | 3 combination sum的变种？加了额外条件是
#1 sum可以是 <= maxsum
#2 和数字的个数？
记得见过fb的面试，有一题类似 | I********y
发帖数: 228 | 4 hopperCount可以很大，
谁能给写个code看看。 | t*********r
发帖数: 845 | 5 可以先排序，然后对排在最前(或者最后的)count个element求和？ | c*******7
发帖数: 438 | 6 感觉类似内存chunk的分配，每个64 bit 的word占8个byte，等于说每个坑的大小是8，
然后总共有N个坑，问给你一堆东西能否塞进这N个坑，前提是同一个东西不能跨两个坑。
不知道这样能不能行，party从大到小排序。hopper按剩余空间做index(hash table)
和 max heap。
对于每下一个party，如果能找到正好可以完全占满的hopper，放进去，不然就放入当
前最大的hopper里。update hopper的hash table和heap。直至结束。
比如parties是[2,3,2,4,3], maxHopperSize是8，hopperCount是2.那么返回的就是
true。
party: 4 3 3 2 2
hopper: 8 8
hopper依序变成 4 8 # 4 5 # 4 2 # 4 0 # 2 0#
而如果parties是[3,3,3,1,2], maxHopperSize是4，hopperCount是3，那么返回就是
false。
party: 3 3 3 2 1
hopper: 4 4 4
hopper依序变成 1 4 4 # 1 1 4 # 1 1 1 # 遇到2 fail。 | v*****u
发帖数: 1796 | 7 反例： 5 5 3 3 3
maxHopperSize 10
hopperCount 2
坑。
【在 c*******7 的大作中提到】
: 感觉类似内存chunk的分配，每个64 bit 的word占8个byte，等于说每个坑的大小是8，
: 然后总共有N个坑，问给你一堆东西能否塞进这N个坑，前提是同一个东西不能跨两个坑。
: 不知道这样能不能行，party从大到小排序。hopper按剩余空间做index(hash table)
: 和 max heap。
: 对于每下一个party，如果能找到正好可以完全占满的hopper，放进去，不然就放入当
: 前最大的hopper里。update hopper的hash table和heap。直至结束。
: 比如parties是[2,3,2,4,3], maxHopperSize是8，hopperCount是2.那么返回的就是
: true。
: party: 4 3 3 2 2
: hopper: 8 8
| I********y
发帖数: 228 | 8 这题在leetcode里，够格算hard的不？
[在 NewmanGG (小胖) 的大作中提到：]
：只能搜，如果hoppercount不大（比如2、3）可以动态规划，但是复杂度是
：maxHoppersize^hopperCount
：........... | m**********g
发帖数: 199 | 9 都NPC了， 放哪儿也是最难的问题了啊.
【在 I********y 的大作中提到】
: 这题在leetcode里，够格算hard的不？
: [在 NewmanGG (小胖) 的大作中提到：]
: ：只能搜，如果hoppercount不大（比如2、3）可以动态规划，但是复杂度是
: ：maxHoppersize^hopperCount
: ：...........
| j**********3
发帖数: 3211 | |
|
