2

我需要创建一个排序算法，根据对对卡片进行排序，例如，如果你有一个 4JJQQ，它应该排序 QQJJ4。我尝试了许多不同的方法，但似乎无法正确订购。我基本上有一系列卡片，包含那只手。

4

2 回答 2

2

这个问题对我来说仍然有点不清楚。所以我会做一些假设，如果我错了，你可以纠正我。

如果您的主要问题是基本上比较像 J 这样的文字和像 4 这样的数字，那么计数排序是您的解决方案。

它是什么：它是一种排序算法，适用于被排序的可能值有限的情况。您创建一个包含所有可能值的表，在一次扫描中，计算每个文字在表中相应行中更新相同的所有出现次数。然后您所要做的就是使用它以适合您的偏好顺序对原始数组进行排序。

优点：计数排序是一种比其他通用算法（如 Merge 和 Quicksort）更快的算法（平均需要 O(n) 时间）。如果您确实有有限的可能值，那么我说您使用它。

现在是按“对”进行排序的部分，这是我不太明白的。您能否告诉以下测试用例“JJQJ4”和“JQ329”的预期答案是什么？

典型的计数排序可以将这些排序为QJJJ4和QJ932（这里没有对的概念）

如果您的答案模式是[Pairs][Singular]每个按降序排序，您只需修改计数排序，使其首先填充偶数张卡片。如果任何文字剩余的可用卡片是 1 或 0，它会在最后填充它们。这样，我的测试用例的答案将是

JJQJ4和QJ923。

您的两个测试用例似乎也很合适。

选择：

您提到当很明显它们是一对时，您想跳过必须比较两个文字。我是否可以建议使用一些类似树的文字存储。所以，这个想法是有一个有 2 个孩子的中央玩家节点。Left Child 将存储对的出现，而 Right 将存储单数。

文字的存储将以二叉树的方式完成。文字的插入将被修改。

当你得到 45JJQ，

1）输入：4。过程：将4存储为播放器节点的rChld

2）输入：5。过程：将 5 存储为 rChld of 4

3）输入：J。过程：将 J 存储为 5 的 rChld

4）输入：J。过程：由于另一个 J 存在，5->rChld:NULL。J 被存储为玩家节点的 lChld（同样，以二叉树的方式，即，如果 lChld [Two Pairs] 中已经存在一个文字，那么 J 将根据它是否被存储为左或右孩子更大或更小）。

5）输入：Q。过程：将 Q 存储为 5 的 rChld

要比较两手牌，您首先要成对搜索最高的牌（最右边的没有孩子的孩子）。您还可以轻松计算对数。在一般的二叉树中，您需要 BFS 或 DFS。但是由于您最多只能有 2 对，因此您可以轻松地做到这一点。如果 lChld 为空，则再次搜索 rChild 中具有单数牌的高牌。

注意：如果您确实在制作类似于扑克的游戏，您可能还想要 3 of a kind 之类的东西。这可以通过在玩家节点的左子节点中存储“权重”来容纳在节点中。也就是说，如果 J 出现两次，则权重为 2，如果出现三次，则权重为 3，依此类推。比权重更好的方法可能是使用二项式堆。

于 2012-05-29T23:50:37.090 回答
1

如果 TYPE = {A,K,Q,J,A,10..2} （可能是 Java 的enum） 其中 A > K > Q > J > 10 > ... > 2

然后，这会做到这一点：

class Card implements Comparable<Card> {
  public TYPE ty;
  public Card(TYPE t) {
    ty = t;
  }
  public int compareTo(Card card) {
    return card.ty - ty; //you should rewrite this according to [1] rules
  }
}

排序：

Collections.sort(listOfCards); where listOfCards is a List<Card>.

[1] http://www.javapractices.com/topic/TopicAction.do?Id=10

于 2012-05-29T23:40:03.043 回答