G家onsite 8/8

求问第二题，group里的每个item都必须被所有比他大的item包含吗？如果是(1, 2, 4), (1, 2), (4) 这三个可以放一起吗？

zxcnn 发表于 2016-8-19 06:28
感觉答得很好啊，HC这么不靠谱吗

可能有的回答不够最优？= =

pushazhiniao 发表于 2016-8-19 05:11
感觉楼主的题第二题我不是很明白额。求讲解。
我说一说另外几题。
1.第一题就是bfs，感觉并不需要hashmap ...

1. 第一题的大数据用的hashmap, 因为大数据是按行读取的。
2.这题我不确定还有没有更优解，但是目前DP感觉不行~这个思路算是我在面试官启发下给的。面试官说他也是这么做的，他说想不到更优的了。
3.没错就是这样~
4.1要求词组是连续的，不是随便挑几个单词组合。比如happy new year new year. max = 2. 可以有词组 new year，year new, 但是没有 happy year， new new 什么的~
4.2 前面有一层主给的解法很赞~

1.2 不需要hashmap，记住上一行的结果，当循环array用，挪一位跟下一行直接比就好；
2. 感觉答案很漂亮，不需要unionfind
3. 回答的也很好
4.2. 这是leetcode所有数出现两次except一个数只出现一次那题几乎原题呀。把所有数异或一次，异或结果就是你要的结果。

hyj143 发表于 2016-8-19 07:35
所以4.2 有人想到用二分了么

正解， 这题确实二分最快

楼主第四轮第一题暴力就是O(n)了吧，没有什么可优化的吧

chenzhan171 发表于 2016-8-19 14:32
正解， 这题确实二分最快

求问二分法怎么写

chenzhan171 发表于 2016-8-19 14:32
正解， 这题确实二分最快

我就随便问问 二分怎么做？

第二题我觉得直接greedy就可以了吧 。
但是为什么greedy 是正确的呢？？

hyj143 发表于 2016-8-20 00:01
我就随便问问 二分怎么做？

二分就是找两个string中第一个不一样的char， 以第一个string为基准， st = 0 , ed = s1.length() - 1;
然后二分和第二个矩阵中相同位置的char比较， 如果二分没有找到， 则多出来那个元素必然是s2的最后那个。