G家onsite 8/8

感觉楼主的题第二题我不是很明白额。求讲解。
我说一说另外几题。
1.第一题就是bfs，感觉并不需要hashmap。起始[(0,0)]然后每一轮比较(i,j)和(i+1,j+1)并放入两端的[(i,j+1),(i+1,j)]。也就是斜着走的bfs。
2.比较不明白的是1)那个例子每个set都有2，为啥要分成两份，一份不可以吗？2)这题要求最优解，楼主的方法像greedy，不过能保证最优吗？还是需要dp？
3.楼主的把char序列转成整数来比较很好呢，followup里类似bucket sort，每个机器跑一遍自己的substring，算出最小最大index然后跟隔壁bucket比较。
4.第四轮国人小哥好给力。第一题是类似combination sum之类的，dfs跑出小于等于n的长度的list就存入返回值。第二题就是lc的one edit distance吧。

求问楼主第二题的题意。

补充内容 (2016-8-19 05:18):
谢谢楼主解释，如果是包含关系的话，应该类似lc的这题https://leetcode.com/problems/largest-divisible-subset/
这题dp做法

补充内容 (2016-8-19 05:22):
不过楼主的这题还是要greedy

第二题我估计转换成图比较好解释，每个set变成一个node，然后不同set之间的包含关系当做是有方向的边，比如A包含B，那么A有个边指向B，最后构建出来这个图之后，看起来没有人指向的node的数量就是最少可以分成的份数，一个思路，不知道对不对。

randrand1 发表于 2016-8-19 05:16
第二题我估计转换成图比较好解释，每个set变成一个node，然后不同set之间的包含关系当做是有方向的边，比如 ...

感觉你说的可行，好像union-find啊

补充内容 (2016-8-19 05:35):
楼主，union-find里每次都设置较小的set为root不可以吗？这样就要求每个set跟根set比较看是不是一组？最后看有多少组？比如链接(1,2)和(1,2,5)的时候设置(1,2)为parent，这样(2,5)不可以链接。

def groupSets(listOfSets):
        parent = {}
        groups = set()
        # make bigger set parent, if a set is a root set's superset, link
        def link(x, y):
                if len(listOfSets[x]) > len(listOfSets[y]):
                        parent[y] = x
                else:
                        parent[x] = y
        def find(x):
                if parent[x] != x:
                        parent[x] = find(parent[x])
                return parent[x]
        listOfSets.sort(key=lambda x:len(x))
        for i, s in enumerate(listOfSets):
                parent[i] = i
                added = False
                for rep in groups:
                        root = find(rep)
                        if listOfSets[root].issubset(s):
                                link(i, root)
                                added = True
                                break
                if not added:
                        groups.add(i)
        return len(groups)

input1 = [set([1,2,3]), set([1,2]), set([2]), set([2,4]), set([2,3])]
input2 = [set([1,2,3]), set([1,2]), set([2]), set([2,3])]
input3 = [set([1,2,3]), set([1,2]), set([2]), set([2,4])]
print(groupSets(input1))
print(groupSets(input2))
print(groupSets(input3))


写了第二题跑了一下结果是对了，前面说错了，root要是最大set。求指教

补充内容 (2016-8-19 06:27):
下面是输出：
[set([2]), set([1, 2]), set([2, 4]), set([2, 3]), set([1, 2, 3])]
3
[set([2]), set([1, 2]), set([2, 3]), set([1, 2, 3])]
2
[set([2]), set([1, 2]), set([2, 4]), set([1, 2, 3])]
2

pushazhiniao 发表于 2016-8-19 06:26
def groupSets(listOfSets):
        parent = {}
        groups = set()

下面是输出：
[set([2]), set([1, 2]), set([2, 4]), set([2, 3]), set([1, 2, 3])]
3
[set([2]), set([1, 2]), set([2, 3]), set([1, 2, 3])]
2
[set([2]), set([1, 2]), set([2, 4]), set([1, 2, 3])]
2

感觉答得很好啊，HC这么不靠谱吗

要A是B的并集，A和B才可以在一份里。 是什么意思。

回答的确实不错啊。

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

4.2 这样做对吗？

1. public static char findChar(String s1, String s2){
   
2.                 char [] a=s1.toCharArray();
   
3.                 char [] b=s2.toCharArray();
   
4.                 int sum1=0;
   
5.                 int sum2=0;
   
6.                 for(int i=0;i<a.length;i++){
   
7.                 sum1+=a[i]-'a';       
   
8.                 }
   
9. 
   
10.                 for(int i=0; i<b.length;i++){
    
11.                 sum2+=b[i]-'a';
    
12.                 }
    
13. 
    
14.                 return (char) ('a'+(sum2-sum1));
    
15.         }

复制代码

所以4.2 有人想到用二分了么