骰子拼字

现在都已经考二分图匹配这么难的题了吗.....

刚刚电面面了这道，吓到我了。。。

fuxi9999 发表于 2019-3-23 13:35
在论坛里搜了一下这题。看到这个介绍二分图解法的， copy过来给大家参考
=============================== ...

这个算法还是常用的，比方给工人配活，求成本最低的搭配方式；或者舞伴配对最happy的组合。

这题是二分图最大匹配问题，解法如下：

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

补充内容 (2019-4-29 11:40):
这题的难度不太大，所以很有可能让你写代码。

Joseph_Liu 发表于 2019-4-23 02:13
刚刚电面面了这道，吓到我了。。。

结果咋样啊

感觉这个maximum bipartite  matching /  max flow的python代码还挺简洁的 https://www.geeksforgeeks.org/maximum-bipartite-matching/
和前面的java代码方法一样。

fuxi9999 发表于 2019-3-23 13:35
在论坛里搜了一下这题。看到这个介绍二分图解法的， copy过来给大家参考
=============================== ...

看大家都说是二分图最大匹配问题，但有没有可能dice和string构不成二分图呢？比如这个例子: dice = ['ac', 'bs', 'ao'], s = 'bca', 这个本身构不成二分图，用匈牙利算法得出解是2，但实际应该是3, 'ac' -> 'c', 'bs' -> 'b', 'ao' -> 'a' 。

孙行者 发表于 2019-4-29 11:36
这题是二分图最大匹配问题，解法如下：
**** 本内容被作者隐藏 ****

看大家都说是二分图最大匹配问题，但有没有可能dice和string构不成二分图呢？比如这个例子: dice = ['ac', 'bs', 'ao'], s = 'bca', 这个本身构不成二分图，用匈牙利算法得出解是2，但实际应该是3, 'ac' -> 'c', 'bs' -> 'b', 'ao' -> 'a' 。

补充内容 (2019-5-20 05:57):
请忽略，我搞错了。

孙行者 发表于 2019-4-29 11:36
这题是二分图最大匹配问题，解法如下：
**** 本内容被作者隐藏 ****

请忽略上条回复，我搞错了。但你代码有点问题，bipartitie维度应该是[m+n][m+n], dice和string里的字符应该是不同的节点