我需要创建一个排序算法,根据对对卡片进行排序,例如,如果您有 4JJQQ,它应该对 QQJJ4 进行排序。我尝试了很多不同的方法,但似乎很难正确排序。我基本上有一系列牌,其中包含那手牌。
最佳答案
这个问题对我来说还是有点不清楚。所以我会做一些假设,如果我错了,你可以纠正我。
如果您的主要问题基本上是比较 J 这样的文字和 4 这样的数字,那么 Counting Sort是你的解决方案。
它是什么:它是一种排序算法,应用于可能排序的值有限的情况。您创建一个包含所有可能值的表,在一次扫描中,计算每个文字在表中相应行中更新相同内容的所有出现次数。然后您所要做的就是使用它以适合您的偏好顺序对原始数组进行排序。
优点:计数排序是比合并和快速排序等其他通用算法更快的算法(平均需要 O(n) 时间)。如果你的可能值确实有限,那么我建议你使用它。
现在是“成对”排序的部分,这是我不太明白的事情。 您能否告诉我们以下测试用例“JJQJ4”和“JQ329”的预期答案是什么?
典型的计数排序可以将它们排序为QJJJ4和QJ932(这里没有对的概念)
如果您的答案模式是[对][单数],每个答案都按降序排列, 您只需要修改计数排序,使其首先填充偶数张卡片。如果任何文字剩余的可用卡片为 1 或 0,则会在最后填充它们。这样,我的测试用例的答案将是
JJQJ4和QJ923。
此外,您的两个测试用例似乎也适合。
替代方案:
您提到,当很明显它们是一对时,您希望跳过比较两个文字。我可以建议使用一些类似树的文字存储吗?因此,我们的想法是拥有一个带有 2 个子节点的中央玩家节点。左 child 将存储成对的出现,而右 child 将存储单数。
文字的存储将以二叉树的方式完成。文字的插入将被修改。
当你获得 45JJQ 时,
1) 输入: 4 。流程:将4存储为玩家节点的rChld
2) 输入: 5 。过程:将 5 存储为 4 的 rChld
3) 输入:J 。过程:将J存储为rChld of 5
4) 输入:J 。处理:由于存在另一个J,因此5->rChld:NULL。 J 被存储为玩家节点的 lChld(同样,以二叉树方式,即,如果 lChld [两对] 中已经存在文字,则 J 将被存储为文字左或右子节点,具体取决于它是更大或更小)。
5) 输入:Q 。过程:将 Q 存储为 rChld of 5
要比较两手牌,首先要成对搜索最大的牌(最右边的 child 没有 child )。您还可以轻松计算对的数量。在一般的二叉树中,您需要 BFS 或 DFS。但由于最多只能拥有 2 对,因此您可以轻松做到这一点。如果lChld为空,则再次在rChild中查找单数牌的大牌。
注意:如果您确实正在制作类似于扑克的游戏,您可能还需要 3 个类似的游戏。可以通过在玩家节点的左子节点中存储“权重”来将其容纳在节点中。即,如果J出现两次,权重为2,如果出现三次,权重为3,依此类推。比权重更好的方法可能是使用 binomial heaps 。
关于java - 排序算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10808024/