[Coursera] Standford Algorithm Design & Analysis II

kinslover 发表于 2012-12-25 09:52
hamming的话我没做什么优化，就是O(N^2)的算一遍，保留

嗯，我那个程序跑了有10s多，测试了一下基本都在pre-processing上了。。论坛上有人说把各个位加起来然后直接看距离什么的，但又没详细说。不知道他们的O(n)的算法怎么弄出来的。我hamming距离的数据结构用STL里的bitmap了，不知道内部怎么实现的，比我自己弄的数据结构快了很多。我在wiki上看到一个计算的算法但是用bitmap实现不了。你是怎么构建距离的数据结构的？

bmbdl 发表于 2012-12-25 09:51
不用每个节点之间都比较

每个节点只可能有300个节点与它的的距离不超过2

这是什么意思啊？能解释一下吗？貌似这个图里有很多重复的节点哦。

moophis 发表于 2012-12-25 11:53
这是什么意思啊？能解释一下吗？貌似这个图里有很多重复的节点哦。

举个例子，比如一个数 101，与它汉明距离为1的数只可能有三个，也就是001, 111, 100。距离为2的类似，有 C(3,2) 个。距离为0的有一个。长度为24的情况类似，所以每个数只需要常数时间的处理，总体也就是O(n)啦。

这道题里的label直接用数字表示就行了，因为只有24位。

bmbdl 发表于 2012-12-25 09:59
嗯。。暴力的话，用find-union就好了，遍历20k*20k个边，同时就可以find-union做完了。代码比BFS/DFS简单 ...

Union-find是不是还要再扫一遍数组统计一下总的连通分量数目？那样的话可能还得用map维护一下，同时由于需要遍历所有边，整体应该会比DFS慢不少。

bmbdl 发表于 2012-12-25 15:10
举个例子，比如一个数 101，与它汉明距离为1的数只可能有三个，也就是001, 111, 100。距离为2的类似，有  ...

你好啊，也在这题卡了好久。每个节点只需要跟301个节点比较就好，但是要怎么找到这301个节点啊？一直没搞懂这个问题。另外，问个比较弱的。。你们数据读进来是怎么存的啊?我是用C写的。。。因为它是一个一个数字进来，应该不能存到一个int里面吧？。。。

kinslover 发表于 2012-12-25 16:00
Union-find是不是还要再扫一遍数组统计一下总的连通分量数目？那样的话可能还得用map维护一下，同时由于需 ...

每次union减一即可。。

zhuzhda 发表于 2012-12-25 16:15
你好啊，也在这题卡了好久。每个节点只需要跟301个节点比较就好，但是要怎么找到这301个节点啊？一直没搞 ...

嗯。。C的话数据结构是个问题，我用的是ruby自带的permutation函数，python也有，其它语言不太了解。字符串转数字的话可以自己写个函数，不麻烦，类似atoi的

zhuzhda 发表于 2012-12-25 16:15
你好啊，也在这题卡了好久。每个节点只需要跟301个节点比较就好，但是要怎么找到这301个节点啊？一直没搞 ...

我是用C++的bitmap容器了，图省事。如果用C的话，不知道这个行不行，我估计可以吧:
struct bitmap {
    unsigned char[3];
};
读数据的时候根据读的数据分别按位或下这个结构里的成员。不过前提就是你得先知道这个汉明距离是24位的。

bmbdl 发表于 2012-12-25 16:24
每次union减一即可。。

你的意思是每成功union一次减一吗？因为可能存在make union两个已经在一个cluster的节点的情况。

另外你刚说的那个估算是基于没有两个节点的之间的距离是0的情况。但是这个图里有很多重合的节点啊？距离的可能性确实有C(24, i) (i = 0,1,2,3) 种，但是每种距离可能性的节点也许不止有一个。还有你是怎么查找其他节点是否符合预计的可能性的？O(n)的方法还是不太明白呀~~请赐教啦

bmbdl 发表于 2012-12-25 16:25
嗯。。C的话数据结构是个问题，我用的是ruby自带的permutation函数，python也有，其它语言不太了解。字符 ...

总时间复杂度可以认为是 O(301 * n log n) 不？