สมมติว่าเรามีสตริงตัวพิมพ์เล็ก s เราต้องหาจำนวนขั้นต่ำของสตริงย่อยที่ต่อเนื่องกัน ซึ่ง s ถูกแบ่งออกเป็นส่วน ๆ โดยที่แต่ละสตริงย่อยจะไม่เพิ่มขึ้นหรือไม่ลดลง ตัวอย่างเช่น หากสตริงเป็นเหมือน "pqqqr" เป็นสตริงที่ไม่ลดจำนวนลง และ "qqqp" เป็นสตริงที่ไม่เพิ่มขึ้น
ดังนั้น หากอินพุตเป็น s ="pqrsrqp" ผลลัพธ์จะเป็น 2 เพราะเราสามารถแยก s เช่น "pqrs" และ "rqp" ได้
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ถ้า s ว่างแล้ว
-
คืนค่า 0
-
-
สุดท้าย :=s[0]
-
ทิศทาง :=1
-
นับ :=1
-
สำหรับแต่ละอักขระใน s ทำ
-
ถ้าถ่าน> สุดท้ายแล้ว
-
ถ้าทิศทางเหมือนกับ 1 แล้ว
-
ทิศทาง :=0
-
-
มิฉะนั้นเมื่อทิศทางเหมือนกับ 2 แล้ว
-
ทิศทาง :=1
-
นับ :=นับ + 1
-
-
-
มิฉะนั้นเมื่อถ่าน <สุดท้ายแล้ว
-
ถ้าทิศทางเหมือนกับ 1 แล้ว
-
ทิศทาง :=2
-
-
มิฉะนั้นเมื่อทิศทางเหมือนกับ 0 แล้ว
-
ทิศทาง :=1
-
นับ :=นับ + 1
-
-
-
สุดท้าย :=ถ่าน
-
-
จำนวนคืน
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
def solve(s): if not s: return 0 last = s[0] direction = 1 count = 1 for char in s: if char > last: if direction == 1: direction = 0 elif direction == 2: direction = 1 count += 1 elif char < last: if direction == 1: direction = 2 elif direction == 0: direction = 1 count += 1 last = char return count s = "pqrsrqp" print(solve(s))
อินพุต
"pqrsrqp"
ผลลัพธ์
2
