最方便的寓所

Lunluen 发表于 2019/03/31 02:19:45


有个test case错了
应该是5
[mw_shl_code=python,true]    def test_3(self):
        street = [
         ...

应该不是错了，而是题目定义不同，这题有的面经要求是distance sum最小，有的面经要求是到最远的requirement 最小，稍微看了下你的码，应该是用distance sum的问法，我的solution 是解是到最远最短的问法，distance sum 答案最小要给5，最远最小就是4了

neozhang9233 发表于 2019-3-29 09:20
粘一个个人的答案，无论是求距离和还是最远都可以用这个方法，速度为O（nk），k为requires项数。

[mw_sh ...

有个问题和楼主讨论下。假设n是block的数量，先不说createMap的复杂度，就算是或者可以优化成nk吧。
第二步找最小距离的时候，两个for loop就是nk复杂度，寻找单个required的最小距离复杂度worse case也是n啊。所以worse case O(kn^2)? （比方说每个block都有所有的required facility。）

先做个 req->block#的mapping，
然后再来就每次找离得最近的req在哪儿就行了。因为我们只考虑1.靠左最近的 2.靠右最近的。所以每次遇到第二个小于当前block #的index把最前面的那个index就pop出去。然后每次是常数项查询。
最后的timecomplexity 大概是 o(n*k*2) -> o(n*k)

1. from collections import defaultdict
   
2. from collections import deque
   
3. def xuangongyu(street,requirement):
   
4.     reqset = set(requirement)
   
5.     map_a_s = defaultdict(deque)
   
6.     for i,block in enumerate(street):
   
7.         for item in block:
   
8.             if item in reqset:
   
9.                 map_a_s[item].append(i)
   
10.     print(map_a_s)
    
11.     res = []
    
12.     globalmin = len(street)
    
13.     for i,block in enumerate(street):
    
14.         localmax = 0
    
15.         for item in reqset:
    
16.             print(map_a_s)
    
17.             popflag = False
    
18.             itemmin = len(street)
    
19.             for ri,v in enumerate(map_a_s[item]):
    
20.                 itemmin = min(itemmin,abs(i-v))
    
21.                 if v <= i and ri != 0:
    
22.                     popflag = True
    
23.                 elif v > i:
    
24.                     break
    
25.             if popflag: map_a_s[item].popleft()
    
26.             localmax = max(itemmin,localmax)
    
27.         if localmax < globalmin:
    
28.             res = [street[i]]
    
29.         elif localmax == globalmin:
    
30.             res.append(street[i])
    
31.         globalmin = min(globalmin,localmax)
    
32.     return globalmin,res

复制代码

neozhang9233 发表于 2019-3-29 09:20
粘一个个人的答案，无论是求距离和还是最远都可以用这个方法，速度为O（nk），k为requires项数。

[mw_sh ...

这个方法复杂度是不止O(nk)哦，因为求getMinLen不是O(1)

umialpha 发表于 2019-4-3 10:22
这个方法复杂度是不止O(nk)哦，因为求getMinLen不是O(1)

getMinLen()的速度取决于requires在road上的平均数量，我当时说因为在真是的例子里，也不可能一条街每栋房子都是麦当劳，就把他近似看成1了，细究起来，如果非要说O（n）我觉得也是可以吧，哈哈哈哈哈，说话的艺术

neozhang9233 发表于 2019-4-5 08:18
getMinLen()的速度取决于requires在road上的平均数量，我当时说因为在真是的例子里，也不可能一条街每栋 ...

这个可以使用binary search稍微提升下吧？

list中的位置是排序的，直接将当前block的index在其中搜索，找到之前之后的元素，比较下大小

第四题 是给一个1D array吗 然后里面包括各种各种 比如[学校,医院,0,0,0,餐厅,咖啡馆] 这样的输入?

毛线666 发表于 2019-3-29 08:16
个人观点，仅供参考：
1. 33天能到200分是基于每天都登陆签到，答对问题并且不花任何积分的情况下。 对 ...

说得好! 我也觉得设高限不是很方便 特别是在职刷题跳槽的

kaipeng21 发表于 2019-3-28 07:15
**** 本内容被作者隐藏 ****

还是这个例子讲的清楚 给你加米了 可是加米的原因写错了 :(

neozhang9233 发表于 2019-4-5 08:18
getMinLen()的速度取决于requires在road上的平均数量，我当时说因为在真是的例子里，也不可能一条街每栋 ...

复杂度应该是O(nf) f is the total number of facilities.