Tìm người chơi sắp xếp lại các ký tự để có được chuỗi palindrome đầu tiên bằng Python

Giả sử chúng ta có một chuỗi S với các chữ cái thường, bây giờ có hai người chơi đang chơi trò chơi. Các quy tắc như sau -

• Người chơi thắng trò chơi, nếu ở bất kỳ bước di chuyển nào, người chơi có thể xáo trộn các ký tự của chuỗi để có được chuỗi palindrome.

• Người chơi không thể thắng khi phải xóa bất kỳ ký tự nào khỏi chuỗi.

Chúng tôi phải lưu ý rằng cả hai người chơi đều chơi trò chơi một cách tối ưu và người chơi 1 bắt đầu trò chơi. Chúng ta phải tìm ra người chiến thắng trong trò chơi.

Vì vậy, nếu đầu vào là "pqpppq", thì đầu ra sẽ là Người chơi1 với tư cách là người chơi-1 trong bước đầu tiên, hãy sắp xếp các ký tự để nhận được “ppqqpp” và thắng trò chơi.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• l:=kích thước của chuỗi

• freq:=tạo một danh sách có kích thước 26 và được điền bằng 0

• đối với tôi trong phạm vi từ 0 đến l, tăng 1, làm

  • tăng tần suất của chuỗi [i] lên 1

  • đếm:=0

  • đối với tôi trong phạm vi từ 0 đến 25, hãy thực hiện

    • nếu freq [i] mod 2 không phải là 0, thì

      • count:=count + 1

  • nếu số đếm là 0 hoặc số đếm là số lẻ, thì

    • trả lại 1

  • nếu không,

    • trả lại 2

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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) )

Đầu vào

"pqpppq"

Đầu ra

Player: 1