在 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

Arnab Chakraborty

更新於：2020年8月27日

74 次瀏覽

啟動您的 職業生涯

透過完成課程獲得認證

開始