Google 6月新鲜电面

这是GOOGLE秋招还是春招？

这个题的DP解法属于极度冷门的吧- -匈牙利算法,这都属于比较高级的算法实现了....面试估计能给出dfs+backtrack解法就可以了....

旧未来 发表于 2020/06/24 14:16:39

匈牙利算法有办法给出所有最大匹配的matching吗？还是只能给出达到最大匹配的一种matching？如果这个题目让...

对，只能给一个，要求所有的应该可以状态压缩DP或者你说的搜索

amgfan 发表于 2020/06/24 15:08:40
匈牙利算法是不是只能求一个最大匹配?

对的，只有一个。我看题主用的是 or，假设只需要一个解了

Annenberg 发表于 2020-6-25 07:51
我的第一反应是path augmentation，不过我没听匈牙利算法。看来要秒谷歌还是要做top coder呀，lc已经没用 ...

其实要看面试官需要啥 考察dfs基本功 还是期待你是competitive programming选手 - 出这个题目如果没有见过Hungarian算法的，我感觉不大可能现场想出来的

这题用的是backtracking，我做了一下。似乎用dp也可以做，但是答案我都没看懂……