Giả sử chúng ta có một chuỗi chữ thường s. Chúng ta phải tìm số lượng tối thiểu các chuỗi con liền kề trong đó s được chia thành các phần sao cho mỗi chuỗi con không tăng hoặc không giảm. Vì vậy, ví dụ:nếu chuỗi như "pqqqr" là một chuỗi không giảm và "qqqp" là một chuỗi không tăng.
Vì vậy, nếu đầu vào là s ="pqrsrqp", thì đầu ra sẽ là 2, vì chúng ta có thể ngắt các s như "pqrs" và "rqp".
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
nếu s trống thì
-
trả về 0
-
-
cuối cùng:=s [0]
-
hướng:=1
-
đếm:=1
-
đối với mỗi ký tự trong s, thực hiện
-
if char> last, then
-
nếu hướng giống như 1, thì
-
hướng:=0
-
-
ngược lại khi hướng giống như 2 thì
-
hướng:=1
-
count:=count + 1
-
-
-
ngược lại khi char
-
nếu hướng giống như 1, thì
-
hướng:=2
-
-
ngược lại khi hướng bằng 0 thì
-
hướng:=1
-
count:=count + 1
-
-
-
cuối cùng:=char
-
-
số lần trả lại
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn
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))
Đầu vào
"pqrsrqp"
Đầu ra
2