骰子拼字

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

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

关于双倍积分奖励算法题和系统设计题讨论的决定：

我们：
1. 希望能看到干货讨论；
2. 希望能看到好的代码（web端高级发帖模式下，@ 朋友右边的<> 可以选择多种代码）

版主 @14417335 负责审核加分，也请大家给好的回复加分 + 顶。
大家给30，我会跟进奖励30，double之；
大家给100，我也会跟进奖励100，double之。

很理解大家写代码、调试、写思路分析，很花时间。对于特别好的回复，还会有额外加分。

欢迎大家拿出好的题目讨论，选中了我会全站置顶。哪位同学起了好的题目/帖子，激发了干货讨论，也会获得一定的积分奖励。

欢迎大家踊跃参与。看到好的回复，也请大家顶一下，作为对别人积极参与讨论、热心分享的认可和鼓励。
其他可以获得双倍积分的题目：

在刷题版里选择高频题标签，链接:
https://www.1point3acres.com/bbs/forum.php?mod=forumdisplay&fid=84&filter=typeid&typeid=1019

大家看到LC没有的高频题，也请贴到刷题版里，又有大米又有赞。对于学弟学妹们也是功劳一件。举手之劳。谢谢大家的参与。

在论坛里搜了一下这题。看到这个介绍二分图解法的， copy过来给大家参考
=================================
magicsets 发表于 2017-7-6 02:55:03
第二个问题本质上是求二分图的最大匹配... 算法是“匈牙利算法”或者网络流的”最大流算法“，复杂度是O(V^3)，V = dices数量 + word长度。

具体来说就是建立两个节点集合S和T，word中每个字母为S中一个节点，每个dice为T中一个节点，然后对于任意节点s∈S，t∈T，s与t之间建立一条边当且仅当dice t包含字母s。

然后S和T构成一个二分图，求得这个二分图的最大匹配数为W，那么结果“是否可以由这些骰子摇出”等价于(W == word长度)。

这种图论题目确实很难（而且工作中没用），自己去想基本上只能弄出来指数级的穷举方法，leetcode上好像也是没有的，一些学校的算法课程会在最后一两章讲网络流。

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

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

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

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

步惊云 发表于 2019-3-4 23:04
题你读懂了吗

我只能是连蒙带猜大概想明白了这题难点在哪.

题目是你说的这个意思。例子也很好。

再加一个例子吧：

骰子 = [a, b], [c, c], [a, a]要求组成abc。则必须第一个骰子b，第二个c，第三个a。

这个问题，其实答到深搜就好了，但是更好的算法可以答匈牙利算法或者KM算法，但是估计不会让现场写的。。。

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

dices数量就是word的长度
V 是不是应该 = dices的面数 + word长度

14417335 发表于 2019-3-23 19:58
dices数量就是word的长度
V 是不是应该 = dices的面数 + word长度

我觉得V应该就是骰子的数量或者word长度。
二向图一边是字母，另一边是骰子，如果字母在骰子里，就连一下。

补充内容 (2019-3-24 02:49):
二分图，不是二向图

fuxi9999 发表于 2019-3-24 02:45
我觉得V应该就是骰子的数量或者word长度。
二向图一边是字母，另一边是骰子，如果字母在骰子里，就连一 ...

这题好像是四次方而不是三次方的O。

不用你的V的定义讨论了。就设V是骰子的数目（也等于字的数目），E是骰子的面数。那么我感觉总体复杂度是 O(V * (E * V * E))

14417335 发表于 2019-3-24 03:07
这题好像是四次方而不是三次方的O。

不用你的V的定义讨论了。就设V是骰子的数目（也等于字的数目），E ...

我觉得建了图之后就不需要考虑骰子的面数了。


补充内容 (2019-3-24 03:54):
应该这么说，骰子的面数限制了边的数量。一般匈牙利是V*V matrix，每个节点的边都是V。他们的复杂度是O(V^3). 而这题V=15，E=6.复杂度应该小于O(V^3). 我觉得应该是O(V*V*E)