在 Python 中查找第一个将字符重新排列成回文串的玩家

假设我们有一个包含小写字母的字符串 S，现在有两个玩家正在玩游戏。规则如下：

  • 如果在任何移动中，玩家可以重新排列字符串的字符以获得回文串，则该玩家获胜。

  • 当玩家必须从字符串中删除任何字符时，该玩家无法获胜。

我们必须记住，两位玩家都以最佳方式玩游戏，并且玩家 1 先开始游戏。我们必须找到游戏的获胜者。

因此，如果输入类似于“pqpppq”，则输出将是玩家 1，因为玩家 1 在第一步中将字符排列为“ppqqpp”并获胜。

为了解决这个问题，我们将遵循以下步骤：

  • l := 序列的大小

  • freq := 创建一个大小为 26 且填充为 0 的列表

  • 对于 i 从 0 到 l，递增 1，执行：

    • 将 sequence[i] 的 freq 递增 1

    • count := 0

    • 对于 i 从 0 到 25，执行：

      • 如果 freq[i] mod 2 不为 0，则

        • count := count + 1

    • 如果 count 为 0 或 count 为奇数，则

      • 返回 1

    • 否则，

      • 返回 2

示例

让我们看看下面的实现，以便更好地理解：

实时演示

def who_is_the_winner(sequence):
   l = len(sequence)
   freq = [0 for i in range(26)]
   for i in range(0, l, 1):
      freq[ord(sequence[i]) - ord('a')] += 1
   count = 0
   for i in range(26):
      if (freq[i] % 2 != 0):
         count += 1
   if (count == 0 or count & 1 == 1):
      return 1
   else:
      return 2
sequence = "pqpppq"
print("Player:", who_is_the_winner(sequence) )

输入

"pqpppq"

输出

Player: 1

更新于：2020年8月27日

74 次浏览

启动您的 职业生涯

通过完成课程获得认证

开始
广告