Python程式：查詢單調字串組的最小數量

假設我們有一個小寫字串s。我們需要找到將s劃分為多個連續子串的最小數量，使得每個子串要麼是非遞減的，要麼是非遞增的。例如，“pqqqr”是非遞減字串，“qqqp”是非遞增字串。

例如，如果輸入是s = "pqrsrqp"，則輸出為2，因為我們可以將s分解為"pqrs"和"rqp"。

為了解決這個問題，我們將遵循以下步驟：

  • 如果s為空，則

    • 返回0

  • last := s[0]

  • direction := 1

  • count := 1

  • 對於s中的每個字元，執行：

    • 如果char > last，則

      • 如果direction等於1，則

        • direction := 0

      • 否則，如果direction等於2，則

        • direction := 1

        • count := count + 1

    • 否則，如果char < last，則

      • 如果direction等於1，則

        • direction := 2

      • 否則，如果direction等於0，則

        • direction := 1

        • count := count + 1

    • last := char

  • 返回count

示例

讓我們看下面的實現來更好地理解

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

更新於：2021年10月12日

瀏覽量：225

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告