java 实现BINGO游戏的算法

ukxgm1gy 于 2023-05-05 发布在 Java

关注(0)|答案(3)|浏览(251)

对于那些谁不知道宾果游戏，其发挥如下

1）您会得到一张BINGO卡，其中随机打印了一个NXN矩阵的数字。数字是唯一的。打印的最大数字可以大于N^2。例如，如果你有5x5矩阵，那么最大数量也可以是75。但是数字的范围是预先决定的，比如1到M。*
2）一个人在1到M的范围内随机说出数字。*
3）如果号码在您的卡上，请将号码交叉。*
4）重复交叉数字的过程。当您穿过一整行或一整列或两条对角线时，您将获得第一个宾果游戏。游戏仍在继续，因为对于N行，N列和2条对角线，总的BINGO可能是N+N+2。*

现在我想为它创建一个算法。用户将输入随机数，算法将听到它们并在矩阵中交叉其数字（已经提供）。一旦它得到BINGO它就声明它。最好的可能方法是什么
我试着为卡维护一个二维矩阵
当一个数字被宣布时，我在O（NxN）时间内搜索它。当我找到它时，我将其设为0。
在把它设为0之后，我搜索它对应的行和列是否现在都是零。如果它在对角线上，我也搜索对角线。这需要O（3N）时间。
有更好的办法吗？

Java

来源：https://stackoverflow.com/questions/19606840/algorithm-to-implement-the-bingo-game

3条答案

按热度按时间

wfauudbj1#

您可以为每个Map到一对（行，列）的数字形成一个Map。

if ( myMap[number] exists ) {
  then increment rowCount[ myMap[number].row ];
  then increment columnCount[ myMap[number].column ];
}

if ( rowCount[myMap[number].row] == N ) { bingo! }
if ( columnCount[myMap[number].column] == N ) { bingo! }

myMap.erase( number );

对角线也是如此。

赞(0）回复(0）举报 2023-05-05

k2arahey2#

使用数组存储卡上的数字并保持排序。在调用数字时，使用二进制搜索（O（logN）时间）来搜索数字。这应该是一个快速的方法。

赞(0）回复(0）举报 2023-05-05

bmvo0sr53#

创建一个类Coordinate，用于保存宾果卡中的x和y位置。初始化为false的NxN布尔数组，用于跟踪宾果卡上被划掉的内容。
N^2次遍历宾果卡，并将每个数字添加到哈希表中，使用数字作为键，新坐标作为值。
n次迭代所有将被调用的数字，从哈希表中检索坐标，并更新布尔数组的状态。在调用重复数字的情况下，必须检索并更新布尔数组，直到哈希表不包含键。
第一次宾果检查布尔数组上每个方向的时间为4N
N^2 + n*4N总运行时间

赞(0）回复(0）举报 2023-05-05

我来回答

java 实现BINGO游戏的算法

3条答案

相关问题

热门标签

最新问答