寻找两个人都喜欢的餐厅的minimum index sum。
Example :
Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["KFC", "Shogun", "Burger King"]
Output: ["Shogun"]
Explanation: The restaurant they both like and have the least index sum is "Shogun" with index sum 1 (0+1).
这题我一开始想用两个指针来查找的，想了一下复杂度是O(n2)（嵌套的for循环），而且也需要额外空间保存多个餐厅。所以如果先把第一个人喜欢的餐厅的index保存起来，再用第二个人喜欢的餐厅去get(key)匹配，这样复杂度是O(n)。
写的时候发现，只能保存当前最优啊。于是我还用了Iterator去查找entry.getValue() == minSum的key保存到arraylist里，最后还有个arraylist转array的操作。。AC了，但实在是冗长：
我的代码：
public String[] findRestaurant(String[] list1, String[] list2) {
int minSum = Integer.MAX_VALUE;
HashMap<String, Integer> map = new HashMap<>();
//SparseArray
HashMap<String, Integer> curMin = new HashMap<>();
for (int i = 0; i < list1.length; i++) {
map.put(list1[i], i);
}
for (int j = 0; j < list2.length; j++) {
if (map.get(list2[j]) != null) {
if (j + map.get(list2[j]) <= minSum) {
minSum = j + map.get(list2[j]);
curMin.put(list2[j], minSum);
}
}
}
//traverse the hashmap
ArrayList<String> res = new ArrayList<>();
Iterator iterator = curMin.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry entry = (Map.Entry) iterator.next();
if ((Integer) entry.getValue() == minSum) {
res.add((String) entry.getKey());
}
}
return res.toArray(new String[res.size()]);
}
其实呢，可以用类似DFS遍历二叉树输出每一层节点的那种方法，把每次得到的minSum再做key，保存到arraylist<list<String>>里去（大雾），这样不行的，因为arraylist的查找是O(n)时间 没什么区别。
看了别人的答案：
public String[] findRestaurant(String[] list1, String[] list2) {
Map<String, Integer> map = new HashMap<>();
List<String> res = new LinkedList<>();
int minSum = Integer.MAX_VALUE;
for (int i=0;i<list1.length;i++) map.put(list1[i], i);
for (int i=0;i<list2.length;i++) {
Integer j = map.get(list2[i]);
if (j != null && i + j <= minSum) {
if (i + j < minSum) { res = new LinkedList<>(); minSum = i+j; }
res.add(list2[i]);
}
}
return res.toArray(new String[res.size()]);
}
他的思路是，如果遇到index sum相同的饭店，就保存起来；如果遇到index sum更小的饭店，就把这个res清空，更新minSum，重新开始保存。
今天写了简历，一个日本猎头问我是否available to talk，我回复说yes，她立刻从日本打电话过来。。英文聊了15分钟，我竟然全都听懂了，还蛮开心的。就是她跟我说80%的人都跪在了面试之前的笔试上，让我觉得有些难受了。。虽然早已经做好了送人头的准备。不管怎么说，算是迈出了这么一步。Always, good luck, Larry!
29 May 2017
