สมมติว่าเรามีสตริง S ที่มีตัวพิมพ์เล็ก ตอนนี้มีผู้เล่นสองคนกำลังเล่นเกม กฎมีดังต่อไปนี้ −
-
ผู้เล่นชนะเกม หากผู้เล่นสามารถสับเปลี่ยนอักขระของสตริงเพื่อให้ได้สตริงพาลินโดรมได้
-
ผู้เล่นไม่สามารถชนะได้เมื่อต้องลบอักขระใดๆ ออกจากสตริง
เราต้องจำไว้ว่าผู้เล่นทั้งสองเล่นเกมได้อย่างเหมาะสมและผู้เล่น1 เริ่มเกม เราต้องหาผู้ชนะของเกมให้ได้
ดังนั้น หากอินพุตเป็นเหมือน "pqpppq" เอาต์พุตจะเป็น Player1 เนื่องจากผู้เล่น-1 ในขั้นตอนแรกจะจัดเรียงตัวละครเพื่อรับ “ppqqpp” และชนะเกม
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
l :=ขนาดของลำดับ
-
freq :=ทำรายการขนาด 26 และเติม 0
-
สำหรับฉันอยู่ในช่วง 0 ถึง l เพิ่มขึ้น 1 ทำ
-
เพิ่มความถี่ของลำดับ[i] ขึ้น 1
-
นับ :=0
-
สำหรับผมอยู่ในช่วง 0 ถึง 25 ทำ
-
ถ้า freq[i] mod 2 ไม่ใช่ 0 แล้ว
-
นับ :=นับ + 1
-
-
-
หากนับเป็น 0 หรือนับเป็นคี่
-
กลับ 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
