G家onsite 8/8

hunter12345654 发表于 2016-8-20 02:30
第二题如果是交集就行，所有子集有同一个元素，怎么做呢？
e.g （1,2）（1,3）（1,4）（2,5）（3,6）（4,7 ...

是并集，我一开始说错啦。你这个例子就不能合并在一个组里了。全部都是独立的

low910411 发表于 2016-8-25 01:10
是并集，我一开始说错啦。你这个例子就不能合并在一个组里了。全部都是独立的

我的意思是说，我把题目改了，改成有相同元素的就可以放到一个集合里。 求最小集合数量怎么做？

hunter12345654 发表于 2016-8-25 01:17
我的意思是说，我把题目改了，改成有相同元素的就可以放到一个集合里。 求最小集合数量怎么做？

那就union find

low910411 发表于 2016-8-25 01:19
那就union find

你的属于用错了？应该是子集？

补充内容 (2016-8-25 02:10):
*术语

第一题就是i-j的关系
主斜线是0
然后依次是-1, 1
-2, 2
按照这个顺序生成循环i，算j判断是不是相等就好了

follow up 只需要记录第一行和第一列的数字，然后根据上面那个法则反推i,j判定是不是相等就好了

南慕伦 发表于 2016-8-25 02:10
你的属于用错了？应该是子集？

补充内容 (2016-8-25 02:10):

第二题如果是说子集的话 必然那个是最优的，并查集做没有意义，因为这里有多个元素你仍然需要一个一个比对。

low910411 发表于 2016-8-25 01:19
那就union find

我对union find不太熟，如何保证集合数量最小呢。 我之前举得例子，如何保证结果是[(1,2)(2,5)],[(1,3)(3,6)],[(1,4)(4,7)] 而不是 [(1,2)(1,3)(1,4)],[(2,5)],[(3,6)],[(4,7)] 呢

hunter12345654 发表于 2016-8-25 02:24
我对union find不太熟，如何保证集合数量最小呢。 我之前举得例子，如何保证结果是[(1,2)(2,5)],[(1,3)(3 ...

我觉得保证不了。

补充内容 (2016-8-25 02:31):
如果是有相同元素就可以放一起，我能想到的就 搜索+剪枝，找到一个上界剪枝应该还是比较强的

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

其实我想说, java substring 占空间....