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 | |
|