最方便的寓所

粘一个个人的答案，无论是求距离和还是最远都可以用这个方法，速度为O（nk），k为requires项数。

1. class Solution {
   
2. 
   
3.     /*
   
4.     * Input: 1. 给一条路，路上的不同位置有不同的设施，有多个设施在不同位置的情况, List<Set<String>>
   
5.     *        2. 给一个需求设施的set
   
6.     * Output： 希望给出一个位置，距离所有设施的距离最近的和
   
7.     *
   
8.     * Example:
   
9.     *   Road: {
   
10.     *           [bookstore, school],
    
11.     *           [grocery] ,
    
12.     *           [],
    
13.     *           [],
    
14.     *           [bookstore, library],
    
15.     *           []
    
16.     *           [grocery]
    
17.     *        }
    
18.     *   Requires: [bookstore, library, grocery]
    
19.     *   Output: the best place is 4, to bookstore and lib is 0, and grocery is 2, so in sum is 2.
    
20.     * */
    
21. 
    
22.     public int findBestLocationn(List<Set<String>> road, List<String> requires) {
    
23.         Map<String, List<Integer>> roadMap = createMap(road);
    
24.         int minSum = Integer.MAX_VALUE, index = 0;
    
25.         for (int i = 0; i < road.size(); i++) {
    
26.             int sum = 0;
    
27.             for (int j = 0; j < requires.size(); j++) {
    
28.                 sum += getMinLen(roadMap, requires.get(j), i);
    
29.             }
    
30.             if (sum < minSum) {
    
31.                 minSum = sum;
    
32.                 index = i;
    
33.             }
    
34.         }
    
35.         return index;
    
36.     }
    
37. 
    
38.     private Map<String, List<Integer>> createMap(List<Set<String>> road) {
    
39.         Map<String, List<Integer>> roadMap = new HashMap<>();
    
40.         for (int i = 0; i < road.size(); i++) {
    
41.             for (String facility: road.get(i)) {
    
42.                 List<Integer> list = roadMap.getOrDefault(facility, new ArrayList<>());
    
43.                 list.add(i);
    
44.                 roadMap.put(facility, list);
    
45.             }
    
46.         }
    
47.         return null;
    
48.     }
    
49. 
    
50.     private int getMinLen(Map<String, List<Integer>> roadMap, String require, int index) {
    
51.         List<Integer> list = roadMap.get(require);
    
52.         int minLen = Integer.MAX_VALUE;
    
53.         for (int pos: list) {
    
54.             minLen = Math.min(minLen, Math.abs(pos-index));
    
55.         }
    
56.         return minLen;
    
57.     }
    
58.    
    
59. }

复制代码

补充内容 (2019-3-29 09:21):
return raodMap;

第二个method最后应该是，忘了改了

brave2 发表于 2019-3-29 11:59
我怎么感觉你这方法不对呢。。是我理解错了吗。
为啥“找所有符合条件的移动窗口中的最小值，纪录最小窗 ...

跟利口漆遛一样，sliding window 中必须要包含所有的requirement，window的开始与结束两端必有requirement ，这个window越小表示requirement 之间的距离越近，根据题意最短距离指的是公寓到最远的requirement poi 的距离，而window的正中间到两端的距离是最短的，离开window中点就会使到其中一端的距离变长，就不是最近了

这是相对而言我比较不确定算法是不是完全正确的，如果有反例欢迎指出修正

brave2 发表于 2019/03/29 13:36:36


反例比如说：

7个点：0，0，0，0，0，0，1000

距离所有点之和最近的点 应该是点0，距离为1000；而不是点500，距离为3500

题意有误解，这题有两种问法，一种是问距离和，一种是问到最远的一个的距离，距离和的话这个作法当然是不对的，如果只是到最远的requirement 的距离，500距离0和1000都是500，这例子就没问题

补充内容 (2019-3-29 13:52):
所以我的第一种方法也是写max(dist[i].values()) 不是sum(dist[i].values())

kaipeng21 发表于 2019/03/28 23:34:13
根据面经讨论写了两个方案，附上代码和unittest，如有错误或遗漏的case欢迎留言指教，followup用第一种改好像比较容易

[hide=200]
[mw_shl_code=python...

补充：我这题写的最近的定义是，离最远的requirement 的距离，也有的题目是问到所有requirement 的距离和，距离和的问法方案二就不适用，方案一要小修改

我也觉得这涨积分大米的要求特别高。如果一年60的会费我早买了，只有一个月，也太贵了。新人什么都看不到，也伤心

ymqu 发表于 2019-3-29 19:43
我也觉得这涨积分大米的要求特别高。如果一年60的会费我早买了，只有一个月，也太贵了。新人什么都看不到， ...

我对毛线的关于大米门槛回复写到公社里去了。

https://www.1point3acres.com/bbs ... read&tid=495720

第9垅

贴个自己的解法, 时间复杂度是O(KN)而非O(KNL)

另外感谢kaipeng21的test cases

Time complexity: O(KN)
Space complexity: O(KL)

N: street長度
K: requirements長度
L: 同一個requirement在*不同*index上出現的最大次數

1. import collections
   
2. from typing import List
   
3. 
   
4. 
   
5. class Interview(object):
   
6. 
   
7.     def solution(self, street: List[List[str]], requirements: List[str]) -> int:
   
8.         dists = {}
   
9.         road_map = collections.defaultdict(collections.deque)
   
10. 
    
11.         # Builds the road map.
    
12.         for i, location in enumerate(street):
    
13.             for facility in set(location):  # Note: use `set` to deduplicate.
    
14.                 if facility in requirements:
    
15.                     road_map[facility].append(i)
    
16.         
    
17.         for facility in requirements:
    
18.             # Adds additional two ends to avoid some annoying if statements.
    
19.             road_map[facility].appendleft(float('-inf'))
    
20.             road_map[facility].append(float('inf'))
    
21. 
    
22.             dists[facility] = float('inf')
    
23. 
    
24.         index = -1  # Returns -1 if no solution exists.
    
25.         dist_sum = float('inf')
    
26.         for i in range(len(street)):
    
27.             # Updates minimum distances
    
28.             for facility in requirements:
    
29.                 left, right = road_map[facility][0], road_map[facility][1]
    
30.                 dists[facility] = min(i - left, right - i)
    
31.                 if i == right:
    
32.                     road_map[facility].rotate(-1)  # Rotates one step left.
    
33.             
    
34.             # Updates the best location.
    
35.             current_sum = sum(dists.values())
    
36.             if current_sum < dist_sum:
    
37.                 dist_sum = current_sum
    
38.                 index = i
    
39.         
    
40.         return index
    
41. 
    
42. 
    
43. # Don't specify return value if it's None.
    
44. test_cases = [
    
45.     [
    
46.         ["Store", "School", "Museum"],
    
47.         ["Hospital", "Restaurant"],
    
48.         ["School", "Restaurant"],
    
49.     ],
    
50.     ["Store", "Museum", "Hotel"],
    
51.     -1,
    
52.     [
    
53.         ["Store", "School", "Museum"],
    
54.         ["Hospital", "Restaurant"],
    
55.         ["School", "Restaurant"],
    
56.         [],
    
57.         ["Museum"],
    
58.     ],
    
59.     ["Store", "Museum", "Restaurant"],
    
60.     0,
    
61.     #
    
62.     [
    
63.         ["Store", "School", "Museum"],
    
64.         ["Hospital", "Restaurant"],
    
65.         ["School", "Restaurant"],
    
66.         [],
    
67.         ["Museum"],
    
68.     ],
    
69.     ["Hospital", "Restaurant"],
    
70.     1,
    
71.     #
    
72.     [
    
73.         ["Store", "School", "Museum"],
    
74.         ["Hospital", "Restaurant"],
    
75.         ["School", "Restaurant"],
    
76.         [],
    
77.         ["Museum"],
    
78.     ],
    
79.     ["Museum", "Hospital"],
    
80.     0,
    
81.     ###
    
82.     [
    
83.         ["School", "Store", "School"],
    
84.         ["Park"],
    
85.         [],
    
86.         ["Restaurant"],
    
87.         ["Hospital"],
    
88.     ],
    
89.     ["Park","Restaurant"],
    
90.     1,
    
91.     #
    
92.     [
    
93.         ["School", "Store", "School"],
    
94.         ["Park"],
    
95.         [],
    
96.         ["Restaurant"],
    
97.         ["Hospital"],
    
98.     ],
    
99.     ["School","Restaurant"],
    
100.     0,
     
101.     #
     
102.     [
     
103.         ["School", "Store", "School"],
     
104.         ["Park"],
     
105.         [],
     
106.         ["Restaurant"],
     
107.         ["Hospital"],
     
108.     ],
     
109.     ["Hospital"],
     
110.     4,
     
111.     ###
     
112.     [
     
113.         ["A", "B", "C"],
     
114.         ["D", "E", "F"],
     
115.         ["G", "H"],
     
116.         ["I", "J", "K"],
     
117.         ["L", "M", "N"],
     
118.         ["O", "P", "Q", "R", "S", "T", "U", "V"],
     
119.         ["W", "X", "Y"],
     
120.         [],
     
121.         ["Z"],
     
122.     ],
     
123.     ["F", "K"],
     
124.     1,
     
125.     #
     
126.     [
     
127.         ["A", "B", "C"],
     
128.         ["D", "E", "F"],
     
129.         ["G", "H"],
     
130.         ["I", "J", "K"],
     
131.         ["L", "M", "N"],
     
132.         ["O", "P", "Q", "R", "S", "T", "U", "V"],
     
133.         ["W", "X", "Y"],
     
134.         [],
     
135.         ["Z"],
     
136.     ],
     
137.     ["A", "Z"],
     
138.     0,
     
139.     #
     
140.     [
     
141.         ["A", "B", "C"],
     
142.         ["D", "E", "F"],
     
143.         ["G", "H"],
     
144.         ["I", "J", "K"],
     
145.         ["L", "M", "N"],
     
146.         ["O", "P", "Q", "R", "S", "T", "U", "V"],
     
147.         ["W", "X", "Y"],
     
148.         [],
     
149.         ["Z"],
     
150.     ],
     
151.     ["C", "V", "Z"],
     
152.     5,
     
153.     ###
     
154.     [
     
155.         ["A", "B", "C"],
     
156.         ["F"],
     
157.         [],
     
158.         ["D", "E"],
     
159.         [],
     
160.         [],
     
161.         [],
     
162.         ["D", "E"],
     
163.         [],
     
164.         [],
     
165.         ["C", "B", "A"]
     
166.     ],
     
167.     ["A", "E"],
     
168.     0,
     
169.     #
     
170.     [
     
171.         ["A", "B", "C"],
     
172.         ["F"],
     
173.         [],
     
174.         ["D", "E"],
     
175.         [],
     
176.         [],
     
177.         [],
     
178.         ["D", "E"],
     
179.         [],
     
180.         [],
     
181.         ["C", "B", "A"]
     
182.     ],
     
183.     ["F", "A"],
     
184.     0,
     
185.     #
     
186.     [
     
187.         ["A", "B", "C"],
     
188.         ["F"],
     
189.         [],
     
190.         ["D", "E"],
     
191.         [],
     
192.         [],
     
193.         [],
     
194.         ["D", "E"],
     
195.         [],
     
196.         [],
     
197.         ["C", "B", "A"]
     
198.     ],
     
199.     ["D", "E"],
     
200.     3,
     
201.     ###
     
202.     [
     
203.         ["A", "B", "C"],
     
204.         [],
     
205.         [],
     
206.         ["D", "E"],
     
207.         ["F", "G", "H"],
     
208.         ["I", "J", "K"],
     
209.         ["L"],
     
210.         ["M"],
     
211.         ["E"],
     
212.         ["N"]
     
213.     ] * 3,
     
214.     ["A", "D"],
     
215.     0,
     
216.     #
     
217.     [
     
218.         ["A", "B", "C"],
     
219.         [],
     
220.         [],
     
221.         ["D", "E"],
     
222.         ["F", "G", "H"],
     
223.         ["I", "J", "K"],
     
224.         ["L"],
     
225.         ["M"],
     
226.         ["E"],
     
227.         ["N"]
     
228.     ] * 3,
     
229.     ["D", "M"],
     
230.     3,
     
231.     #
     
232.     [
     
233.         ["A", "B", "C"],
     
234.         [],
     
235.         [],
     
236.         ["D", "E"],
     
237.         ["F", "G", "H"],
     
238.         ["I", "J", "K"],
     
239.         ["L"],
     
240.         ["M"],
     
241.         ["E"],
     
242.         ["N"]
     
243.     ] * 3,
     
244.     ["B", "N"],
     
245.     9,
     
246.     #
     
247.     [
     
248.         ["A", "B", "C"],
     
249.         [],
     
250.         [],
     
251.         ["D", "E"],
     
252.         ["F", "G", "H"],
     
253.         ["I", "J", "K"],
     
254.         ["L"],
     
255.         ["M"],
     
256.         ["E"],
     
257.         ["N"]
     
258.     ] * 3,
     
259.     ["E", "F", "M"],
     
260.     4,
     
261. ]
     
262. 
     
263. 
     
264. if __name__ == '__main__':
     
265.     interview = Interview()
     
266.     args_count = Interview.solution.__code__.co_argcount - 1  # - 1 for self.
     
267.    
     
268.     args = []
     
269.     iterator = iter(test_cases)
     
270.     while True:
     
271.         try:
     
272.             args.append(next(iterator))
     
273.         except StopIteration:
     
274.             break
     
275. 
     
276.         if len(args) == args_count:
     
277.             result = interview.solution(*args)
     
278.             if result is not None:
     
279.                 try:
     
280.                     answer = next(iterator)
     
281.                     assert result == answer
     
282.                 except AssertionError:
     
283.                     print(f'Input:')
     
284.                     for arg in args:
     
285.                         print(f'\t{arg}')
     
286.                     print(f'Expected: {answer}')
     
287.                     print(f'Your output: {result}')
     
288.             args = []
     
289. 
     
290.     print('End.')

复制代码

补充内容 (2019-3-31 02:21):
忘记设限制
没办法删文的吗?

补充内容 (2019-3-31 02:24):
解释一下
概念就是最初就纪录各requirements的位置
之后利用deque只比较最接近的两个
为了方便只回传符合要求的最小index

follow-up直接对没有apartment的index给continue就好了

kaipeng21 发表于 2019-3-28 23:34
根据面经讨论写了两个方案，附上代码和unittest，如有错误或遗漏的case欢迎留言指教，followup用第一种改好 ...

有个test case错了
应该是5

1.     def test_3(self):
   
2.         street = [
   
3.             ["A", "B", "C"],
   
4.             ["D", "E", "F"],
   
5.             ["G", "H"],
   
6.             ["I", "J", "K"],
   
7.             ["L", "M", "N"],
   
8.             ["O", "P", "Q", "R", "S", "T", "U", "V"],
   
9.             ["W", "X", "Y"],
   
10.             [],
    
11.             ["Z"]
    
12.         ]
    
13.         requirements = ["C", "V", "Z"]
    
14.         assert sorted(best_apartment(street, requirements)) == [4]

复制代码