最近从FAANG采访中得到了这个问题。
给出游戏宝石迷阵,其中3个或更多相同颜色的上/下/左/右引起爆炸。然后,播放器将交换相邻的颜色以引起爆炸效果。创建一个随机的生成器以填充木板的颜色。
我建议先生成板,然后如果板没有一种可能的方式来交换爆炸,我们可以通过交换一些颜色来创建。没关系。
然后他深入研究问题的随机生成部分,然后我建议设置一个set和while循环以生成每种颜色。设置是我不想生成的颜色。但是,这将导致冲突,并且由于随机生成器具有不确定的时间复杂度,因此它可能永远持续运行。他要我制作一个具有确定性时间复杂度,但在避免板上爆炸的同时还是随机的发生器。
我对此大为困惑,关于随机确定性时间复杂度算法的主题似乎并不多。
编辑:
找到一种算法,该算法生成NxM网格图的随机着色,其中允许两个连续的相同颜色但三个或三个以上不连续的节点在确定时间(多项式时间)中运行,并且大于2使用颜色。