V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
letianqiu
V2EX  ›  程序员

求助一道算法题。

  •  
  •   letianqiu · 2018-03-07 19:31:30 +08:00 · 2611 次点击
    这是一个创建于 2457 天前的主题,其中的信息可能已经有所发展或是发生改变。
    题目:
    一共有 N 个 cricket team 和 N 个朋友,N 个朋友分别支持这 N 个 team 中的一些队伍(可以都不支持)。你并不知道每个朋友具体支持什么队伍。有函数 support ( friend,team )返回朋友是否支持队伍。现在你希望选出你的支持队伍(可以不支持任何队伍),但是不能和任何一个朋友支持的队伍完全相同,并且要尽量少调用 support 函数

    我目前的思路是对于每个朋友,遍历 team,找到第一个他不支持的队伍,把这个队伍加入我支持的队伍 list 然后跳出,继续询问下一个朋友。不知道这个思路是否有错误,以及有没有更佳的算法
    6 条回复    2018-03-07 22:49:45 +08:00
    unavph
        1
    unavph  
       2018-03-07 20:40:37 +08:00   ❤️ 4
    给个看 N 次的:取对角线然后按位取反,这样得到的结果和第 i 个朋友的第 i 位总是不同的。
    unavph
        2
    unavph  
       2018-03-07 20:44:33 +08:00
    @unavph 没有更好的结果了,任何查询小于 N 次的算法都会对至少一个朋友的情况完全不知情。这样的话会有至少一个朋友的支持队伍是任意值,也就可能和自己结果重复。
    qiuyk
        3
    qiuyk  
       2018-03-07 21:09:00 +08:00
    想了一下,对是否支持 team 建立二叉决策树,支持往左不支持往右。原问题就变成了找叶节点到根节点不与其他朋友重合的简单路径。应该是可以用 BFS 加剪枝做,不过暂时没想到要怎么剪枝。
    enenaaa
        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 调用。
    clavichord93
        5
    clavichord93  
       2018-03-07 22:36:23 +08:00 via iPhone
    @unavph 应该没问题,初步想了一下也是这么做
    enenaaa
        6
    enenaaa  
       2018-03-07 22:49:45 +08:00
    额, 将楼主的解法看错了。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1739 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 16:40 · PVG 00:40 · LAX 08:40 · JFK 11:40
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.