0

我的问题是关于 FB HackerCup 2013 QualificationRound 问题 - BalancedSmileys。

问题陈述：https ://www.facebook.com/hackercup/problems.php?pid=403525256396727&round=185564241586420 （也复制到这里：https ://github.com/anuragkapur/Algorithmic-Programming/tree/master/src/com /anuragkapur/fb/hackercup2013/qr#problem-2-balanced-smileys）

我想出了如何使用具有指数运行时间的 BruteForce 方法来解决这个问题。

根据发布的官方解决方案，有一个线性运行时间的解决方案。此处描述：https ://www.facebook.com/notes/facebook-hacker-cup/qualification-round-solutions/598486173500621

本质上，它维护两个计数器：minOpen 和 maxOpen。每当遇到左括号“(”时，maxOpen 就会增加。如果“(”不是笑脸的一部分，minOpen 也会增加。处理“)”的类似策略也是如此，如上面的解释链接中所述。

我可以看到线性时间方法有效，但在我的脑海中并不清楚 - 怎么样？所以我正在调查这个小组，看看是否有人可以给出线性运行时间解决方案的替代“解释”。

非常感谢！

4

2 回答 2

1

如果不是规则 #2 中的冒号，那么显而易见的算法将是一个具有两种状态的有限状态机，它循环遍历字符串并维护括号计数：

  • pcount = 0
  • 对于每个字符：
    • 如果是':'：丢弃下一个字符
    • 如果是 '（'：pcount++
    • 如果是')'：pcount--如果pcount > 0，否则立即返回“NO”

规则 #2 允许使用冒号这一事实使其更具挑战性，因为“(:)”或“(foo :)”形式的消息也可能被视为具有平衡括号。这条规则本质上说的是“你很难判断一个括号是否真的是一个括号或一个表情符号的一部分”，并且你应该确定“是否有一种方法可以在保持括号平衡的同时解释他的信息”。

更清楚地说：我们实际上根本不关心表情符号。我们将找出括号是否可以平衡。

天真的方法是维护一个括号计数器数组。最初，它只包含一个括号计数器。每次遇到 '(' 或 ')' 时，都将当前的括号计数器数组附加到自身，按照上面简单算法中的建议将前半部分递减/递减。到达字符串末尾后，检查数组是否包含零。如果是这样，则有一种方法可以将字符串视为具有平衡括号。否则，没有。

第二种算法可能还有改进的余地，如果消息包含 1000 个括号，甚至可能有一个优雅得令人瞠目结舌的解决方案，它不会耗尽内存。但是，如果有足够的 RAM，这种幼稚的方法将在线性时间（不幸的是，指数空间）内确定正确答案。

于 2013-04-07T17:46:19.457 回答
1

预处理：对输入进行标记并将每个标记转换为一个列表，其中包含对开括号计数的可能影响。

输入

i am sick today (:()
:(:))

变得

[[0], [0], ..., [0], [1], [0, 1], [-1]]
[[0, 1], [-1, 0], [-1]]

. 现在，你的蛮力算法是这样的。

def solution1(lst, opencnt=0, i=0):
    if opencnt < 0:
        return False
    elif i >= len(lst):
        return opencnt == 0
    else:
        for delta in lst[i]:
            if solution1(lst, opencnt + delta, i + 1):
                return True
        return False

对于给定的输入，该函数solution1总是给出相同的输出。对于在 {-1, 0, 1} 中具有条目的给定， (-1 to ) 和(0 to )lst中的每一个都只有线性数量的可能性，因此通过缓存给定输入的输出，即记忆，我们得到二次时间算法。opencntlen(lst)ilen(lst) - 1

线性时间算法将控制流从里到外翻转。我们没有对 each 进行单独的递归调用delta，而是创建opencnt了一个集合。

def solution2(lst, opencnt={0}, i=0):
    opencnt = {x for x in opencnt if x >= 0}
    if i >= len(lst):
        return 0 in opencnt
    else:
        return solution2(lst, {x + delta for x in opencnt for delta in lst[i]}, i + 1)

这个实现还不是线性时间。最后的优化是opencnt始终是一个区间，即[minOpen, maxOpen]，并且可以在恒定时间内进行操作。

于 2013-04-07T17:37:43.590 回答