1
unavph 2018-03-07 20:40:37 +08:00 4
给个看 N 次的:取对角线然后按位取反,这样得到的结果和第 i 个朋友的第 i 位总是不同的。
|
2
unavph 2018-03-07 20:44:33 +08:00
@unavph 没有更好的结果了,任何查询小于 N 次的算法都会对至少一个朋友的情况完全不知情。这样的话会有至少一个朋友的支持队伍是任意值,也就可能和自己结果重复。
|
3
qiuyk 2018-03-07 21:09:00 +08:00
想了一下,对是否支持 team 建立二叉决策树,支持往左不支持往右。原问题就变成了找叶节点到根节点不与其他朋友重合的简单路径。应该是可以用 BFS 加剪枝做,不过暂时没想到要怎么剪枝。
|
4
enenaaa 2018-03-07 22:34:56 +08:00
楼主的思路有问题。 按这个思路,如果第一个朋友支持 0 个 team, 后面人支持 N 个,结果为 N 个,这明显是错的。
在不考虑优化时, 需遍历所有朋友的支持情况,即 N*N 次函数调用。 注意到题目只要求任一不同路径,实际上并不一定要完全遍历。 如 @qiuyk 所说, 可以构建二叉树来搜索。 我的思路,步骤: 1. 对 N 个 team 编号为 t1~ tn。 2. 以 t1 为二叉树根节点。设 ti=t1 3. 遍历 所有的朋友, 如果有人支持 ti, 则为当前层次的所有节点创建左子节点。 如果有人不支持 ti, 则为当前层次所有节点建立右子节点。 4. 遍历本层所有节点, 如果有子节点少于 2 个节点。 即当前路径与所有朋友都不同,回溯路径即为结果。如果是完全二叉树, 则 ti = ti+1。从第 3 步继续执行。 这个算法只有最坏时才需要 N*N 次 support 调用。 |
5
clavichord93 2018-03-07 22:36:23 +08:00 via iPhone
@unavph 应该没问题,初步想了一下也是这么做
|
6
enenaaa 2018-03-07 22:49:45 +08:00
额, 将楼主的解法看错了。
|