G家onsite 8/8

chenzhan171 发表于 2016-8-20 01:06
二分就是找两个string中第一个不一样的char， 以第一个string为基准， st = 0 , ed = s1.length() - 1;
...

两个String没说顺序一样啊。。。你用二分做是要他能保证第一个string和第二个string相同的部分顺序一样才行

phantom 发表于 2016-8-20 01:39
两个String没说顺序一样啊。。。你用二分做是要他能保证第一个string和第二个string相同的部分顺序一样才 ...

又去看了遍lz的题设， 恩，不能用二分（lz的eg给的顺序是一样的， 所以看错了）

phantom 发表于 2016-8-20 01:39
两个String没说顺序一样啊。。。你用二分做是要他能保证第一个string和第二个string相同的部分顺序一样才 ...

就算顺序一样，如果这样怎么办：“aaaaa" vs "aaaaba"，比中间还是不知道往哪边走

chenzhan171 发表于 2016-8-20 01:06
二分就是找两个string中第一个不一样的char， 以第一个string为基准， st = 0 , ed = s1.length() - 1;
...

顺序相同的话能用二分，但是顺序不同的话就不能了吧，比如abcd和dac。顺序不同还是得用异或

lovelysier613 发表于 2016-8-20 02:10
就算顺序一样，如果这样怎么办：“aaaaa" vs "aaaaba"，比中间还是不知道往哪边走

你说的对，顺序相同也不行

第二题如果是交集就行，所有子集有同一个元素，怎么做呢？
e.g （1,2）（1,3）（1,4）（2,5）（3,6）（4,7）

Josh 发表于 2016-8-19 09:17
求问第二题，group里的每个item都必须被所有比他大的item包含吗？如果是(1, 2, 4), (1, 2), (4) 这三个可以 ...

可以放在一起的

lovelysier613 发表于 2016-8-19 14:08
1.2 不需要hashmap，记住上一行的结果，当循环array用，挪一位跟下一行直接比就好；
2. 感觉答案很漂亮， ...

感谢回答~
1.2这个我回来也想了下，感觉你的方法更好
4.2没想到是数字那道题的马甲啊啊啊啊~

kevinsun 发表于 2016-8-19 16:16
楼主第四轮第一题暴力就是O(n)了吧，没有什么可优化的吧

楼上有人提到用slid window 优化一点点

low910411 发表于 2016-8-20 02:35
楼上有人提到用slid window 优化一点点

感觉时间和空间复杂度都是一样的？还是我没有理解sliding windows。能不能给个详细点儿的过程？