最方便的寓所

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

粘一个个人的答案，无论是求距离和还是最远都可以用这个方法，速度为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最后应该是，忘了改了

根据面经讨论写了两个方案，附上代码和unittest，如有错误或遗漏的case欢迎留言指教，followup用第一种改好像比较容易

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

补充内容 (2019-3-28 23:41):
总觉得这还不是最优解，有没有更好的方法啊

关于双倍积分奖励算法题和系统设计题讨论的决定：

我们：
1. 希望能看到干货讨论；
2. 希望能看到好的代码（web端高级发帖模式下，@ 朋友右边的<> 可以选择多种代码）

版主 @14417335 负责审核加分，也请大家给好的回复加分 + 顶。
大家给30，我会跟进奖励30，double之；
大家给100，我也会跟进奖励100，double之。

很理解大家写代码、调试、写思路分析，很花时间。对于特别好的回复，还会有额外加分。

欢迎大家拿出好的题目讨论，选中了我会全站置顶。哪位同学起了好的题目/帖子，激发了干货讨论，也会获得一定的积分奖励。

欢迎大家踊跃参与。看到好的回复，也请大家顶一下，作为对别人积极参与讨论、热心分享的认可和鼓励。

其他可以获得双倍积分的题目：

在刷题版里选择高频题标签，链接:
https://www.1point3acres.com/bbs/forum.php?mod=forumdisplay&fid=84&filter=typeid&typeid=1019

大家看到LC没有的高频题，也请贴到刷题版里，又有大米又有赞。对于学弟学妹们也是功劳一件。举手之劳。谢谢大家的参与。

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

如果是后者，用移动窗口模板找最小的包含所有requirement的区间，再找中间应该就行了

讨论高频题，分数设这么高， 是只有senior 农民才看得到么

kaipeng21 发表于 2019-3-28 07:18
如果是后者，用移动窗口模板找最小的包含所有requirement的区间，再找中间应该就行了

这个实现比较复杂吧，什么条件窗口滑动一下。前一个block移出，后一个block 进入。。

毛线666 发表于 2019-3-28 07:56
讨论高频题，分数设这么高， 是只有senior 农民才看得到么

不是senior是serious。

分数200那么对于任何serious的农民都应该较快得到。且不说地里很多如何攒积分的帖子。就是每日签到都应该报道33天后成为200积分。

14417335 发表于 2019-3-28 21:54
不是senior是serious。

分数200那么对于任何serious的农民都应该较快得到。且不说地里很多如何攒积分 ...

个人观点，仅供参考：
1. 33天能到200分是基于每天都登陆签到，答对问题并且不花任何积分的情况下。 对于大多数人来说学生／工作的人，可能有due或者在赶项目。不一定每天能上来签到。另外对于答题，我打错的一道题是facebook的level 几等于xx公司的level几？ 我不认为这个是个necessary或者大部分人都知道的知识。很难确保说你每天答题都是正确的。一旦打错，要减分，那么日子相当于往后拖了一天。 总而言之，理论上的33天，会延长到1.5 - 2个月。

2. 全力刷题的小伙伴对于参与这类帖子的积极度更高。同时，全力刷题的小伙伴的战线不会拖得太长。通常3-4个月，就得出去面了。那么在准备面试的后期，精力会以面经或者特定公司的高频题为主。不一定会特别follow general的高频题。那么这类帖子最核心的人群就很难保证了。
对于其他刷题的朋友，如果战线拖的很长的那种，肯定一天没有多少时间真的在刷题，那么参与这类帖子的几率就相对很低了。

3. 实践是检验真理的标准。对吧

again，个人观点。仅供参考

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

默默同意层主。。